采用邻接矩阵表示法创建无向网的算法
时间: 2024-01-10 16:44:57 浏览: 25
邻接矩阵是一种常见的图的表示方法,可以用来表示有向图和无向图。对于无向网,我们可以采用邻接矩阵表示法来创建。
具体算法步骤如下:
1. 定义一个二维数组adjMatrix[N][N],其中N为顶点数,初始化数组元素为0。
2. 对于每条边(u, v),将adjMatrix[u][v]和adjMatrix[v][u]的值设置为边的权值。
3. 如果两个顶点之间没有边,则adjMatrix[u][v]和adjMatrix[v][u]的值为0。
4. 最终得到的邻接矩阵就是无向网的表示。
下面是一个示例代码:
```
// 定义邻接矩阵
int adjMatrix[N][N];
// 初始化邻接矩阵
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
adjMatrix[i][j] = 0;
}
}
// 添加边
for(int k=0; k<edgeNum; k++){
int u, v, w;
cin >> u >> v >> w;
adjMatrix[u][v] = w;
adjMatrix[v][u] = w;
}
```
其中,edgeNum为边的数量,u和v是边的两个顶点,w是边的权值。通过循环输入每条边的信息,可以创建一个无向网的邻接矩阵。
相关问题
}//LocateVex int CreateUDN(AMGraph &G){ //采用邻接矩阵表示法,创建无向网G /**************begin************/ /**************end************/ }//CreateUDN int main(){ //cout << "************算法6.1 采用邻接矩阵表示法创建无向网**************" << endl << endl; AMGraph G; int i , j; CreateUDN(G); cout <<endl; //cout << "*****邻接矩阵表示法创建的无向网*****" << endl; for(i = 0 ; i < G.vexnum ; ++i){ for(j = 0; j < G.vexnum; ++j){ if(j != G.vexnum - 1){ if(G.arcs[i][j] != MaxInt) cout << G.arcs[i][j] << "\t"; else cout << "∞" << "\t"; } else{ if(G.arcs[i][j] != MaxInt) cout << G.arcs[i][j] <<endl; else cout << "∞" <<endl; } } }//for cout <<endl; return 0; }//main 测试输入: 3 2 A B V A B 2 A V 4 预期输出: ∞ 2 4 2 ∞ ∞ 4 ∞ ∞
下面是完整的代码实现:
```c++
#include <iostream>
using namespace std;
#define MaxInt 0x7ffffffe //最大值(即0X7FFFFFFF除去符号位)
typedef struct{
char vexs[100]; //顶点集合
int arcs[100][100]; //邻接矩阵,可看作边表
int vexnum,arcnum; //图的当前点数和边数
}AMGraph;
int LocateVex(AMGraph G,char ch){
//确定ch在G中的位置
for(int i = 0 ; i < G.vexnum ; ++i)
if(G.vexs[i] == ch)
return i;
return -1;
}
int CreateUDN(AMGraph &G){
//采用邻接矩阵表示法,创建无向网G
cin >> G.vexnum >> G.arcnum; //输入点数和边数
for(int i = 0 ; i < G.vexnum ; ++i)
cin >> G.vexs[i]; //输入顶点信息
//初始化邻接矩阵
for(int i = 0 ; i < G.vexnum ; ++i)
for(int j = 0 ; j < G.vexnum ; ++j)
G.arcs[i][j] = MaxInt;
//构造邻接矩阵
for(int k = 0 ; k < G.arcnum ; ++k){
char v1,v2;
int w;
cin >> v1 >> v2 >> w; //输入边(vi,vj)上的权值w
int i = LocateVex(G,v1); //确定v1和v2在G中的位置
int j = LocateVex(G,v2);
G.arcs[i][j] = w;
G.arcs[j][i] = G.arcs[i][j]; //因为是无向图,矩阵对称
}
return 1;
}
int main(){
cout << "************算法6.1 采用邻接矩阵表示法创建无向网**************" << endl << endl;
AMGraph G;
int i , j;
CreateUDN(G);
cout << endl;
cout << "*****邻接矩阵表示法创建的无向网*****" << endl;
for(i = 0 ; i < G.vexnum ; ++i){
for(j = 0; j < G.vexnum; ++j){
if(j != G.vexnum - 1){
if(G.arcs[i][j] != MaxInt)
cout << G.arcs[i][j] << "\t";
else
cout << "∞" << "\t";
}
else{
if(G.arcs[i][j] != MaxInt)
cout << G.arcs[i][j] <<endl;
else
cout << "∞" <<endl;
}
}
}//for
cout <<endl;
return 0;
}
```
输入测试数据:
```
3 2
A B V
A B 2
A V 4
```
输出结果:
```
************算法6.1 采用邻接矩阵表示法创建无向网**************
*****邻接矩阵表示法创建的无向网*****
∞ 2 4
2 ∞ ∞
4 ∞ ∞
```
用图的邻接矩阵表示法实现图的深度优先搜索和广度优先搜索
图的邻接矩阵表示法是一种常见的图的表示方法,可以用来实现图的深度优先搜索和广度优先搜索。
深度优先搜索(DFS)是一种遍历图的算法,它从一个起始顶点开始,沿着一条路径一直走到底,直到不能再走为止,然后回溯到上一个顶点,继续沿着另一条路径走下去,直到遍历完整个图。DFS可以用递归或栈来实现。
广度优先搜索(BFS)是一种遍历图的算法,它从一个起始顶点开始,先访问它的所有邻居顶点,然后再访问它们的邻居顶点,以此类推,直到遍历完整个图。BFS可以用队列来实现。
具体实现时,可以先根据图的邻接矩阵表示法构建出图的邻接矩阵,然后根据DFS或BFS的算法思想,遍历整个图。在遍历过程中,可以使用一个数组来记录每个顶点的状态,例如是否已经被访问过等。遍历结束后,可以输出遍历的结果,例如每个顶点的访问顺序等。
需要注意的是,图的邻接矩阵表示法只适用于稠密图,对于稀疏图,应该使用邻接表或邻接多重表来表示。此外,在实际应用中,还需要考虑图的大小和算法的时间复杂度等因素。