图的图的遍历
常见的图遍历方式有两种：深度优先遍历和广度优先遍历，这两种遍历方式对有向图和无向图均适用。 深度优先遍历的思想类似于树的先序遍历。其遍历过程可以描述为：从图中某个顶点v出发，访问该顶点，然后依次从v的未被访问的邻接点出发继续深度优先遍历图中的其余顶点，直至图中所有与v有路径相通的顶点都被访问完为止。
深度优先遍历算法实现：
为了便于在算法中区分顶点是否已被访问过，需要创建一个一维数组visited[0..n-1]（n是图中顶点的数目），用来设置访问标志，其初始值visited（0≤i≤n-1）为"0"，表示邻接表中下标值为i的顶点没有被访问过，一旦该顶点被访问，将visited置成"1"。
int visited[0..n-1]={0,0,...0};
void DFS(AdjList adj,int v)
{//v是遍历起始点的在邻接表中的下标值，其下标从0开始
visited[v]=1; visited(adj[v].elem);
for (w=adj[v].firstedge;w;w=w->next)
if (!visited[w->adjvex]) DFS(adj,w->adjvex);
}
对于无向图，这个算法可以遍历到v顶点所在的连通分量中的所有顶点，而与v顶点不在一个连通分量中的所有顶点遍历不到；而对于有向图可以遍历到起始顶点v能够到达的所有顶点。若希望遍历到图中的所有顶点，就需要在上述深度优先遍历算法的基础上，增加对每个顶点访问状态的检测： intvisited[0..n-1]={0,0,...0};voidDFSTraverse(AdjListadj){for(v=0;v<n;v++)if(!visited[v])DFS(adj,v);} 对图的广度优先遍历方法描述为：从图中某个顶点v出发，在访问该顶点v之后，依次访问v的所有未被访问过的邻接点，然后再访问每个邻接点的邻接点，且访问顺序应保持先被访问的顶点其邻接点也优先被访问，直到图中的所有顶点都被访问为止。下面是对一个无向图进行广度优先遍历的过程。
下面我们讨论一下实现广度优先遍历算法需要考虑的几个问题：
（1）在广度优先遍历中，要求先被访问的顶点其邻接点也被优先访问，因此，必须对每个顶点的访问顺序进行记录，以便后面按此顺序访问各顶点的邻接点。应利用一个队列结构记录顶点访问顺序，就可以利用队列结构的操作特点，将访问的每个顶点入队，然后，再依次出队，并访问它们的邻接点；
（2）在广度优先遍历过程中同深度优先遍历一样，为了避免重复访问某个顶点，也需要创建一个一维数组visited[0..n-1]（n是图中顶点的数目），用来记录每个顶点是否已经被访问过。
int visited[0..n-1]={0,0,...0};
void BFS(AdjList adj,int v)
{//v是遍历起始点在邻接表中的下标，邻接表中下标从0开始
InitQueue(Q); //Q是队列
visited[v]=1; visite(adj[v].elem); EnQueue(Q,v);
while (!QueueEmpty(Q)) {
DeQueue(Q,v);
for (w=adj[v].firstedge;w;w=w->next)
if (!visited[w->adjvex]) {
visited[w->adjvex]=1;
visite(adj[w->adjvex].elem);
EnQueue(Q,w->adjvex); }
}
}
