广度优先的原则是从图的一个顶点出发,依次访问它的相邻节点,接着从这些相邻节点出发再访问它们的相邻节点。并使“先被访问的顶点的相邻节点”先于“后被访问的顶点的相邻节点”被访问。直到图中所有的顶点均被访问。例如下图:
上图的广度优先访问顺序为:
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12
来看一下程序的实现过程。这里需要引入一个辅助的数据结构——队列。用队列来存放当前顶点的相邻节点。
//广度优先搜索 bool graph_breadth_first_search(s_graph *graph) { if (graph == null) { return false; } //设置队列 s_queue queue; init_queue(&queue, sizeof(int), free_int, null); //设置顶点已访问标志 bool visited[graph->size]; for (int i = 0; i < graph->size; i++) { visited[i] = false; } //访问所有的顶点 for (int i = 0; i < graph->size; i++) { //深度广先访问顶点 graph_bfs(graph, i, visited, &queue); } //销毁队列 destroy_queue(&queue); return true; } //广度优先访问顶点递归算法 void graph_bfs(s_graph *graph, int v_ind, bool *visited, s_queue *queue) { //如果此顶点已被访问,则直接返回 if (visited[v_ind]) { return; } //设置此顶点为已访问 visited[v_ind] = true; //调用访问回调函数访问此节点 graph->visit_vertex(graph->vertex[v_ind]); //取得下一条边 s_arccell *ac = graph->vertex[v_ind].arccel_first; //循环所有关联i的边 while (ac != null) { //将此顶点的关联顶点加入队列 int *ival = malloc(sizeof(int)); *ival = ac->i_index; queue_in(queue, ival); //如果还有下一条j相关的边 s_arccell *ac_p = graph->vertex[ac->j_index].arccel_first; while (ac_p != null) { //将此顶点的关联顶点加入队列 int *jval = malloc(sizeof(int)); *jval = ac_p->j_index; queue_in(queue, jval); ac_p = ac_p->next_j; } //下一条i边 ac = ac->next_i; } //如果队列不为空,即:出队列成功 int *vertex = null; if (queue_out(queue, (void**) &vertex)) { //对此顶点进行广度优先搜索 graph_bfs(graph, *vertex, visited, queue); } }
再来看一下main函数:
#include <stdio.h> #include <stdlib.h> #include "graph.h" int main(int argc, char **args) { //邻接表 s_graph graph; graph_init(&graph, 13, &visit_int, &visit_int); /* * 初始化数据部分代码略 */ //深度优先遍历图 graph_breadth_first_search(&graph); //销毁邻接表 graph_destroy(&graph); return 0; }
运行结果:
0 1 2 3 4 5 6 7 8 9 10 11 12
本例代码:
code path chapter.06/e.g.6.6/ https https://github.com/magicworldos/datastructure.git git git@github.com:magicworldos/datastructure.git subverion https://github.com/magicworldos/datastructure
Copyright © 2015-2023 问渠网 辽ICP备15013245号