- 概念
- 遍历定义
- 遍历实质
- 避免重复访问
- 深度优先遍历
- 遍历方法
- 深度优先搜索遍历连通图
- 深度优先搜索遍历非连通图
- 邻接矩阵表示的无向图深度遍历实现
- 采用邻接表表示图的深度优先搜索遍历
- DFS算法效率分析
- 广度优先搜索（Breadth First Search, BFS）
- 遍历方法
- 广度优先搜索遍历连通图
- BFS算法效率分析
- DFS与BFS算法效率比较
从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点， 且使每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算。遍历实质
找每个顶点的邻接点的过程。避免重复访问
图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。
怎样避免重复访问？
解决思路：设置辅助数组visited[n]，用来标记每个被访问过的顶点。
- 初始状态visited[i]为0；
- 顶点 i 被访问，改visited[i]为1，防止被多次访问。
- 在访问图中某一起始顶点v后，由v出发，访问它的任一邻接顶点w1；
- 再从w1出发，访问与w1邻接但还未访问过的顶点w1；
- 然后再从w2出发，进行类似的访问，…
- 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点u为止。
- 接着，退回一步，退到前一次刚访问过的顶点，看是否还有其他没有被访问的邻接顶点。
如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；
如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过位置。
注：连通图的深度优先遍历类似于树的先根遍历。
① 从图中某个顶点 v 出发， 访问 v, 并置 visited[v]的值为 true。
② 依次检查 v 的所有邻接点 w, 如果 visited[w]的值为 false, 再从 w 出发进行递归遍历，直到图中所有顶点都被访问过。
bool visited [MVNum]; // 访问标志数组， 其初值为 "false"
void DFS(Graph G,int v)
{ // 从第 v 个顶点出发递归地深度优先遍历图G
cout<=O;w=NextAdjVex(G,v,w))
// 依次检查 v 的所有邻接点 w , FirstAdjVex (G, v)表示 v 的第一个邻接点
// NextAdjVex(G,v,w)表示 v 相对千 w 的下一个邻接点， w≥0表示存在邻接点
if(!visited[w]) DFS(G, w); // 对 v 的尚未访问的邻接顶点 w 递归调用 DFS
}
深度优先搜索遍历非连通图
void DFSTraverse(Graph G)
{ //对非连通图G做深度优先遍历
for(v=O;v
邻接矩阵表示的无向图深度遍历实现
// 采用邻接矩阵表示图的深度优先搜索遍历
void DFS_AM(AMGraph G,int v)
{ // 图G为邻接矩阵类型，从第v个顶点出发深度优先搜索遍历图G
cout<
采用邻接表表示图的深度优先搜索遍历
void DFS_AL (ALGraph G,int v)
{ // 图G为邻接表类型， 从第v个顶点出发深度优先搜索遍历图G
cout<
w=p->adjvex; // 表示w是v的邻接点
if(!visited[w]) DFS(G,w); // 如果w未访问， 则递归调用DFS
p=p->nextarc; // p指向下一个边结点
}
}
DFS算法效率分析
- 用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，时间复杂度为O(n2)。
- 用邻接表来表示图，虽然有2e个表结点，但只需扫描e个结点即可完成遍历，加上访问n个头结点的时间，时间复杂度为O(n+e)。
结论：
- 稠密图适于在邻接矩阵上进行深度遍历；
- 稀疏图适于在邻接表上进行深度遍历。
广度优先搜索（Breadth First Search, BFS）
遍历方法
从图的某一结点出发，首先依次访问该结点的所有邻接结点Vi1，Vi2，…，Vin再按这些顶点被访问的先后次序依次访问与它们相邻接的所有未被访问的顶点。
重复此过程，直至所有顶点均被访问为止。
广度优先搜索遍历连通图
算法步骤：
（1）从图中某个顶点 v 出发， 访问 v，并置 visited[v]的值为 true, 然后将 v 进队。
（2）只要队列不空， 则重复下述操作：
- 队头顶点 u 出队；
- 依次检查 u 的所有邻接点 w, 如果 visited[w]的值为 false, 则访问 w, 并置 visited[w]的值为 true, 然后将 w 进队。
void BFS{Graph G,int v)
{ // 按广度优先非递归遍历连通图G
count<
DeQueue(Q, u); // 队头元素出队并置为u
for(w=FirstAdjVex(G,u);w>=O;w=NextAdjVex(G,u,w))
// 依次检查u的所有邻接点w, FirstAdjVex(G,u)表示u的第一个邻接点
// NextAdjVex(G,u,w)表示u相对于w的下一个邻接点，w≥0表示存在邻接点
if(!visited[w]) // w为u的尚未访问的邻接顶点
{
cout<
BFS算法效率分析
- 如果使用邻接矩阵，则BFS对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（n个元素），总的时间代价为O(n2)。
- 用邻接表来表示图，虽然有2e个表结点，但只需扫描e个结点即可完成遍历，加上访问n个头结点的时间，时间复杂度为O(n+e)。
DFS与BFS算法效率比较
- 空间复杂度相同，都是O(n)（借用了堆栈或队列）；
- 时间复杂度只与存储结构（邻接矩阵或邻接表）有关，而与搜索路径无关。
