学步园

所谓遍历,就是把图中的顶点访问且只访问一次。为了使每个顶点只访问一次，我们需要设置一个标志数组visited。

图的遍历有两种方法: 1-深度优先搜索; 2-广度优先搜索

1-深度优先搜索

  指按照深度方向搜索，它类似于数的先根遍历。

思路为:

a,从图中的某一顶点V0出发,先遍历V0.

b,找出刚访问过的顶点的第一个未访问过邻接顶点,然后访问该顶点。以该顶点为新的顶点,重复此步骤，直到刚访问过的顶点没有未被访问过的邻接顶点为止。

c,返回前一个访问过的且任有未被访问过的邻接点的顶点，找出该顶点的下一个未被访问过的邻接点，访问该顶点，然后执行步骤b。

如下图对应的深度优先遍历序列为:ABCFDGEHI

以下为邻接矩阵和邻接表对应的深度优先遍历方法:

#define MAX_VERTEX_NUM 20//最大支持的顶点个数
int visited[MAX_VERTEX_NUM];//访问标志数组

//邻接矩阵对应的深度优先遍历算法
void TraverseGraph(Graph g)
{
	for(int i=1;i<=g.vexnum;i++){
		visited[i] = 0;//设置0表示未访问
	}
	for(i=1;i<=g.vexnum;i++){//循环调用DepthFirstSearch(g,i);若图为联通图，该循环只执行一次
		if(!visited[i])
			DepthFirstSearch(g,i);
	}
}

/*邻接矩阵对应的DepthFirstSearch(g,i)函数*/
void DepthFristSearch(AdjMatrix g, int v0)
{
	visit();//具体的操作根据实际而定
	visited[v0]=1;//该顶点已访问
	for(int vj=0;vj<n;vj++){
		if(!visited[vj]&&g.arcs[v0][[vj].adj==1)
			DepthFirstSearch(g,vj);
	}
}

//邻接表对应的优先深度遍历算法
void DepthFirstSearch(AdjList g,int vo)
{
	visit(v0);//根据需要改变
	visited[v0]=1;
	p=g.vertex[v0].firstarc;
	while(p!=NULL){
		if(!visited[p->adjvex]){
			DepthFirstSearch(g,p->adjvex);
			p=p->nextarc;
		}
	}
}	

2-广度优先搜索
   思路:

a,从图中的某个顶点v0出发，首先遍历v0.

b,一次访问v0的各个未被访问的邻接顶点。

c,分别从这些邻接点出发，依次访问它们的各个未被访问的邻接点。

如上图的遍历序列为:ABDECGFHI

下面为广度优先遍历V0所在连通子图方法:

void BreadthFirstSearch(Graph g,int v0)
{
	visit(v0);//根据需要改变为具体操作
	visited[v0] = 1;
	InitQueue(&Q);//初始化空队列
	EnterQueue(&Q,v0);
	while(!Empty(Q)){
		DeleteQueue(&Q,&v);//队首元素出队
		w = FirstAdjvex(g,v);
		while(w!=-1){
			if(!visited[w]){
				visit(w);
				visited[w]=1;
				EnterQueue(&Q,w);
			}
			w=NextAdjVertex(g,v,w);
		}
	}
}