图的遍历

遍历定义：

（遍历的实质：找到每个顶点的邻接点的过程）

图的遍历特点

解决重复遍历方法

图的遍历

1、深度优先遍历(DFS)

方法：

例子：

（连通图的深度优先遍历类似于树的先跟遍历，走不动再往回退）

思想思路  

（其中辅助数组visited[n]，一开始初始化为0，访问到就初始化为1。）

大致算法实现

void DFS(AMraph G, int v){  //图G为邻接矩阵类型
  cout << v;    //访问第v个顶点
  visited[v] = true;  //做标志
  for( w = 0; w < G.vexnum; w++)  //依次检查邻接矩阵v所在的行
  {
    if(G.arcs[v][w] != 0 && ! visited[w]) //如果w是v的邻接点，且w未被访问，则递归调用DFS
    DFS(G,w);
  }
}

简单分析代码实现过程：

0.以上图为例，首先以2为起点出发，在邻接表中找到2指向1和5，按顺序，首先先到1.

1. 对1做标志，然后继续寻找下一个，在邻接表中找到2为第一个，但是2已经做了标志，所以继续找，找到3.
2. 然后在3中找，首先是1，但是1已经做了标志，找其他的，找到了5.然后在5中开始寻找，但是5中全部都已经做了标志，什么也找不到，循环结束。
3. 递归回到上一级3,3接着剩下的循环找6，但是6没有连接，所以循环也结束，继续递归上一级1.
4. 1之前是循环找到了2，2完成了，所以到3,3也完成了，然后循环到4,4此时还没有做标志，所以进入4。
5. 4中在邻接表中找到1,1已经作了标志不行，然后找到了6,6可以，递归到6。
6. 但是在6的循环中，全部都不符合，所以循环结束，返回到4的循环。
7. 4的循环找的是6,6为最后一个，所以4的循环也结束了，递归返回1的循环。
8. 1上次循环到4，接着循环寻找，但是56都不符合条件，递归返回到起点2.
9. 而起点2开始循环到1，所以接着循环。但是其他的已经没有符合条件的，所以2的循环也结束，此时遍历完。

DFS算法效率分析（以无向图为例）

结论：

稠密图适用于邻接矩阵上进行深度遍历

稀疏图适用于在邻接表上进行深度遍历

2、广度优先遍历(BFS)

方法

例子（以连通图为例）

思想思路

（利用了一个队列对图进行广度优先算法的思路）

大致算法实现

按广度优先的非递归遍历连通图G

void BFS(Graph G,int v){  //按广度优先算法遍历（非递归）
  count << v;    //访问第v个顶点
  visited[v] = true;  
  InitQueue(Q);   //辅助队列Q初始化，置空
  EnQueue(Q,v);   //v进队
  while( !QueueEmpty(Q)){ //队列非空，就不断的将队列中的元素找到其其他的连接弧
  DeQueue(Q,u);  //队头元素出队并置为u
  //从第一个弧开始，不断的找下一条弧，再看下一条弧设计到的结点有无被访问
  for ( w = FirstAdjVex(G,u); w >= 0; w = NextAdjVex(G,u,w))
  {
    if( !visited[w] ){  //w为u的尚未访问的邻接顶点
    cout << w;    //表示出于w处
    visited[w] = true;  //如果没有做标志表示为走，做标志
    EnQueue(Q,w);  //w进队
    }
  }
  }
}

BFS算法效率分析

DFS与BFS算法效率比较

• 空间复杂度相同，都是O(n).(借用了堆栈或队列)
• 时间复杂度只与存储结构（邻接矩阵n2或邻接表n+e）有关,而与搜索路径无关。