图的遍历——深度优先（DFS）与广度优先（BFS）

图的遍历
每个顶点只被访问一次

深度优先

遍历原则：以连通分量为单位遍历

算法

void DFS(VLink G[], int v)
{
	int w;
	VIST(v);           //访问顶点v
	visted[v] = 1;    //做标记，表示v已被访问
	w = FIRSTADJ(G, v);        //求v的第一个邻接点的位置，若无，返回-1
	while( w!= -1){
		if (visited[w]==0)
			DFS(G,w);
			w=NEXTADJ(G,V) //求v的下一个邻接点的位置，若无，返回-1
	}
}
void TRAVEL_DFS(VLink G[], int visited[], int n;)
{
	int i;
	for(i = 0;i<n;i++){
		visited[i]=0；                //赋初值
	for(i = 0;i<n;i++){
		if(visited[i]==0)
			DFS(G, i);
	}	
	}
}

广度优先

遍历原则：先访问指定出发点，然后再依次访问该点未访问过的邻接点，然后再访问这些邻接点的未访问过的邻接点。
说明需要记录下访问的顺序，为此设置一个队列结构。

算法

void BFS(VLink G[], int v)
{
	int w;
	VISIT(v);
	visited[v]=1;
	ADDQ(Q, v);
	while(!EMPTY(Q)){
		v=DELQ(Q);
		w=FIRSTADJ(G,v);
		while(w!=-1){
			if(visited[w]==0){
				VIST(w);
				ADDQ(Q,w);
				visited[w]=1;
			}
			w=NEXTADJ(G,v);
		}
	}
}

void TRAVEL_BFS(VLink G[], int visited[], int n)
{
	int i;
	for(i = 0;i<n;i++)
		visited[i]=0;
	for(i  = 0;i<n;i++){
		if(visited[i]==0)
			BFS(G,i);
	}
}