文档介绍：图算法
从图中某个顶点V0 出发,访问此顶点,然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图,直至图中所有和V0有路径相通的顶点都被访问到。
一、深度优先搜索遍历图
连通图的深度优先搜索遍历
V1
V2
V4
V5
V3
V7
V6
V8
例
深度遍历:V1 V2 V4 V8 V5 V6 V3 V7
SG1
SG2
SG3
W1、W2和W3 均为 V 的邻接点,SG1、SG2 和 SG3 分别为含顶点W1、W2和W3 的子图。
访问顶点 V ;
for (W1、W2、W3 )
若该邻接点W未被访问,
则从它出发进行深度优先搜索遍历。
V
w1
w3
w2
从上页的图解可见:
1. 从深度优先搜索遍历连通图的过程类似于树的先根遍历;
解决的办法是:为每个顶点设立一个“访问标志 visited[w]”;
2. 如何判别V的邻接点是否被访问?
6
DFS算法框架:
递归写法:(较常用)
DFS(NODE N)
{
FOR N的每一个邻接结点V
{
IF(V还没有被搜索过)
DFS(V);
}
}
void DFS(Graph G, int v) {
// 从顶点v出发,深度优先搜索遍历连通图 G
visited[v] = TRUE; VisitFunc(v);
for(w=FirstAdjVex(G, v);
w!=0; w=NextAdjVex(G,v,w))
if (!visited[w]) DFS(G, w);
// 对v的尚未访问的邻接顶点w
// 递归调用DFS
} // DFS
二、广度优先搜索遍历图
V
w1
w8
w3
w7
w6
w2
w5
w4
对连通图,从起始点V到其余各顶点必定存在路径。
其中,V->w1, V->w2, V->w8
的路径长度为1;
V->w7, V->w3, V->w5
的路径长度为2;
V->w6, V->w4
的路径长度为3。
w1
V
w2
w7
w6
w3
w8
w5
w4
从图中的某个顶点V0出发,并在访问此顶点之后依次访问V0的所有未被访问过的邻接点,之后按这些顶点被访问的先后次序依次访问它们的邻接点,直至图中所有和V0有路径相通的顶点都被访问到。
若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。
V1
V2
V4
V5
V3
V7
V6
V8
例
广度遍历:V1 V2 V3 V4 V5 V6 V7 V8