【数据结构】图的深度优先遍历
一.图的遍历
图的遍历需要解决的关键问题
1.在图中，如何选取遍历的起始顶点？
从编号小的顶点开始
- 在线性表中，数据元素在表中的编号就是元素在序列中的位置，因而其编号是唯一的。
- 在树中，将节点按层序编号，由于树具有层次性，因而其层序编号也是唯一的。
- 在图中，任何两个顶点之间都可能存在边，顶点时没有确定的先后次序的，所以，顶点的编号不唯一。
为了定义操作的方便，将图中的顶点安任意顺序排列起来，比如，按顶点的存储顺序。
2.从某个起始点可能到达不了所有其它顶点，怎么办？
多次调用从某顶点出发遍历图的算法
3.因图中可能存在回路，某些顶点可能会被重复访问，那么如何避免不会因回路而陷入死循环呢？
附设访问标志数组visited[n] （n为结点个数）
4.在图中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，如何选取下一个要访问的顶点呢？
- 深度优先遍历
- 广度优先遍历
二.深度优先遍历
1.基本思想
1）访问顶点v；
2）从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历；
3）重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。
2.伪代码
- 1.访问顶点v；visited[v]=1;
- 2.w=顶点v的第一个邻接点；
- 3.while（w存在）
- 3.1 if（w未被访问）从顶点w出发递归执行该算法；
- 3.2w=顶点v的下一个邻接点；
3.代码实现
3.1 邻接矩阵
template<class T>
void MGraph<T>::DFSTraverse(int v){bool visited[vertexNum]=false;//设置标志数组int w,i,count=0;cout<<vertex[v]<<endl;//访问顶点vvisited[v]=true;//标志数组置为true++count;//结点访问一次，计数器加一for(i=0;i<vertexNum;i++){if(arc[v][i]&&!visited[i]){//存在边且未被访问过w=i;//更新w的值DFSTraverse(w);//再次深度优先搜索w}if(count==vertexNum){//所有结点都被访问过，返回，减少执行次数return;}}}3.2 邻接表
template <class T>
void ALGraph<T>::DFSTraverse(int v){int w,i=0,count=0;bool visited[vertexNum]=false;struct ArcNode *p=adjList[v].firstEdge;cout<<adjList[v].vertex<<endl;//访问节点vvisited[v]=true;//标志数组置为true++count;if(count==vertexNum){return;}while(p){if(!visited[p->adjvex]){w=p->adjvex;DFSTraverse(w);}else{p=p->next;}}
}