本文共 1739 字，大约阅读时间需要 5 分钟。

• 这里贴出我之前的一篇博文，里面有我用邻接矩阵、邻接表和十字链表实现图的代码：

一、图的遍历

1、基本概念

• 所谓图的遍历，是指从图中的某一顶点出发，按照某种搜索算法沿着图中的边对图中的顶点访问一次有且仅访问一次。图的遍历算法主要有两种：广度优先搜索和深度优先搜索。

2、广度优先搜索算法

• 广度优先搜索，英文名为Breadth-First-Search，通常简写为 BFS，类似于二叉树的层次遍历，其基本思想如下：
  1）以顶点 v 为起始点，首先访问该点。
  2）接着依次访问起始点的邻接点，再从这些邻接点出发访问他们自己尚未被访问过的邻接点。
  3）重复1）2）直到图中所有顶点都被访问过；如果不能访问所有顶点，那么更换一个初始点再一次进行上述操作。
• 简单来说，就是以 v 为起点，由近到远依次访问和 v 有路径相通且路径长度依次为 1，2……的点。
  
• 以上图为例，以 e 为初始点使用广度优先遍历得出序列：e b c a d。代码见博文头部的链接。
• 图的广度优先搜索算法，在实现时需要借助队列，n 个顶点便需要入队 n 次，故而最坏情况下，空间复杂度为O(|V|)。时间复杂度，则需要根据具体实现的是邻接矩阵还是邻接表，若是邻接表则时间复杂度为O(|V|+|E|)，因为每个点要搜索一次，而每个点的边表也需要搜索一次；若是用邻接矩阵，则时间复杂度为O(|V|²)。

3、深度优先搜索算法

• 深度优先搜索英文为：Depth-First-Search，通常简写为 DFS，类似于树的先序遍历，其基本思想如下：
• 1）以 v 为初始点，首先访问该点；
• 2）访问与 v 邻接且未被访问过的任何邻接点w₁，再访问与 w₁ 邻接的点 w₂……反复如是，直到不能再继续向下访问；
• 3）依次退回最近被访问过的点，若其还有未被访问的邻接点，则从该点开始重复上述过程，直到途中所有点均已访问过。
• 同样的图，若 e 为初始点依照深度优先搜索遍历得出序列：e b a d c。
• 深度优先搜索算法的实现，需要借助递归栈，因此其空间复杂度为O(|V|)，邻接矩阵的深度优先搜索的时间复杂度为O(|V|²)，邻接表的深度优先搜索时间复杂度为O(|V|+|E|)。

二、图遍历算法的应用

1、BFS 算法的应用

• 图的广度优先搜索算法的应用主要有两个：求解单源最短路径问题和生成树。

1.1、最短路径求解

• 需要求最短路径的图，通常是无权图或所有边的权都一样，而图的广度优先搜索本就是按照与出发点远近依次访问顶点的，因此特别适合用于求解最短路径问题。
• 其伪代码如下：

void Graph::BFSMinDistance(Graph g, int u){
   	int *distance = new int[vexnum];	int *visited = new int[vexnum];	for(int i=0; i
   
    =0;w=NextNeighbor(u,w))		{
   			if(!visited[w])			{
   				visited[w]=true;				distance[w]=distance[u]+1;				EnQueue(Q,w);			}		}	}}
   

1.2、广度优先生成树

• 通过对一个图进行广度优先搜索遍历，可以得到一棵广度优先生成树。邻接矩阵的广度优先生成树是唯一的，因为图的邻接矩阵是唯一的；而图的邻接表往往并不唯一，相对应的其广度优先生成树也是不唯一的。
  

2、深度优先生成树或林

• 深度优先搜索通常用于将图转为树或森林，但不是每个图都能如此。连通图通过DFS可以生成对应的树，而不是连通图通过 DFS 生成的是森林。同样的，基于邻接矩阵的生成树或林是唯一的，邻接表的则不唯一。

3、通过遍历判断图的连通性

• 无论是有向图或是无向图，通过通过广度优先搜索遍历或深度优先搜索遍历，来判断图是否连通。
• 对于无向图，若是连通图，则从某一个顶点出发，仅需一次遍历就能够访问图中所有的点，而如果非连通图则一次遍历只能访问一个连通分量。
• 对于有向图，若从初始点到图中每个点都有路径，则能够访问到所有点，表现在邻接矩阵上就是 i 所在行（可以包括自身）都是1。

转载地址：http://whqgn.baihongyu.com/