数据结构学习小记4（图4之图的遍历）
图的遍历和树的遍历类似，也是从图中的某一顶点出发按照某种方法对图中所有顶点访问且仅仅访问一次，图的遍历算法是求解图的连通性问题、拓扑排序和关键路径等算法的基础。
根据路径的方向，通常有两条遍历图的路径：深度优先搜索和广度优先搜索。它们对无向图和有向图都适用。
深度优先搜索：
深度优先搜索（Depth First Search,DFS,类似于树的先序遍历，是树的先序遍历的推广）过程：
（1）找图中某个顶点v出发，访问v
（2）找出刚访问过的顶点的第一个未被访问的邻接点，访问该顶点。以该顶点为新顶点，重复此步骤，直到刚访问过的顶点没有未被访问过的邻接点为止。
（3）返回前一个访问过的且仍有未被访问的邻接点的顶点，找出该顶点的下一个未被访问的邻接点，访问该顶点。
（4）重复步骤（2）和（3）。
例如此图，DFS的顺序为：1->2->3->5->4(回溯到点4）（还有其他的遍历路径）
2.算法实现
【算法步骤】
（1）从图中某个顶点v出发，访问v,并置visited[v]为true
（2）依次检查v的所有邻接点w,若visited[w]的值为false,再从w出发进行递归遍历，直到图中所有的顶点都被访问过。（visited[]数组用于标记区分顶点是否已被访问，初值置为false,一旦某个顶点被访问，则其相应的分量置为true）
【算法描述】
DFS遍历连通图(大体的算法，后续算法会用邻接矩阵和邻接表实现）
bool visited[MVNum]; //其初值为false
void DFS(Graph G,int v)
{//从第v个顶点出发递归
cout<<v;
visited[v]=true; //顶点被访问，则其相应的分量置为true
for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)）
//FirstAdjVex(G,v)表示v的第一个邻接点
//NextAdjVex(G,v,w)表示v相对于w的下一个邻接点，w≥ 0表示存在邻接点
//以上两个函数如果图的存储结构不同，这俩的实现方法也不同，时间耗费也不同，后续的算法会用邻接矩阵和邻接表具体实现遍历过程
if(!visited[w]) DFS(G,w);
}
DFS遍历非连通图
void DFSTraverse(Graph G)
{for(v=0;v<G.vexnum;++v)
visited[v]=false;
for(v=0;v<G.vexnum;++v)
if(!visited[v]) DFS(G,v);//调用DFS算法
}
用邻接矩阵表示图的DFS
void DFS_AM(AMGraph G,int v)
{cout<<v;
visited[v]=true;//置访问过的标志数组相应分量值为true
for(w=0;w<G.vexnum;w++)//依次检查邻接矩阵v所在的行
if((G.arcs[v][w]!=0)&&（!visited[w]）) DFS_AM(G,M);
//G.arcs[v][w]!=0表示w是v的邻接点，如果w未访问，则递归调用DFS_AM
}
用邻接表表示图的DFS
void DFS_AL(ALGraph G,int v)
{
cout<<v;
visited[v]=true;//置访问过的标志数组相应分量值为true
p=G.vertices[v].firstarc;//p指向v的边链表的第一个边结点
while(p!=NULL)
{
w=p->adjvex;
if(!visited[w]) DFS_AL(G,w);
p=p->nextarc;
}
}
【算法分析】
在分析以上算法，在遍历图时，对图中每个顶点至多调用一次DFS函数，因为一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。因此，遍历图的过程实质上就是对每个顶点查找其邻接点的过程，其耗费的时间取决于所采用的存储结构。
当用邻接矩阵表示图时，查找每个顶点的邻接点的时间复杂度为O(n^2).(n为图中顶点数）
当用邻接表做图的存储结构时，查找邻接点的时间复杂度为O(e),其中e为图中的 边数，故当以邻接表做存储结构时，DFS遍历图的时间复杂度为O(n+e).
广度优先搜索遍历的过程
广度优先搜索(Breadth First Search,BFS)遍历类似于树的层次遍历过程。
过程：
（1）从图中某个顶点v出发，访问v
（2）依次访问v的各个未曾访问过的邻接点
（3）分别从这些邻接点出发依次访问他们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问。重复步骤(3)，直至图中所有已被访问的顶点的邻接点都被访问到。
BFS遍历的顺序为：1->2->4->3->5
BFS算法实现
【算法步骤】
（1）从图中某个顶点v出发，访问v, 并置visited[v]的值为true,然后将v进队
（2）只要队列不为空，则重复下述操作：
队头顶点u出队
依次检查u的所有邻接点w,如果visited[w]的值为false,则访问w,并置visited[w]的值为true,然后将w进队
【算法描述】
BFS遍历连通图
void BFS(Graph G,int v)
{
cout<<v;
visited[w]=true;
InitQueue(Q);//辅助队列Q初始化，置空
EnQueue(Q，v);//v进队
while(!QueueEmpty(Q))//队列非空
{
DeQueue(Q,u);
for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)）
//FirstAdjVex(G,v)表示v的第一个邻接点
//NextAdjVex(G,v,w)表示v相对于w的下一个邻接点，w≥ 0表示存在邻接点
//以上两个函数如果图的存储结构不同，这俩的实现方法也不同，时间耗费也不同，后续的算法会用邻接矩阵和邻接表具体实现遍历过程
if(!visited[w])
{
cout<<v;
visited[w]=true;
EnQueue(Q,w);//v进队
}
}
}
对于非连通图，从另一个未被访问的顶点作为起始点，重复以上过程
【算法分析】
当用邻接矩阵表示图时，查找每个顶点的邻接点的时间复杂度为O(n^2).(n为图中顶点数）
当用邻接表做图的存储结构时，查找邻接点的时间复杂度为O(e),其中e为图中的 边数，故当以邻接表做存储结构时，BFS遍历图的时间复杂度为O(n+e),和DFS相同。
两种遍历方式的不同之处仅仅在于对顶点访问的顺序不同。
