2009-7-30 软件基础教案（第八章 图）
第八章 图图的基本概念图的存储结构图的遍历最小生成树的概念 (简单介绍 )
最小路径的概念 (简单介绍 )
Chapter 8 Graph
2009-7-30 软件基础教案（第八章 图）
8.1 图的基本概念
1.图定义 图是由结点集合 (vertex)及结点间的关系集合组成的一种数据结构,
Graph＝ ( V,E )
其中 V = { x | x? 某个数据元素集合 }
是结点的有穷非空集合；
E = {(x,y) | x,y? V }
或 E = {<x,y> | x,y? V && Path (x,y)}
是结点之间关系的有穷集合，也叫做边 (edge)集合。
Path (x,y)表示从 x 到 y 的一条单向通路,它是有方向的。
2009-7-30 软件基础教案（第八章 图）
有向图与无向图 在有向图中，结点对 <x,y>是有序的。在无向图中，结点对 (x,y)是无序的。
子图 设有两个图 G＝ (V,E) 和 G’＝ (V’,E’)。若 V’?
V 且 E’?E,则称 图 G’ 是 图 G 的子图。
邻接结点 如果 (u,v) 是 E(G) 中的一条边，则称 u 与 v
互为邻接结点 。
2009-7-30 软件基础教案（第八章 图）
无 向图 G2
A B
C D
E
A B
D
E
A A B
C D
A B
C D
E
无向图 G2的子图
A B
C D
A A
C D
A
C
A B
C D
有向图 G1的子图有向图 G1
有向图无向图及其子图：
2009-7-30 软件基础教案（第八章 图）
权 某些图的边具有与它相关的数,称之为权。这种带权图叫做 网络 。 (书 p199 图 8-3)
完全图 若有 n 个顶点的无向图有 n(n-1)/2 条边,
则此图为完全无向图。 有 n 个顶点的有向图有 n(n-
1) 条边,则此图为完全有向图。
结点的度 一个顶点 v的度是与它相关联的边的条数。
记作 TD(v)。 在有向图中,顶点的度等于该顶点的入度
(ID(v))与出度 (OD(v))之和。 TD(v)=ID(v)+OD(v)
2009-7-30 软件基础教案（第八章 图）
例子 1,1 6
2
54
3
a
b c
d
e f
TD(1)=3 TD(2)=3
TD(3)=3 TD(4)=2
TD(5)=2 TD(6)=1
ID(a)=1 OD(a)=2 TD(a)=3
ID(b)=1 OD(b)=2 TD(b)=3
ID(c)=2 OD(c)=0 TD(c)=2
ID(d)=1 OD(d)=1 TD(d)=2
ID(e)=0 OD(e)=1 TD(e)=1
ID(f)=1 OD(f)=0 TD(f)=1
2009-7-30 软件基础教案（第八章 图）
1
2
3
5
6
8
74
10
7
9
6
6
7
12
315
16
30
45
A
B
D
C
E
60
35
80
40
75
网 络例子 2：
2009-7-30 软件基础教案（第八章 图）
路径 在图 G＝ (V,E) 中,若从顶点 vi 出发,沿一些边经过一些结点 vp1,vp2,…,vpm，到达顶点 vj。则称顶点序列 ( vi vp1 vp2,.,vpm vj ) 为从顶点 vi 到顶点
vj 的路径。 它经过的边 (vi,vp1),(vp1,vp2),...,(vpm,
vj)应是属于 E的边。
路径长度
非带权图的路径长度是指此路径上边的条数。
带权图的路径长度是指路径上各边的权之和。
2009-7-30 软件基础教案（第八章 图）
简单路径 若路径上各顶点 v1,v2,...,vm 均不互相重复,则称这样的路径为简单路径。
回路 若路径上第一个顶点 v1 与最后一个顶点 vm 重合,则称这样的路径为回路或环。
2009-7-30 软件基础教案（第八章 图）
连通图 在无向图中,若从顶点 v1到顶点 v2有路径,则称顶点 v1与 v2是连通的。如果图中任意一对顶点都是连通的,则称此图是 连通图 。
强连通图 在有向图中,若对于每一对顶点 vi和 vj,都存在一条从 vi到 vj和从 vj到 vi的路径,则称此图是强连通图。 (书 p198 图 8-2 G4)
2009-7-30 软件基础教案（第八章 图）
1
3 4 5
2 1
3 4 5
2
V={1,2,3,4,5}
E={(1,2),(1,3),(1,4),
(2,4),(4,5)}
V={1,2,3,4,5}
E={<1,2>,<1,3>,<3,1>,
<2,4>,<4,1>,<4,5>}
无向图 有向图连通图非连通图
1
3 4 5
2 6
7
H1连通分量 H2连通分量例子 3：
2009-7-30 软件基础教案（第八章 图）
1
3
2
强连通图 非强连通图
51
3 4
2
1
3 4
2
5
强连通分量
H1
强连通分量
H2
例子 4：
2009-7-30 软件基础教案（第八章 图）
生成树 一个连通图的生成树是它的极小连通子图，
在 n个顶点的情形下，有 n-1条边。但有向图则可能得到它的由若干有向树组成的生成森林。
本章不予讨论的图
2009-7-30 软件基础教案（第八章 图）
8.2 图的存储结构图的四种常用的存储形式：
邻接矩阵和加权邻接矩阵（ labeled adjacency matrix）
邻接表
十字链表 (不讲 )
邻接多重表（不讲）
一、邻接矩阵 （静态存储方法）
先决条件,若图 G=（ V,E）有确定个数的顶点！
存储方法,顶点?一维数组 (V表示 )
邻接关系?矩阵 (A表示 )
2009-7-30 软件基础教案（第八章 图）
设图 A = (V,E)是一个有 n 个顶点的图，则图的邻接矩阵是一个二维数组 A.edge[n][n]，定义：
,
),(,,
]][[,
否则或者如果
0
><1
A
EjiEji
jiE d g e
无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。
2009-7-30 软件基础教案（第八章 图）
1).无权值的无向图的邻接矩阵设无向图具有 n 个结点，则用 n 行 n 列的布尔矩阵 A 表示该无向图；
并且 A[i,j] = 1,如果 i 至 j 有一条无向边； A[I,j] = 0如果 i 至 j 没有一条无向边
。
注意,A[i,i] = 0。 i结点的度,i行或 i列之和。上三角矩阵或下三角矩阵 存储 。
表示成右图矩阵
A B
C D
E
A
B
C
D
E
0 1 1 0 0
1 0 0 1 1
1 0 0 0 1
0 1 0 0 1
0 1 1 1 0
A B C D E
2009-7-30 软件基础教案（第八章 图）
A B
C D
2).无权值的有向图的邻接矩阵设有向图具有 n 个结点，则用 n 行 n 列的布尔矩阵 A 表示该有向图；
如果 i 至 j 有一条有向边,A[i,j] = 1 ；如果 i 至 j 没有一条有向边
,A[i,j] = 0.
注意,A[i,i] = 0。 出度,i行之和。入度,j列之和。
表示成右图矩阵
0 1 1 0
0 0 0 0
0 0 0 1
1 0 0 0
A B C D
A
B
C
D
2009-7-30 软件基础教案（第八章 图）
3).网络的邻接矩阵本书使用该定义
),(,),(
]][[.
ji
ji
EjiEjijijiW
jiEdge
==
=!
<!
0
=A
对角线但是否则,
或且如>?
),(,),(]][[.
ji
EjiEjijiWjiEdge
=!
<=A
但是否则,
或>
0
1 2
3
A.Edge=
0
1
3
2
4
5
6
7
A.Edge=
V[]=[0,1,2,3]
V[]=[0,1,2,3,4,5,6,7]
例 1：
例 2：
A B C D E
A
B
C
D
E?
0010050
0004070
1000080
0400020
507080200
B
E
D
C
B
A
V
B
E
D
C
A
20
80
10
70
40
50
例 3：
2009-7-30 软件基础教案（第八章 图）
3.在无向图中,统计第 i 行 (列 ) 1 的个数可得顶点 i 的度 。
4.在有向图中,统计第 i 行 1 的个数可得顶点 i 的出度，统计第 j 列 1 的个数可得顶点 j 的入度。
5.属于静态存储方法。不易扩充。
6.与顶点个数有关，与边（弧）无关。会出现稀疏矩阵。
1.无向图的邻接矩阵是对称的，
2.有向图的邻接矩阵可能是不对称的。
邻接矩阵的特点：
2009-7-30 软件基础教案（第八章 图）
二,邻接表 (Adjacency List)－ （动态存储方法）
1）无向图的邻接表把同一个顶点发出的边链接在同一个边链表中，链表的每一个结点代表一条边，叫做边结点，结点中保存有与该边相关联的另一顶点的顶点下标 dest 和指向同一链表中下一个边结点的指针 link。
0
1
2
3
2009-7-30 软件基础教案（第八章 图）
2)有向图的邻接表和逆邻接表
在有向图的邻接表中，第 i 个边链表链接的边都是 顶点 i 发出的边 。也叫做 出边表 。
在有向图的逆邻接表中，第 i 个边链表链接的边都是 进入顶点 i 的边 。也叫做 入边表 。
2009-7-30 软件基础教案（第八章 图）
带权图的边结点中保存该边上的权值 cost。
顶点 i 的边链表的表头指针 adj 在顶点表的下标为 i
的顶点记录中，该记录还保存了该顶点的其它信息。
在邻接表的边链表中,各个边结点的链入顺序任意，
视边结点输入次序而定。
设图中有 n 个顶点,e 条边，则 用邻接表表示无向图时,需要 n 个顶点结点,2e 个边结点；用 邻接表表示有向图时,若不考虑逆邻接表，只需 n 个顶点结点，
e 个边结点。
2009-7-30 软件基础教案（第八章 图）
3)网络的邻接表 B
E
D
C
A
20
80
10
70
40
50
A
B
C
D
E
0
1
2
3
4
1 20
0 20
4 ^503 702 80
0 80
0 70
3 ^40
2 ^10
1 ^40
4 ^10
0 50
2009-7-30 软件基础教案（第八章 图）
8.3 图的遍历图的两种常见的遍历形式：
深度优先搜索
广度优先搜索遍历的定义,从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做 图的遍历 ( Graph Traversal )。
2009-7-30 软件基础教案（第八章 图）
遍历 的方法,
DFS 在访问图中某一起始顶点 v 后，由 v 出发，访问它的任一邻接顶点 w1；再从 w1 出发，访问与 w1邻 接但还没有访问过的顶点 w2；然后再从 w2 出发，进行类似的访问,… 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。
1、深度优先搜索 DFS ( Depth First Search )
2009-7-30 软件基础教案（第八章 图）
深度优先搜索的示例 1
深度优先搜索过程 深度优先生成树
深度优先搜索的示例 2
有向图的实例：为了说明问题，邻接结点的访问次序以序号为准。序号小的先访问。如：结点 5 的邻接结点有两个 6,7，
则先访问结点 6，再访问结点 7。
2009-7-30 软件基础教案（第八章 图）
5
6
7
2
4
1
3
5
6 7
2
3
1
4
·
·
·
· ·
·
·
从结点 出发的搜索序列：
5,6,2,3,1,4,7
适用的数据结构,栈
5
1
2
43
·
·
· ·
从结点 出发的搜索序列：
1,2,3,4没有搜索到所有的结点，必须另选图中未访问过的结点，
继续进行搜索。
1
2009-7-30 软件基础教案（第八章 图）
2.广度优先搜索 BFS ( Breadth First Search )
广度优先搜索的示例 1
广度优先搜索过程 广度优先生成树
2009-7-30 软件基础教案（第八章 图）
使用广度优先搜索在访问了起始顶点 v 之后，由 v 出发，依次访问 v 的各个未曾被访问过的邻接顶点 w1,
w2,…,wt，然后再顺序访问 w1,w2,…,wt 的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，
再访问它们的所有还未被访问过的邻接顶点,… 如此做下去，直到图中所有顶点都被访问到为止。
广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况。因此，广度优先搜索不是一个递归的过程，
其算法也 不是递归 的。
2009-7-30 软件基础教案（第八章 图）
队列的变化：
A
B C D
E F G H I J K
L
树的按层次进行访问的次序：
A,B,C,D,E,F,G,H、
I,J,K,L
适用的数据结构,队列
树：
A
B C D
1、结点 A进队
2、结点 A出队、访问，队空
3、结点 A的儿子结点进队
4,结点 B出队、访问
5、结点 B的儿子结点进队
6、结点 C出队、访问
7、结点 C的儿子结点进队
·
·
·
·
C D
E F GC D
E F GD
E F GD H
广度优先搜索的示例 2
2009-7-30 软件基础教案（第八章 图）
广度优先搜索的示例 3
无向图的实例：为了说明问题，邻接结点的访问次序以序号为准。序号小的先访问。如：结点 1 的邻接结点有三个 2,12,11
，则先访问结点 2,11，再访问结点 12。
1
2 12 11
3 6 7 10
4 5 8 9
1
2 1211
3 6 7 10
4 5 8 9
·
·
·
·
·
·
· ·
· ·
· ·
图的广度优先的访问次序：
1,2,11,12,3,6,7,10,4,5,8,9 适用的数据结构,队列
8.3最小生成树
( minimum cost spanning tree )
使用 不同的遍历图的方法,可以得到 不同的生成树 ；从不同的顶点出发,也可能得到 不同的生成树 。
按照生成树的定义,n 个顶点的连通网络的生成树有 n
个顶点,n-1条边。
构造最小生成树的 准则,
必须只使用该网络中的边来构造最小生成树；
必须使用且仅使用 n-1 条边来联结网络中的 n 个顶点；
不能使用产生回路的边。
最小生成树,所有生成树中，边的权值总和最小。
2009-7-30 软件基础教案（第八章 图）
8.4最短路径 (Shortest Path)
最短路径问题 (概念 ),如果从图中某一顶点 (称为源点 )到达另一顶点 (称为终点 )的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。
作业,p232 8-1 8-2
2009-7-30 软件基础教案（第八章 图）
The end! See you later!
第八章 图图的基本概念图的存储结构图的遍历最小生成树的概念 (简单介绍 )
最小路径的概念 (简单介绍 )
Chapter 8 Graph
2009-7-30 软件基础教案（第八章 图）
8.1 图的基本概念
1.图定义 图是由结点集合 (vertex)及结点间的关系集合组成的一种数据结构,
Graph＝ ( V,E )
其中 V = { x | x? 某个数据元素集合 }
是结点的有穷非空集合；
E = {(x,y) | x,y? V }
或 E = {<x,y> | x,y? V && Path (x,y)}
是结点之间关系的有穷集合，也叫做边 (edge)集合。
Path (x,y)表示从 x 到 y 的一条单向通路,它是有方向的。
2009-7-30 软件基础教案（第八章 图）
有向图与无向图 在有向图中，结点对 <x,y>是有序的。在无向图中，结点对 (x,y)是无序的。
子图 设有两个图 G＝ (V,E) 和 G’＝ (V’,E’)。若 V’?
V 且 E’?E,则称 图 G’ 是 图 G 的子图。
邻接结点 如果 (u,v) 是 E(G) 中的一条边，则称 u 与 v
互为邻接结点 。
2009-7-30 软件基础教案（第八章 图）
无 向图 G2
A B
C D
E
A B
D
E
A A B
C D
A B
C D
E
无向图 G2的子图
A B
C D
A A
C D
A
C
A B
C D
有向图 G1的子图有向图 G1
有向图无向图及其子图：
2009-7-30 软件基础教案（第八章 图）
权 某些图的边具有与它相关的数,称之为权。这种带权图叫做 网络 。 (书 p199 图 8-3)
完全图 若有 n 个顶点的无向图有 n(n-1)/2 条边,
则此图为完全无向图。 有 n 个顶点的有向图有 n(n-
1) 条边,则此图为完全有向图。
结点的度 一个顶点 v的度是与它相关联的边的条数。
记作 TD(v)。 在有向图中,顶点的度等于该顶点的入度
(ID(v))与出度 (OD(v))之和。 TD(v)=ID(v)+OD(v)
2009-7-30 软件基础教案（第八章 图）
例子 1,1 6
2
54
3
a
b c
d
e f
TD(1)=3 TD(2)=3
TD(3)=3 TD(4)=2
TD(5)=2 TD(6)=1
ID(a)=1 OD(a)=2 TD(a)=3
ID(b)=1 OD(b)=2 TD(b)=3
ID(c)=2 OD(c)=0 TD(c)=2
ID(d)=1 OD(d)=1 TD(d)=2
ID(e)=0 OD(e)=1 TD(e)=1
ID(f)=1 OD(f)=0 TD(f)=1
2009-7-30 软件基础教案（第八章 图）
1
2
3
5
6
8
74
10
7
9
6
6
7
12
315
16
30
45
A
B
D
C
E
60
35
80
40
75
网 络例子 2：
2009-7-30 软件基础教案（第八章 图）
路径 在图 G＝ (V,E) 中,若从顶点 vi 出发,沿一些边经过一些结点 vp1,vp2,…,vpm，到达顶点 vj。则称顶点序列 ( vi vp1 vp2,.,vpm vj ) 为从顶点 vi 到顶点
vj 的路径。 它经过的边 (vi,vp1),(vp1,vp2),...,(vpm,
vj)应是属于 E的边。
路径长度
非带权图的路径长度是指此路径上边的条数。
带权图的路径长度是指路径上各边的权之和。
2009-7-30 软件基础教案（第八章 图）
简单路径 若路径上各顶点 v1,v2,...,vm 均不互相重复,则称这样的路径为简单路径。
回路 若路径上第一个顶点 v1 与最后一个顶点 vm 重合,则称这样的路径为回路或环。
2009-7-30 软件基础教案（第八章 图）
连通图 在无向图中,若从顶点 v1到顶点 v2有路径,则称顶点 v1与 v2是连通的。如果图中任意一对顶点都是连通的,则称此图是 连通图 。
强连通图 在有向图中,若对于每一对顶点 vi和 vj,都存在一条从 vi到 vj和从 vj到 vi的路径,则称此图是强连通图。 (书 p198 图 8-2 G4)
2009-7-30 软件基础教案（第八章 图）
1
3 4 5
2 1
3 4 5
2
V={1,2,3,4,5}
E={(1,2),(1,3),(1,4),
(2,4),(4,5)}
V={1,2,3,4,5}
E={<1,2>,<1,3>,<3,1>,
<2,4>,<4,1>,<4,5>}
无向图 有向图连通图非连通图
1
3 4 5
2 6
7
H1连通分量 H2连通分量例子 3：
2009-7-30 软件基础教案（第八章 图）
1
3
2
强连通图 非强连通图
51
3 4
2
1
3 4
2
5
强连通分量
H1
强连通分量
H2
例子 4：
2009-7-30 软件基础教案（第八章 图）
生成树 一个连通图的生成树是它的极小连通子图，
在 n个顶点的情形下，有 n-1条边。但有向图则可能得到它的由若干有向树组成的生成森林。
本章不予讨论的图
2009-7-30 软件基础教案（第八章 图）
8.2 图的存储结构图的四种常用的存储形式：
邻接矩阵和加权邻接矩阵（ labeled adjacency matrix）
邻接表
十字链表 (不讲 )
邻接多重表（不讲）
一、邻接矩阵 （静态存储方法）
先决条件,若图 G=（ V,E）有确定个数的顶点！
存储方法,顶点?一维数组 (V表示 )
邻接关系?矩阵 (A表示 )
2009-7-30 软件基础教案（第八章 图）
设图 A = (V,E)是一个有 n 个顶点的图，则图的邻接矩阵是一个二维数组 A.edge[n][n]，定义：
,
),(,,
]][[,
否则或者如果
0
><1
A
EjiEji
jiE d g e
无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。
2009-7-30 软件基础教案（第八章 图）
1).无权值的无向图的邻接矩阵设无向图具有 n 个结点，则用 n 行 n 列的布尔矩阵 A 表示该无向图；
并且 A[i,j] = 1,如果 i 至 j 有一条无向边； A[I,j] = 0如果 i 至 j 没有一条无向边
。
注意,A[i,i] = 0。 i结点的度,i行或 i列之和。上三角矩阵或下三角矩阵 存储 。
表示成右图矩阵
A B
C D
E
A
B
C
D
E
0 1 1 0 0
1 0 0 1 1
1 0 0 0 1
0 1 0 0 1
0 1 1 1 0
A B C D E
2009-7-30 软件基础教案（第八章 图）
A B
C D
2).无权值的有向图的邻接矩阵设有向图具有 n 个结点，则用 n 行 n 列的布尔矩阵 A 表示该有向图；
如果 i 至 j 有一条有向边,A[i,j] = 1 ；如果 i 至 j 没有一条有向边
,A[i,j] = 0.
注意,A[i,i] = 0。 出度,i行之和。入度,j列之和。
表示成右图矩阵
0 1 1 0
0 0 0 0
0 0 0 1
1 0 0 0
A B C D
A
B
C
D
2009-7-30 软件基础教案（第八章 图）
3).网络的邻接矩阵本书使用该定义
),(,),(
]][[.
ji
ji
EjiEjijijiW
jiEdge
==
=!
<!
0
=A
对角线但是否则,
或且如>?
),(,),(]][[.
ji
EjiEjijiWjiEdge
=!
<=A
但是否则,
或>
0
1 2
3
A.Edge=
0
1
3
2
4
5
6
7
A.Edge=
V[]=[0,1,2,3]
V[]=[0,1,2,3,4,5,6,7]
例 1：
例 2：
A B C D E
A
B
C
D
E?
0010050
0004070
1000080
0400020
507080200
B
E
D
C
B
A
V
B
E
D
C
A
20
80
10
70
40
50
例 3：
2009-7-30 软件基础教案（第八章 图）
3.在无向图中,统计第 i 行 (列 ) 1 的个数可得顶点 i 的度 。
4.在有向图中,统计第 i 行 1 的个数可得顶点 i 的出度，统计第 j 列 1 的个数可得顶点 j 的入度。
5.属于静态存储方法。不易扩充。
6.与顶点个数有关，与边（弧）无关。会出现稀疏矩阵。
1.无向图的邻接矩阵是对称的，
2.有向图的邻接矩阵可能是不对称的。
邻接矩阵的特点：
2009-7-30 软件基础教案（第八章 图）
二,邻接表 (Adjacency List)－ （动态存储方法）
1）无向图的邻接表把同一个顶点发出的边链接在同一个边链表中，链表的每一个结点代表一条边，叫做边结点，结点中保存有与该边相关联的另一顶点的顶点下标 dest 和指向同一链表中下一个边结点的指针 link。
0
1
2
3
2009-7-30 软件基础教案（第八章 图）
2)有向图的邻接表和逆邻接表
在有向图的邻接表中，第 i 个边链表链接的边都是 顶点 i 发出的边 。也叫做 出边表 。
在有向图的逆邻接表中，第 i 个边链表链接的边都是 进入顶点 i 的边 。也叫做 入边表 。
2009-7-30 软件基础教案（第八章 图）
带权图的边结点中保存该边上的权值 cost。
顶点 i 的边链表的表头指针 adj 在顶点表的下标为 i
的顶点记录中，该记录还保存了该顶点的其它信息。
在邻接表的边链表中,各个边结点的链入顺序任意，
视边结点输入次序而定。
设图中有 n 个顶点,e 条边，则 用邻接表表示无向图时,需要 n 个顶点结点,2e 个边结点；用 邻接表表示有向图时,若不考虑逆邻接表，只需 n 个顶点结点，
e 个边结点。
2009-7-30 软件基础教案（第八章 图）
3)网络的邻接表 B
E
D
C
A
20
80
10
70
40
50
A
B
C
D
E
0
1
2
3
4
1 20
0 20
4 ^503 702 80
0 80
0 70
3 ^40
2 ^10
1 ^40
4 ^10
0 50
2009-7-30 软件基础教案（第八章 图）
8.3 图的遍历图的两种常见的遍历形式：
深度优先搜索
广度优先搜索遍历的定义,从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做 图的遍历 ( Graph Traversal )。
2009-7-30 软件基础教案（第八章 图）
遍历 的方法,
DFS 在访问图中某一起始顶点 v 后，由 v 出发，访问它的任一邻接顶点 w1；再从 w1 出发，访问与 w1邻 接但还没有访问过的顶点 w2；然后再从 w2 出发，进行类似的访问,… 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。
1、深度优先搜索 DFS ( Depth First Search )
2009-7-30 软件基础教案（第八章 图）
深度优先搜索的示例 1
深度优先搜索过程 深度优先生成树
深度优先搜索的示例 2
有向图的实例：为了说明问题，邻接结点的访问次序以序号为准。序号小的先访问。如：结点 5 的邻接结点有两个 6,7，
则先访问结点 6，再访问结点 7。
2009-7-30 软件基础教案（第八章 图）
5
6
7
2
4
1
3
5
6 7
2
3
1
4
·
·
·
· ·
·
·
从结点 出发的搜索序列：
5,6,2,3,1,4,7
适用的数据结构,栈
5
1
2
43
·
·
· ·
从结点 出发的搜索序列：
1,2,3,4没有搜索到所有的结点，必须另选图中未访问过的结点，
继续进行搜索。
1
2009-7-30 软件基础教案（第八章 图）
2.广度优先搜索 BFS ( Breadth First Search )
广度优先搜索的示例 1
广度优先搜索过程 广度优先生成树
2009-7-30 软件基础教案（第八章 图）
使用广度优先搜索在访问了起始顶点 v 之后，由 v 出发，依次访问 v 的各个未曾被访问过的邻接顶点 w1,
w2,…,wt，然后再顺序访问 w1,w2,…,wt 的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，
再访问它们的所有还未被访问过的邻接顶点,… 如此做下去，直到图中所有顶点都被访问到为止。
广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况。因此，广度优先搜索不是一个递归的过程，
其算法也 不是递归 的。
2009-7-30 软件基础教案（第八章 图）
队列的变化：
A
B C D
E F G H I J K
L
树的按层次进行访问的次序：
A,B,C,D,E,F,G,H、
I,J,K,L
适用的数据结构,队列
树：
A
B C D
1、结点 A进队
2、结点 A出队、访问，队空
3、结点 A的儿子结点进队
4,结点 B出队、访问
5、结点 B的儿子结点进队
6、结点 C出队、访问
7、结点 C的儿子结点进队
·
·
·
·
C D
E F GC D
E F GD
E F GD H
广度优先搜索的示例 2
2009-7-30 软件基础教案（第八章 图）
广度优先搜索的示例 3
无向图的实例：为了说明问题，邻接结点的访问次序以序号为准。序号小的先访问。如：结点 1 的邻接结点有三个 2,12,11
，则先访问结点 2,11，再访问结点 12。
1
2 12 11
3 6 7 10
4 5 8 9
1
2 1211
3 6 7 10
4 5 8 9
·
·
·
·
·
·
· ·
· ·
· ·
图的广度优先的访问次序：
1,2,11,12,3,6,7,10,4,5,8,9 适用的数据结构,队列
8.3最小生成树
( minimum cost spanning tree )
使用 不同的遍历图的方法,可以得到 不同的生成树 ；从不同的顶点出发,也可能得到 不同的生成树 。
按照生成树的定义,n 个顶点的连通网络的生成树有 n
个顶点,n-1条边。
构造最小生成树的 准则,
必须只使用该网络中的边来构造最小生成树；
必须使用且仅使用 n-1 条边来联结网络中的 n 个顶点；
不能使用产生回路的边。
最小生成树,所有生成树中，边的权值总和最小。
2009-7-30 软件基础教案（第八章 图）
8.4最短路径 (Shortest Path)
最短路径问题 (概念 ),如果从图中某一顶点 (称为源点 )到达另一顶点 (称为终点 )的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。
作业,p232 8-1 8-2
2009-7-30 软件基础教案（第八章 图）
The end! See you later!
