遍历:图跟树意思一样。

图的遍历:把图里的每一个顶点访问一遍，且不能有重复的访问。

图的遍历:深度优先搜索(Depth First Search,DFS)和广度优先搜索(Breadth First Search,BFS)。

6.2.1 深度优先搜索- DFS

迷宫中有一堆灯泡，要一个个点亮。

假设入口的先点亮，视野范围内的3个灯泡，先点亮一个，并继续往下点亮。

选其中一个继续往下点亮。

此时的位置，看到灯都亮了，原路返回，并不能直接退出，因为不知道其他灯是否都点亮了。

原路返回到此位置，发现有灯没亮，选择一个继续往下点亮。

继续点亮。

此时，视力范围内的都亮了。

不能直接出去，因为不知道是否还有其他岔路口，为保险起见，不能从任意结点出去，必须原路返回，一路返回到出口，才可以确定迷宫中的灯都被点亮了。

这个例子，演示的是一个深度优先搜索的过程，当访问完一个结点后，一定是原路返回的，这个行为在程序中对应的就是堆栈的出栈一种行为。

/*
树的遍历:深度优先搜索(Depth First Search,DFS)(伪代码)
类似于树的优先遍历的一个推广.
若有N个顶点、E条边,时间复杂度是:
用邻接表存储图,有O(N+E).
用邻接矩阵存储图,有O(N^2).
*/
void DFS(Vertex V){
	/*
	从给定的结点V出发标记为访问过,访问到某个结点的时候,把灯点亮,并设置true.
	*/
	visited[V] = true;
	for(V 的每个邻接点 W){/*FOR非常耗时*/
		/*
		对于V的每个邻接点W,如果灯没被点亮,那么就点亮.
		递归的去调用DFS.
		先把W点亮,再去把W的邻接点点亮,
		当所有的邻接点都点亮了,那么DFS调用就结束了,就返回上一层这个原路返回的过程.
		*/
		if(!visited[W]){
			DFS(W);
		}
	}
}

若有N个顶点、E条边,时间复杂度是:

用邻接表存储图,有O(N+E).

用邻接矩阵存储图,有O(N^2).

解释:

如果用的邻接表，那么V的每个邻接点，只要访问这个V对应的链表一个个访问过去就好了，链表上面邻接点的总个数等于它两倍的边数。

总的这个时间复杂度，每个结点访问了一次，每条边访问了一次，最终O(N+E)。

如果用邻接矩阵存储图,当我们在说V的每个邻接点的时候，实际上是需要把这个邻接矩阵对应V的一整行N个顶点全都要访问一遍，才知道此顶点的邻接点，所以整个的复杂度是N，在里面套了一层N，所以有O(N^2).

源码: DFS-邻接表存储 -O(N顶点数+E边数)

#include<stdio.h>
/*
图:DFS-邻接表存储
*/
int main(void){
	return 0;
}
void Visit(Vertex V){
	printf("正在访问顶点%d\n", V);
}
/* 
Visited[]为全局变量，已经初始化为false 
*/
void DFS(LGraph Graph, Vertex V, void (*Visit)(Vertex)){
	/* 
	以V为出发点对邻接表存储的图Graph进行DFS搜索 
	*/
	PtrToAdjVNode W;
	/* 访问第V个顶点 */
	Visit(V);
	/* 标记V已访问 */
	Visited[V] = true;
	/* 对V的每个邻接点W->AdjV */
	for(W=Graph->G[V].FirstEdge; W; W=W->Next){
		/* 若W->AdjV未被访问 */
		if(!Visited[W->AdjV]){
			/* 则递归访问之 */
			DFS(Graph, W->AdjV, Visit);
		}
	}
}

6.2.2 广度优先搜索- BFS

广度优先搜索在树中相当于层序遍历，从根结点出发，第一个被访问，然后从上到下，从左到右，一层层的访问这些结点。

程序实现，借助队列。首先把结点1入队，把它弹出时，会把其左右儿子继续入队，再把结点2弹出时，再把其左右儿子入队，以此类推。

在图中如何实现呢？

指定顶点1为起点，先压入队列的循环，弹出时，就顺序的把直接跟1有边相连的点234567都一一压入队列。

下一轮，弹出顶点2，就顺序的把直接跟2有边相连的点89都一一压入队列。

下一层也按照这样的顺序来访问。

