实现基于邻接矩阵表示的广度优先遍历。 函数接口定义: 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 19:12:45 浏览: 62
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 函数中使用循环遍历每个节点,以确保对所有节点都进行了遍历。
阅读全文