1.理解并实现无向图邻接矩阵的创建,理解并实现无向图邻接矩阵方式存储的广度优先遍历的算法,转换成程序并上机实现; //用两个数组分别存储顶点表和邻接矩阵 #define MaxInt 32767 //表示极大值,即∞ #define MVNum 100 //最大顶点数 typedef char VerTexType; //假设顶点的数据类型为字符型 typedef int ArcType; //假设边的权值类型为整型 typedef struct{ VerTexType vexs[MVNum]; //顶点表 ArcType arcs[MVNum][MVNum]; //邻接矩阵 int vexnum,arcnum; //图的当前点数和边数 }AMGraph;
时间: 2023-06-20 07:05:30 浏览: 82
首先,我们需要了解无向图邻接矩阵的基本概念:邻接矩阵是一种常用的图的表示方法,用一个二维数组表示图中各个顶点之间的关系。对于无向图而言,邻接矩阵是一个对称矩阵,即若顶点 i 与顶点 j 之间有边,则 arcs[i][j]=arcs[j][i]=1,否则 arcs[i][j]=arcs[j][i]=0。
下面是无向图邻接矩阵的创建代码:
```
void CreateUDN(AMGraph &G)
{
int i, j, k;
cout << "请输入总顶点数和总边数:";
cin >> G.vexnum >> G.arcnum;
cout << "请输入各个顶点的信息:";
for (i = 0; i < G.vexnum; i++)
cin >> G.vexs[i];
for (i = 0; i < G.vexnum; i++)
for (j = 0; j < G.vexnum; j++)
G.arcs[i][j] = MaxInt;
cout << "请输入每条边的两个端点及权值:";
for (k = 0; k < G.arcnum; k++)
{
cin >> i >> j >> G.arcs[i][j];
G.arcs[j][i] = G.arcs[i][j];
}
}
```
接下来是无向图邻接矩阵存储方式下的广度优先遍历算法:
```
void BFS(AMGraph G, int v, bool visited[])
{
queue<int> q;
cout << G.vexs[v] << " ";
visited[v] = true;
q.push(v);
while (!q.empty())
{
int i = q.front();
q.pop();
for (int j = 0; j < G.vexnum; j++)
{
if (G.arcs[i][j] != MaxInt && !visited[j])
{
cout << G.vexs[j] << " ";
visited[j] = true;
q.push(j);
}
}
}
}
void BFSTraverse(AMGraph G)
{
bool visited[MVNum] = {false};
for (int i = 0; i < G.vexnum; i++)
{
if (!visited[i])
{
BFS(G, i, visited);
}
}
}
```
以上是基本代码实现,可以根据需要进行优化和改进。