以此类推。

这就是一个广度优先搜索。

/*
树的遍历:广度优先搜索(Breadth First Search,BFS)(伪代码)
类似于树的层序遍历的一个推广.
若有N个顶点、E条边,时间复杂度是:
用邻接表存储图,有O(N+E).
用邻接矩阵存储图,有O(N^2).
*/
void BFS(Vertex V){
	/*
	从给定的结点V出发标记为访问过,访问到某个结点的时候,访问过,并设置true.
	并把初始顶点V并压入队列里.
	*/
	visited[V] = true;
	Enqueue(V, Q);
	while(!IsEmpty(Q)){
		V = Dequeue(Q);
		/*
		从队列里弹出一个结点V,并访问它的每个邻接点,
		如果没被访问过,那么先设置成访问,并把邻接点入队列.
		*/
		for(V 的每个邻接点W){/*FOR非常耗时*/
			if(!visited[W]){
				visited[W] = true;
				Enqueue(W, Q);
			}
		}
	}
}

若有N个顶点、E条边,时间复杂度是:

用邻接表存储图,有O(N+E).

用邻接矩阵存储图,有O(N^2).

解释:

如果用邻接表去存储图的话，发现每一个顶点入队列一次，有N个结点，一共是N步，V的每一个邻接点的每条边都被访问了一次，总体时间复杂度是O(N+E).

如果用邻接矩阵存储图，要扫描所有的N的顶点，总体时间复杂度是O(N^2).

源码: BFS-邻接矩阵存储 -O(N^2)

#include<stdio.h>
/*
图:BFS-邻接矩阵存储
*/
int main(void){
	return 0;
}
/* IsEdge(Graph, V, W)检查<V, W>是否图Graph中的一条边，即W是否V的邻接点。  */
/* 此函数根据图的不同类型要做不同的实现，关键取决于对不存在的边的表示方法。*/
/* 例如对有权图, 如果不存在的边被初始化为INFINITY, 则函数实现如下:         */
bool IsEdge(MGraph Graph, Vertex V, Vertex W){
	return Graph->G[V][W] < INFINITY ? true : false;
}

/* Visited[]为全局变量，已经初始化为false */
void BFS(MGraph Graph, Vertex S, void (*visit)(Vertex)){
	/* 以S为出发点对邻接矩阵存储的图Graph进行BFS搜索 */
	Queue Q;
	Vertex V, W;
	/* 创建空队列, MaxSize为外部定义的常数 */
	Q = CreateQueue(MaxSize);
	/* 访问顶点S：此处可根据具体访问需要改写 */
	Visit(S);
	/* 标记S已访问 */
	Visited[S] = true;
	/* S入队列 */
	AddQ(Q, S);
	while(!IsEmpty(Q)){
		/* 弹出V */
		V = Delete(Q);
		/* 对图中的每个顶点W */
		for(W = 0; W < Graph->Nv; W++){
			/* 若W是V的邻接点并且未访问过 */
			if(!Visited[W] && IsEdge(Graph, V, W)){
				/* 访问顶点W */
				Visit(W);
				/* 标记W已访问 */
				Visited[W] = true;
				/* W入队列 */
				AddQ(Q, W);
			}
		}
	}

}

6.2.3为什么需要两种遍历

迷宫，左上角入口，绿色出口，白色格子能走通，黑色各自走不通。

图的结点:能从一个白格子直接走到下一个白格子，那么这两个顶点是有边的，当然，在访问任一顶点相邻的这些邻接点时，得规定一个顺序。

下述规定了一个不太聪明的顺序，每次都从它的最上方的格子开始考虑，顺时针的去考虑其周边的8个格子，哪些是能走通的。

========DFS方法

第1步，往右边走，走到这个白格子，递归调用DFS。

继续走。

发现走错了，但是不知道。

继续走，发现进死胡同了。

只要原路返回，找到下一个能走的路。

走着走着就走差了。

用DFS的话，最终要访问这么多遍格子才能找到出口。

========BFS方法

入口结点先入队列，弹出来以后把它相邻的所有白格子都入队，以此类推。

这是一圈圈的往外搜索的。

用BFS的话，最终要访问这么多遍格子才能找到出口。

6.2.4图不连通怎么办

图的所有遍历方法:从一个结点出发，沿着某一条边往下走，意味着它访问过的所有的结点都是互相之间有直接或间接的方式去联通的。

