图的遍历

1、图的遍历

---- 图的遍历和树的遍历类似，我们希望从图中某一顶点出发访遍图中其余顶点，且使每个顶点仅被访问一次，这一过程

就叫做图的遍历（Traversing Graph）。

---- 树的遍历都是从根结点发起（只有一个），其余所有结点都只有一个双亲。可图就复杂多了，因为它的任一顶点都可能和其余的所有

顶点相邻接，极有可能存在沿着某条路径搜索后，又回到原顶点，而有些顶点却还没有遍历到的情况。因此我们需要在遍历过程中把访问

过的顶点打上标记，以避免访问多次而不自知。具体办法是设置一个访问数组visited[n]，n是图中顶点的个数，初值为0，访问过后设置为1.

通常有两种图的遍历次序方案：它们是深度优先遍历和广度优先遍历。

2、深度优先遍历

---- 深度优先遍历（Depth First Search）,有时也称为深度优先搜索，简称为DFS。

如上图所示，从顶点A开始要走遍图中所有的顶点并做上标记，首先我们从顶点A开始，做上表示走过的记号后，面前有两条路，通向B和F，

先定一个原则，在没有碰到重复顶点的情况下，始终是向右手边走，于是走到了B顶点。整个行路过程，可参看上图的右边，此时发现有三个

分支C、I、G，右边通行原则，我们走到了C顶点，遇到两个分支D和I，右边通行原则，走到D遇到分支H、G、I、E，走到E顶点，再到F，之后

是A，发现顶点A已经走过，返回到F，可以选择G顶点，它有三条通道B、D、H，发现B和D都已经是走过的，于是走到H，H之后的两条通道D和

E都已经走过了。此时我们是否已经遍历了所有的顶点呢？没有。按原路返回，在顶点H处，再无通道没走过，返回到G，也无未走过的通道，返回

到F，没有通道，返回到E，都走过了，返回到D，三个通道G、H、I，I是一个新顶点，没有走过，标记下来，继续返回直到返回顶点A，确认已经

遍历完所有的顶点，即完成任务。

---- 类似于一棵树的前序遍历，它从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径

相同的顶点都被访问到。这里提到的是连通图，对于非连通图，只需要对它的连通分量分别进行深度优先遍历，即在先前一个顶点进行一次深度优

先遍历后，若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问到为止。

如果我们用的是邻接矩阵的方式，则代码如下：

typedef char VertexType;
typedef int EdgeType;
#define Max 100
typedef struct
{
	VertexType vexs[Max]; //顶点表
	EdgeType arc[Max][Max]; //邻接矩阵，可看作边表
	int numVertexes,numEdges;  //图中当前的顶点数和边数
}MGraph;

bool visited[Max];  //访问标志的数组
//邻接矩阵的深度优先递归算法
void DFS(MGraph G,int i)
{
	int j;
	visited[i] = true;
	printf("%c",G.vexs[i]); //打印顶点
	for(j = 0;j<G.numVertexes;j++)
	{
		if(G.arc[i][j]==1 && !visited[j])
			DFS(G,j);
	}
}
//邻接矩阵的深度遍历操作
void DFSTraverse(MGraph G)
{
	int i;
	for(i = 0;i<G.numVertexes;i++)
		visited[i] = false; //初始化所有顶点状态都是未访问过状态
	for(i = 0;i<G.numVertexes;i++)
		if(!visited[i]) //对未访问过的顶点调用DFS，若是连通图，只会执行一次
			DFS(G,i);
}

代码执行的过程，就是寻找所有顶点的过程。如果图结构是邻接表结构，其DFSTraverse函数的代码几乎是相同的，只是在递归函数中因为

将数组换成了链表而有所不同，代码如下：

//结点的定义
typedef char VertexType;
typedef int EdgeType;
#define Max 100
bool visited[Max];
typedef struct EdgeNode  //边表结点
{
	int adjvex; //邻接点域
	EdgeType weight; //权值
	struct EdgeNode *next;
}EdgeNode;

typedef struct VertexNode //顶点表结点
{
	VertexType data; //顶点域
	EdgeNode *firstedge; //边表头指针
}VertexNode,AdjList[Max];

typedef struct
{
	AdjList adjList;
	int numVertexes,numEdges; //图中当前顶点数和边数
}GraphAdjList;
//邻接表的深度优先递归算法
void DFS(GraphAdjList *GL,int i)
{
	EdgeNode *p;
	visited[i] = true;
	printf("%c",GL->adjList[i].data);
	p = GL->adjList[i].firstedge;
	while(p)
	{
		if(!visited[p->adjvex])
			DFS(GL,p->adjvex); //对未访问的邻接顶点进行递归调用
		p = p->next;
	}
}
//邻接表的深度优先遍历操作
void DFSTraverse(GraphAdjList GL)
{
	int i;
	for(i = 0;i<GL.numVertexes;i++)
		visited[i] = false;
	for(i = 0;i<GL.numVertexes;i++)
		if(!visited[i])
			DFS(&GL,i);
}

对比两个不同存储结构的深度优先遍历算法，对于n个顶点e条边的图来说，邻接矩阵由于是二维数组，要查找每个顶点的邻接点需要访问矩阵中的

所有元素，因此都需要O(n^2)的时间。而邻接表做存储结构时，找邻接点所需的时间取决于顶点和边的数量，所以是O(n+e).显然对于点多边少的

稀疏图来说，邻接表结构使得算法在时间效率上大大提高。

3、广度优先遍历

---- 广度优先遍历（Breadth First Search）,又称为广度优先搜索，简称BFS。如果说图的深度优先遍历类似于树的前序遍历，那么图的广度优先

遍历就类似于树的层序遍历了。将上一幅图稍微变形，变形原则是顶点A放置在最上第一层，让与它有边的顶点B、F为第二层，再让与B和F有边

的顶点C、I、G、E为第三层，再将与这四个顶点有边的D、H放在第四层，如下图右图所示，此时在视觉上感觉图的形状发生了变化，其实顶点

和边的关系还是完全相同的。

图的深度优先遍历与广度优先遍历算法在时间复杂度上是一样的，不同之处仅仅在于对顶点访问顺序的不同。