图的遍历——深搜dfs（邻接矩阵）

• 深度优先搜索：从图的一个顶点开始，一直往下搜索，直到遇到已经访问过的顶点进行返回。（类似树的先根遍历）
  例如：
  深搜输出：A B D H E C F G
  

• 深搜算法：从顶点A出发，找A的邻接点B,再找B的邻接点，依次往下进行···直到到E的时候，E的邻接点是B,B已经访问过，所以进行访问E上一个邻接点的其他邻接点，所以需要一个标记该顶点是否被访问过。而且该过程明显是一个递归的过程。另外，如果是非连同图，还要再从另一个顶点开始，再进行该过程。

• 解决深搜算法的关键是如何求该点的邻接点。对于邻接矩阵，顶点的邻接矩阵就是该顶点所对应的那一列的为1的点。但是，要判断该点的邻接点是否访问过。

int FirstVxe(Graph G,int v){
	int j;
	for(j=0;j<G.vexnum;j++){
		if(G.arcs[v][j].adj==1&&visted[j]==false)
			return j;
	}
	if(j>=G.vexnum)
		return -1;
}

• 深搜代码

void dfsGraph(Graph G,int v){
	for(int i=0;i<G.vexnum;i++)
		visted[i]=false;
	for(v;v<G.vexnum;v++){//对于非连同图，在另找一个顶点进行深搜 
		if(visted[v]==false)
			dfs(G,v);
	}
}
void dfs(Graph G,int v){
	visted[v]=true;//是否访问标志 
	//vist(v);//访问v顶点 
	cout<<G.vex[v]<<" ";
	for(int w=FirstVxe(G,v);w>=0;w=FirstVxe(G,w)){//查找邻接点
		if(!visted[w])
			dfs(G,w);
	}
}

• 运行截屏：