如果有另外一个完全不挨着的结点怎么办？

如果DFS或BFS遍历，肯定会丢掉一些孤立的结点，引发问题，图不连通怎么办？

无向图(无箭头)

连通:从V触发，沿着图中已经有的边，一个顶点一个顶点的走，最后能走到W，这样，V到W之间有一条路径，这样，路径的长度就是路径的边数。

路径:V到W之间经过的顶点，如果有两个顶点是相同的，那么 不是简单路径 。

回路:从V到V1，从V1到V2，返回V1，形成一个环，叫回路。如果一个路径上有回路，那么就 不是简单路径 。

不连通的图:依然可以考虑它 部分的连通 ，这样的子图叫连通分量。

注意:无向图!

极大顶点数:这个连通分量一定包含的是可以让它连通的所有顶点包含在里面。

极大边数:这个连通分量一定包含的是包含的边数达到极大。

连通分量子图里面所有的顶点，相连的所有边都要包含在其中，这才组成一个完整的连通分量。

图G右边，这四个子图，一部分边和一部分顶点，这样构成一个子图。

第1个:

包含4个顶点，再加一个顶点进去就不连通了，这是所能连通的最大顶点数，它包含了跟这4个顶点相关的所有的边，没有一条边被漏掉。

第2个:

E和F同理。

第3个:

缺一条边。

第4个:

少一个顶点，即使加进1个顶点后是连通的。

有向图(有箭头)

注意:有向图！

强连通:可从V到W，也可W到V，这两条往返的路径不一定是同一条，但它们一定都存在，那么V和W强连通。

弱连通:不是强连通的，把这个图中的所有的边都抹掉之后，变成无向图之后就是连通的了，这样的图叫 弱连通 。

图G。

第1个:

强连通分量。

从A可以到B，B可以到A，任意两个结点之间都是这个关系，再加D就不是强连通了，因为有路径可以从A到D，但不能从D不能去任意结点。

第2个:

D自己是强连通分量。

源码

#include<stdio.h>
/*
图不连通怎么办?
*/
int main(void){
	return 0;
}

void DFS(Vertex V){
	visited[V] = true;
	/*
	每调用一次DFS(V),就把V所在的连通分量遍历一遍.
	BFS同理:遍历顺序不同,但遍历的顶点都是一样的.
	*/
	for(V 的每个邻接点 W){
		if(!visited[W]){
			DFS(W);
		}
	}
}

/*
每调用一次DFS,那么就访问了一个连通分量.
如果此图本身不连通,就意味着有好几个不同的连通分量.
此方法的作用:把好几个不同的连通分量都遍历.
*/
void ListComponents(Graph G){
	for(each V in G){
		/*
		对图里的每一个顶点V,如果还未被访问过,那么就从它开始调用DFS或BFS(二者一样),
		调用完以后,整个跟V相连的连通分量里所有的点都被访问过了,然后跳出来访问下一个没有被访问过的点.
		然后继续调用DFS或BFS(二者一样),就把另一个连通分量又访问了一遍.
		那么此访问就可以把一个不连通图里面所有的顶点都访问一遍.
		*/
		if(!visited[V]){
			/*or BFS(V)*/
			DFS(V);
		}
	}
}

6.3 应用实例 : 拯救007

以圆点为圆心跳跃，递归做DFS或BFS，半径跳跃，每一条鳄鱼对应一个连通集。

#include<stdio.h>
/*
图:应用实例-007
*/
int main(void){
	return 0;
}
/*
DFS算法
*/
void DFS(Vertex V){
	visited[V] = true;
	for(V 的每个邻接点 W){
		if(!visited[W]){
			DFS(W);
		}
	}
}
int DFS(Vertex V){
	visited[V] = true;
	if(IsSafe(V)){
		answer = YES;
	}else{
		for(each W in G){
			if(!visited[W] && Jump(V, W)){
				answer = DFS(W);
				if(answer == YES){
					break;
				}
			}
		}
	}
	return answer;
}
/*
总体算法
*/
void ListComponents(Graph G){
	for(each V in G){
		if(!visited[V]){
			DFS(V);
		}
	}
}
void Save007(Graph G){
	for(each V in G){
		if(!visited[V] && FirstJump(V)){
			answer = DFS(V);
			if(answer == YES){
				break;
			}
		}
	}
	if(answer == YES){
		output("YES");
	}else{
		output("NO");
	}
}

