数据结构(6_3_1)——图的广度优先遍历

树和图的广度优先遍历区别

树的广度优先遍历：

图的广度优先遍历：

代码：

注:以下代码只适合连通图

#include <stdio.h>
#include <stdbool.h>#define MAX_VERTEX_NUM 100typedef struct ArcNode {int adjvex; // 该边所指向的顶点的位置struct ArcNode* nextarc; // 指向下一条边的指针
} ArcNode;typedef struct VNode {char data; // 顶点信息ArcNode* firstarc; // 指向第一条边的指针
} VNode, AdjList[MAX_VERTEX_NUM];typedef struct {AdjList vertices;int vexnum, arcnum; // 图的顶点数和边数
} ALGraph;bool visited[MAX_VERTEX_NUM]; // 访问标记数组// 访问顶点的函数
void visit(int v) {printf("%d ", v);
}// 判断队列是否为空
bool isEmpty(int front, int rear) {return front == rear;
}// 入队操作
void EnQueue(int* queue, int rear, int v) {queue[rear++] = v;
}// 出队操作
void DeQueue(int* queue, int* front, int* v) {*v = queue[(*front)++];
}// 返回顶点v的第一个邻接点
int FirstNeighbor(ALGraph* G, int v) {if (G->vertices[v].firstarc) {return G->vertices[v].firstarc->adjvex;}return -1;
}// 返回顶点v相对于w的下一个邻接点
int NextNeighbor(ALGraph* G, int v, int w) {ArcNode* p = G->vertices[v].firstarc;while (p && p->adjvex != w) {p = p->nextarc;}if (p && p->nextarc) {return p->nextarc->adjvex;}return -1;
}// 广度优先遍历
void BFS(ALGraph* G, int v) {int queue[MAX_VERTEX_NUM]; // 辅助队列int front = 0, rear = 0; // 队列的头尾指针int w;visit(v); // 访问初始顶点vvisited[v] = true; // 对v做已访问标记EnQueue(queue, rear, v); // 顶点v入队列while (!isEmpty(front, rear)) {DeQueue(queue, &front, &v); // 顶点v出队列for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {// 检查v所有邻接点if (!visited[w]) { // w为v的尚未访问的邻接点visit(w); // 访问顶点wvisited[w] = true; // 对w做已访问标记EnQueue(queue, rear, w); // 顶点w入队列}}}
}// 主函数，用于演示
int main() {// 假设图G已经被正确初始化ALGraph G;// ... 初始化图G ...// 初始化访问标记数组for (int i = 0; i < G.vexnum; ++i) {visited[i] = false;}// 从顶点0开始进行广度优先遍历BFS(&G, 0);return 0;
}

练习：

遍历序列的可变性

BFS算法（优化版可遍历非连通图）

代码：

bool visited[MAX_VERTEX_NUM];//访问标记数组void BFSTraverse(Graph G) {//对图G进行广度优先遍历for (i = 0; i < G.vexnum; ++i)visited[i] = false;//访问标记数组初始化InitQueue(Q);//初始化辅助队列Qfor (i = 0; i < G.vexnum; ++i)//从0号顶点开始遍历if (!visited[i])//对每个连通分量调用一次BFSBFS(G, i);//vi未访问过,从vi开始BFS}
//广度优先遍历
void BFS(Graph G, int v) {//从顶点v出发，广度优先遍历图Gvisit(v);//访问初始顶点vvisited[v] = true;//对v做已访问标记Enqueue(Q, v);//顶点v入队列Qwhile (!isEmpty(Q)) {DeQueue(Q, v);//顶点v出队列for(w=FirsitNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w);)//检查v所有邻接点if (!visited[w]) {//w为v的尚未访问的邻接点visit(w);//访问顶点wvisited[w] = true;//等于w做已访问标记EnQueue(Q, W);//顶点w入队列}}
}