1
7.1 基本术语
7.2 存储结构
7.3 图的遍历
7.4 图的连通性
7.5 图的应用
第7章 图
2
7.3 图的遍历
遍历:从已给的连通图中某一顶点出发,沿着一些边,
访遍图中所有的顶点,且使每个顶点仅被访问一次,
就叫做图的遍历,它是图的基本运算。
遍历实质:找每个顶点的邻接点的过程。
图的特点:图中可能存在回路,且图的任一顶点都可能与
其它顶点相通,在访问完某个顶点之后可能会沿着某
些边又回到了曾经访问过的顶点。
解决思路:可设置一个辅助数组 visited [n ],用来标
记每个被访问过的顶点。它的初始状态为false,
在图的遍历过程中,一旦某一个顶点i被访问,就
立即改 visited [i]为true,防止它被重复访问。
怎样避免重复访问?
3
深度优先搜索和广度优先搜索图常用的遍历:
一、深度优先搜索( DFS ) Depth_First Search
基本思想:——类似于树的先根遍历过程。
1、连通图的深度优先搜索遍历
步骤:
• 访问起始点 v;
• 依次从v的未被访问的邻接点出发深度优先遍历
图直至图中所有和v有路径相通的顶点都被访问
到。
4
v1
v1
v2 v3
v8
v7v6v4 v5
DFS 结果:例1:
→ → → →
→ → →
v2 v4 v8
v5 v3 v6 v7
起点
应退回到V8,因为
V2已有标记
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
5
对于无向图,这个算法可以遍历到v顶点所在的连通
分量中的所有顶点,而与v顶点不在一个连通分量中的
所有顶点遍历不到;
对于有向图可以遍历到起始顶点v能够到达的所有顶
点。
若希望遍历到图中的所有顶点,就需要在上述深度
优先遍历算法的基础上,增加对每个顶点访问状态的
检测。
2、非连通图的深度优先搜索遍历
步骤:
• 访问起始点 v及图中所有和v有路径相通的顶点。
• 如果图中尚有顶点未被访问,则以该顶点为起始点,
进行深度优先搜索遍历。重复上述过程,直至所有
顶点都已被访问。
6
a b
c
h
d e
k
f
g
F F F F F F F F FT T T T T T T T T
a c h d k f e b g
a
c
h k
fed
b
g
访问标志:
访问次序:
例2:
0 1 2 3 4 5 6 7 8
8
1
2 3 4 5
6
7
0
7
void DFSTraverse(Graph G,
Status (*Visit)(int v)) {
// 对图 G 作深度优先遍历。
VisitFunc = Visit;
for (v=0; v
记录顶点访问顺序,将访问的
每个顶点入队,然后,再依次出队,出队时访问其邻
接点并将邻接点入队。
(2)如何避免重复访问某个顶点?
(1)在广度优先遍历中,要求先被访问的顶点其邻接点
也被优先访问,应采用何种方式记录顶点访问顺序?
答:创建一个一维数组visited[0..n-1](n是图中顶
点的数目),用来记录每个顶点是否已经被访问过。
(3)广度优先搜索有回退的情况吗?
12
答:广度优先搜索是一种分层的搜索过程,每向前走
一步可能访问一批顶点,不像深度优先搜索那样有回
退的情况。因此广度优先搜索不是一个递归的过程,
其算法也不是递归的。
void BFSTraverse(Graph G, Status (*Visit)(int v)){
for (v=0; v
题 的出发点: 为使生成树上边的权值之和达到
最小,则应使生成树中每一条边的权值尽可能地小。
克鲁斯卡尔算法的基本思想:
1
4
65
2 3
1
56
55
463
6
2
15
43 2
1
3
5
2 4
6
Kruskal算法的时间效率=O(elog2e)
第7章 图
7.3 图的遍历
一、深度优先搜索( DFS )
幻灯片编号 4
幻灯片编号 5
幻灯片编号 6
幻灯片编号 7
DFS 算法效率分析:
二、广度优先搜索( BFS )
幻灯片编号 10
幻灯片编号 11
幻灯片编号 12
幻灯片编号 13
BFS 算法效率分析:
幻灯片编号 15
例1 :画出下图的生成树。
例2:画出下图的生成森林(或极小连通子图)
幻灯片编号 18
幻灯片编号 19
2. 求无向网的最小生成树
幻灯片编号 21
幻灯片编号 22
幻灯片编号 23
幻灯片编号 24
幻灯片编号 25