6.2.5应用实例:六度空间

当年条件有限，提出此理论的人只能做了非常有限的实验，可以看看这个理论在多大程度上是合理的。

广度优先搜索:

第1圈人:直接认识的、

第2圈人:其朋友直接认识而他不认识、

第3圈人:等等。

并不是为了搜索而搜索，不需要多少人满足条件，而是需要累计访问的结点数。

也不需要一直遍历所有的结点，这里验证六度空间，仅计算6层以内的结点数即可。

难点在于:处理层数问题。

六度空间问题的解决方案:对图里的每一个结点进行一次广度优先搜索。

方法一

#include<stdio.h>
/*
图:应用实例-六度空间
*/
int main(void){
	return 0;
}
/*
六度空间
*/
void SDS(){
	for(each V in G){
		count = BFS(V);
		/*
		在6步以内访问到的结点数占人群总数的百分比.
		*/
		Output(count/N);
	}
}
/*
最原始的BFS模板
*/
int BFS(Vertex V){
	visited[V] = true;
	/*
	累计访问的结点数
	*/
	count = 1;
	Enqueue(V, Q);
	while(!IsEmpty(Q)){
		V = Dequeue(Q);
		for(V 的每个邻接点 W){
			if(!visited[W]){
				visited[W] = true;
				/*
				如何记录层数?
				教材中在此之前给每个结点加了属性level,+1后再执行Enqueue,到第6层就不再往下做了.
				图中的每个结点都多加了整数属性level,多占空间,是O(n)数量级的,并不是很好的方法.
				*/
				Enqueue(W, Q);
				count++;
			}
		}
	}
	return count;
}

方法二(优化)

从中心顶点1开始，层序遍历顺序是234567。

然后从顶点2开始，层序遍历顺序是89到19。

level最初指顶点1的level,因为顶点1是不算的,所以顶点1的level是0.

last的初始值为顶点1.

层序遍历进入while，把顶点1的直接相连的邻接点一个个压入队列中，最后一个进队列的是7，把last=7。

tail应该指向下一层进入队列的最后一个结点，在每一个V的邻接点W进队列的时候都让tail指向W，tail一开始指向8>指向9>指向10>指向11>指向12>最后指向19。

如何知道19是最后一个呢？

当前弹出的V是等于前一步的last，tail指向的结点7一定是下一层的最后一个结点19。

当前弹出的V是等于前一步的last，level++，last=tail，又往外推了一层。

#include<stdio.h>
/*
图:应用实例-六度空间优化
*/
int main(void){
	return 0;
}
/*
六度空间
*/
void SDS(){
	for(each V in G){
		count = BFS(V);
		/*
		在6步以内访问到的结点数占人群总数的百分比.
		*/
		Output(count/N);
	}
}
/*
BFS模板优化
*/
int BFS(Vertex V){
	visited[V] = true;
	/*
	累计访问的结点数
	*/
	count = 1;
	/*
	记录当前顶点所在的层数.
	level最初指顶点1的level,因为顶点1是不算的,所以顶点1的level是0.
	*/
	level = 0;
	/*
	当前层访问的最后一个结点.
	last的初始值为顶点1.
	*/
	last = V;
	Enqueue(V, Q);
	/*
	层序遍历进入while,把顶点1的直接相连的邻接点一个个压入队列中,最后一个进队列的是7,把last=7.
	*/
	while(!IsEmpty(Q)){
		V = Dequeue(Q);
		for(V 的每个邻接点 W){
			if(!visited[W]){
				visited[W] = true;
				Enqueue(W, Q);
				count++;
				/*
				tail应该指向下一层进入队列的最后一个结点,在每一个V的邻接点W进队列的时候都让tail指向W,
				tail一开始指向8>指向9>指向10>指向11>指向12>最后指向19.
				*/
				tail = W;
			}
		}
		/*
		如何知道19是最后一个呢?
		当前弹出的V是等于前一步的last,tail指向的结点7一定是下一层的最后一个结点19.
		当前弹出的V是等于前一步的last,level++,last=tail,又往外推了一层.
		*/
		if(V == last){
			level++;
			last = tail;
		}
		if(level == 6){
			break;
		}
	}
	return count;
}