算法：图的广度优先遍历（Breadth First Search) |
您所在的位置：网站首页 › 遍历算法流程图 › 算法：图的广度优先遍历（Breadth First Search) |
算法：图的广度优先遍历（Breadth First Search)
|
图的遍历和树的遍历类似，我们希望从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历（Traverse Graph)。 图的遍历方法一般有两种，第一种是我们在前面讲过的《深度优先遍历（Depth First Search)》,也有称为深度优先搜索，简称为DFS。第二种是广度优先遍历（Breadth First Search)，也有称为广度优先搜索，简称为BFS。我们在《队列与广度优先搜索》中已经较为详细地讲述了广度优先搜索的策略，这里不再赘述。如果说图的深度优先遍历类似树的前序遍历，那么图的广度优先遍历就类似于树的层序遍历了，我们把图7-5-3的第一幅图稍微变形成第二幅图所示，这样层次感就更强了，广度优先遍历需要用到队列的操作，可以参考《队列的顺序存储结构》。  下面只给出邻接矩阵和邻接表存储方式时的图的广度优先遍历的算法代码，没有给出整体可供测试运行的代码，其实只需要再写一个创建图的函数就可以进行整体测试了，可以参考《邻接矩阵创建图》和《邻接表创建图》 一、如果我们使用的是邻接矩阵的方式，则代码如下：（改编自《大话数据结构》） 代码语言：cpp复制typedef char VertexType; /* 顶点类型应由用户定义 */ typedef int EdgeType; /* 边上的权值类型应由用户定义 */ #define MAXSIZE 9 /* 存储空间初始分配量 */ #define MAXEDGE 15 #define MAXVEX 9 typedef struct { VertexType vexs[MAXVEX]; /* 顶点表 */ EdgeType arc[MAXVEX][MAXVEX];/* 邻接矩阵，可看作边表 */ int numVertexes, numEdges; /* 图中当前的顶点数和边数 */ } MGraph; /* 邻接矩阵的广度遍历算法 */ void BFSTraverse(MGraph G) { int i, j; Queue Q; for (i = 0; i |
【本文地址】
今日新闻 |
推荐新闻 |