实现基于邻接矩阵表示的广度优先遍历。 函数接口定义: void BFS(Graph G, int v); 其中 G 是基于邻接矩阵存储表示的无向图,v表示遍历起点。 裁判测试程序样例: #include <stdio.h> #include <stdlib.h> #define MVNum 10 int visited[MVNum]; typedef struct{ char vexs[MVNum]; int arcs[MVNum][MVNum]; int vexnum,arcnum; }Graph; void CreateUDN(Graph &G);//实现细节隐藏 void BFS(Graph G, int v); void BFSTraverse(Graph G){ int v; for(v = 0; v < G.vexnum; ++v) visited[v] = 0; for(v = 0; v < G.vexnum; ++v) if(!visited[v]) BFS(G, v); } int main(){ Graph G; CreateUDN(G); BFSTraverse(G); return 0; } /* 请在这里填写答案 */ 输入样例: 输入第1行为结点数vexnum和边数arcnum。第2行为结点的值,依次输入arcnum行,每行输入两个结点的值表示该两个结点互为邻接点。 8 8 ABCDEFGH A B A C B D B E C F C G D H E H 输出样例: 遍历序列。 A B C D E F G H
时间: 2024-02-14 11:12:45 浏览: 64
建立图的邻接矩阵或邻接表存储并在此基础上实现图的深度优先遍历和广度优先遍历.doc
5星 · 资源好评率100%
void BFS(Graph G, int v)
{
int queue[MVNum]; // 定义一个队列
int front = 0, rear = 0; // 定义队列的头和尾指针
visited[v] = 1; // 标记当前节点已经访问过
printf("%c ", G.vexs[v]); // 输出当前节点的值
queue[rear++] = v; // 将当前节点加入队列中
while (front != rear) // 队列不为空时
{
int w = queue[front++]; // 取出队首节点
for (int i = 0; i < G.vexnum; i++) // 遍历该节点的所有相邻节点
{
if (G.arcs[w][i] == 1 && !visited[i]) // 如果该相邻节点未被访问过且与当前节点有连边
{
visited[i] = 1; // 标记该相邻节点已经访问过
printf("%c ", G.vexs[i]); // 输出该相邻节点的值
queue[rear++] = i; // 将该相邻节点加入队列中
}
}
}
}
注意,在调用 BFS 函数之前需要先将 visited 数组初始化为 0,表示所有节点都未被访问过。同时,如果图不是连通的,需要在 BFSTraverse 函数中使用循环遍历每个节点,以确保对所有节点都进行了遍历。
阅读全文