第六章 图
§ 6.1 图的定义和术语
图 (Graph)—— 图 G是由两个集合 V(G)和 E(G)组成的,
记为 G=(V,E)
其中,V(G)是顶点的非空有限集
E(G)是边的有限集合，边是顶点的无序对或有序对
有向图 —— 有向图 G是由两个集合 V(G)和 E(G)组成的其中,V(G)是顶点的非空有限集
E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为 <v,w>,v,w是顶点,v为弧尾,w为弧头
无向图 —— 无向图 G是由两个集合 V(G)和 E(G)组成的其中,V(G)是顶点的非空有限集
E(G)是边的有限集合，边是顶点的无序对，记为（ v,w）
或（ w,v),并且（ v,w)=(w,v)
例
2 4 5
1 3 6
G1
图 G1中,V(G1)={1,2,3,4,5,6}
E(G1)={<1,2>,<2,1>,<2,3>,<2,4>,<3,5>,<5,6>,<6,3>}
例
1 5 7
3 2 4
G2
6
图 G2中,V(G2)={1,2,3,4,5,6,7}
E(G1)={(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)}
有向完备图 —— n个顶点的有向图最大边数是 n(n-1)
无向完备图 —— n个顶点的无向图最大边数是 n(n-1)/2
权 —— 与图的边或弧相关的数叫 ~
网 —— 带权的图叫 ~
子图 —— 如果图 G(V,E)和图 G‘(V’,E‘),满足：
V’?V
E’?E
则称 G‘为 G的子图
顶点的度
无向图中，顶点的度为与每个顶点相连的边数
有向图中，顶点的度分成入度与出度
入度：以该顶点为头的弧的数目
出度：以该顶点为尾的弧的数目
路径 —— 路径是顶点的序列 V={Vi0,Vi1,……V in},满足
(Vij-1,Vij)?E 或 <Vij-1,Vij>?E,(1<j?n)
路径长度 —— 沿路径边的数目或沿路径各边权值之和
回路 —— 第一个顶点和最后一个顶点相同的路径叫 ~
简单路径 —— 序列中顶点不重复出现的路径叫 ~
简单回路 —— 除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫 ~
连通 —— 从顶点 V到顶点 W有一条路径，则说 V和 W是连通的
连通图 —— 图中任意两个顶点都是连通的叫 ~
连通分量 —— 非连通图的每一个连通部分叫 ~
强连通图 —— 有向图中，如果对每一对 Vi,Vj?V,Vi?Vj,
从 Vi到 Vj 和从 Vj到 Vi都存在路径，则称 G是 ~
例 2
1 3
2
1 3
有向完备图 无向完备图
3
5
6
例
2 4 5
1 3 6
图与子图 例
2 4 5
1 3 6
G1
顶点 2入度,1 出度,3
顶点 4入度,1 出度,0
例
1 5 7
3 2 4
G2
6
顶点 5的度,3
顶点 2的度,4
例
1 5 7
3 2 4
G2
6
例
2 4 5
1 3 6
G1
路径,1,2,3,5,6,3
路径长度,5
简单路径,1,2,3,5
回路,1,2,3,5,6,3,1
简单回路,3,5,6,3
路径,1,2,5,7,6,5,2,3
路径长度,7
简单路径,1,2,5,7,6
回路,1,2,5,7,6,5,2,1
简单回路,1,2,3,1
连通图例
2 4 5
1 3 6
强连通图3
5
6
例非连通图连通分量例
2 4 5
1 3 6
§ 6.2 图的存储结构
多重链表例
G1
2
4
1
3
例 1
5
3
2
4 G2
V1
V2 ^ ^V4 ^
V3 ^
^ V1 V2
V4 ^ V5 ^
V3
邻接矩阵 —— 表示顶点间相联关系的矩阵
定义,设 G=(V,E)是有 n?1个顶点的图,G的邻接矩阵 A是具有以下性质的 n阶方阵
，其它0
E ( G )v,v或)v,(v若1,],[ jijijiA
例
G1
2
4
1
3
例 1
5
3
2
4 G2
00110
00101
11010
10101
01010
0001
1000
0000
0110?
特点：
无向图的邻接矩阵对称，可压缩存储；有 n个顶点的无向图需存储空间为 n(n+1)/2
有向图邻接矩阵不一定对称；有 n个顶点的有向图需存储空间为 n2
无向图中顶点 Vi的度 TD(Vi)是邻接矩阵 A中第 i行元素之和
有向图中，
顶点 Vi的出度是 A中第 i行元素之和
顶点 Vi的入度是 A中第 i列元素之和
网络的邻接矩阵可定义为：
，其它0
E ( G )v,v或)v,(v若,],[ jijiijjiA?
06183
60240
12007
84005
30750
例 1
4
5
2
3
7
5
3
1
8
6
4
2
关联矩阵 —— 表示顶点与边的关联关系的矩阵
定义,设 G=(V,E)是有 n?1个顶点,e?0条边的图,G的关联矩阵 A是具有以下性质的 n?e阶矩阵
为头边相连，且顶点与边不相连顶点与为尾边相连，且顶点与有向图：
iji
ji
iji
jiA
,1
,0
,1
],[
边不相连顶点与，
边相连顶点与，无向图：
ji
jijiA
0
1],[
1100
0110
0001
1011?
4321
例
G1
2
4
1
3
1
2
3
4
例 1
5
3
2
4 G2
1
2
3
4
5
6
110000
000110
011100
101001
000011
4321 5 6
例 B
D
A C
1
2
3
4
5
6
A
B
C
D
4321 5 6
101011
110000
011100
000111
特点
关联矩阵每列只有两个非零元素，是稀疏矩阵； n越大，零元素比率越大
无向图中顶点 Vi的度 TD(Vi)是关联矩阵 A中第 i行元素之和
有向图中，
顶点 Vi的出度是 A中第 i行中,1”的个数
顶点 Vi的入度是 A中第 i行中,-1”的个数
邻接表
实现：为图中每个顶点建立一个单链表，第 i个单链表中的结点表示依附于顶点 Vi的边（有向图中指以 Vi为尾的弧）
typedef struct node
{ int adjvex; //邻接点域，存放与 Vi邻接的点在表头数组中的位置
struct node *next; //链域，指示下一条边或弧
}JD;
adjvex next
表头接点：
typedef struct tnode
{ int vexdata; //存放顶点信息
struct node *firstarc; //指示第一个邻接点
}TD;
TD ga[M]; //ga[0]不用
vexdata firstarc
例
G1
b
d
a
c
例 a
e
c
b
d G2
1
2
3
4
a
c
d
b
vexdata firstarc
3 2
4
1
^
^
^
^
adjvex next
1
2
3
4
a
c
d
b
vexdata firstarc
4
2
1
2 ^
^
^
adjvex next
5 e
4
3 5 ^1
5
3
2 3 ^
特点
无向图中顶点 Vi的度为第 i个单链表中的结点数
有向图中
顶点 Vi的出度为第 i个单链表中的结点个数
顶点 Vi的入度为整个 单链表中邻接点域值是 i的结点个数
逆邻接表：有向图中对每个结点建立以 Vi为头的弧的单链表例
G1
b
d
a
c
1
2
3
4
a
c
d
b
vexdata firstarc
4
1 ^
1 ^
^
3 ^
adjvex next
有向图的十字链表表示法弧结点：
typedef struct arcnode
{ int tailvex,headvex; //弧尾、弧头在表头数组中位置
struct arcnode *hlink； //指向弧头相同的下一条弧
struct arcnode *tlink; //指向弧尾相同的下一条弧
}AD;
tailvex headvex hlink tlink
顶点结点：
typedef struct dnode
{ int data; //存与顶点有关信息
struct arcnode *firstin； //指向以该顶点为弧头的第一个弧结点
struct arcnode *firstout; //指向以该顶点为弧尾的第一个弧结点
}DD;
DD g[M]; //g[0]不用
data firstin firstout
例 b
d
a
c
a
b
c
d
1
2
3
4
1 31 2
3 43 1
4 34 24 1
^
^
^
^^ ^ ^
^
无向图的邻接多重表表示法顶点结点：
typedef struct dnode
{ int data; //存与顶点有关的信息
struct node *firstedge; //指向第一条依附于该顶点的边
}DD;
DD ga[M]; //ga[0]不用 data firstedge
边结点：
typedef struct node
{ int mark; //标志域
int ivex,jvex; //该边依附的两个顶点在表头数组中位置
struct node *ilink,*jlink; //分别指向依附于 ivex和 jvex的下一条边
}JD;
mark ivex ilink jvex jlink
例 a
e
c
b
d
1
2
3
4
a
c
d
b
5 e
1 2 1 4
3 43 2
3 5 5 2
^
^
^
^^
6.3 图的遍历
从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历 ( Graph
Traversal )。
图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。
为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组 visited [ ]。
辅助数组 visited [ ] 的初始状态为 0,在图的遍历过程中,一旦某一个顶点 i 被访问,就立即让 visited [i] 为 1,防止它被多次访问。
图的遍历的分类,
深度优先搜索
DFS (Depth First Search)
广度优先搜索
BFS (Breadth First Search)
深度优先搜索 DFS ( Depth First Search )
深度优先搜索的示例
A
CD
E
G
B
F IH
A
CD
E
G
B
F IH
1 2 3
45
6
7
8 9
1 2 3
45
6
7
8 9前进 回退深度优先搜索过程 深度优先生成树
DFS 在访问图中某一 起始顶点 v 后,由 v
出发,访问它的任一 邻接顶点 w1; 再从 w1
出发,访问 与 w1邻 接 但还 没有访问过的顶点
w2; 然后再从 w2 出发,进行类似的访问,…
如此进行下去,直至到达所有的邻接顶点都被访问过的顶点 u 为止 。接着,退回一步,
退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。 如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问 ; 如果没有,就再退回一步进行搜索。重复上述过程,直到连通图中所有顶点都被访问过为止。
V1
V2
V4 V5
V3
V7V6
V8
例深度遍历,V1?V2?V4?V8?V5?V3?V6?V7
例 V1
V2
V4
V5 V3
V7
V6
V8
深度遍历,V1?V2?V4?V8?V5?V6?V3?V7
深度优先遍历算法
递归算法开始访问 V0,置 标志求 V0邻接点有邻接点 w
求下一邻接点w?V0
W访问过结束
N
Y
N
Y
DFS
开始标志数组初始化
Vi=1
Vi访问过
DFS
Vi=Vi+1
Vi==Vexnums
结束
N
N
Y
Y
Ch6_1.c
V1
V2
V4 V5
V3
V7V6
V8
例深度遍历,V1?
1
2
3
4
1
3
4
2
vexdata firstarc
2
7
8
3 ^
^
^
adjvex next
5 5
6
4 1 ^5
1
2
8 2 ^
6
7
8
6
7
8
7 3
6 3
5 4
^
^
^
V3?V7?V6?V2?V5?V8?V4
V1
V2
V4 V5
V3
V7V6
V8
例
1
2
3
4
1
3
4
2
vexdata firstarc
2
7
8
3 ^
^
^
adjvex next
5 5
6
^4
8 2 ^
6
7
8
6
7
8
7 ^
^
^
深度遍历,V1?V3?V7?V6?V2?V4?V8?V5
广度优先搜索 BFS ( Breadth First Search )
广度优先搜索的示例
A
CD
E
G
B
F IH
A
CD
E
G
B
F H
1 2
34
5
6
7
8 9
1 2
34
5
6
7
8 9
广度优先搜索过程 广度优先生成树
I
BFS在访问了 起始顶点 v 之后,由 v 出发,
依次访问 v 的各个 未被访问过的邻接顶点
w1,w2,…,wt,然后再顺序访问 w1,w2,…,
wt 的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点,… 如此做下去，
直到图中所有顶点都被访问到为止。
广度优先搜索是一种分层的搜索过程,每向前走一步可能访问一批顶点,不像深度优先搜索那样有往回退的情况。因此,广度优先搜索不是一个递归的过程。
为了实现逐层访问,算法中使用了一个 队列,
以记忆正在访问的这一层和上一层的顶点,
以便于向下一层访问。
为避免重复访问,需要一个辅助数组
visited [ ]，给被访问过的顶点加标记。
V1
V2
V4 V5
V3
V7V6
V8
例例 V1
V2
V4
V5 V3
V7
V6
V8
广度遍历,V1?V2?V3?V4?V5?V6?V7?V8
广度遍历,V1?V2?V3?V4?V5?V6?V7?V8
广度优先遍历算法开始标志数组初始化
Vi=1
Vi访问过
BFS
Vi=Vi+1
Vi==Vexnums
结束
N
N
Y
Y
Ch6_2.c
开始访问 V0,置 标志求 V邻接点 w
w存在吗 V下一邻接点?w
w访问过结束
N
Y
N
Y
BFS
初始化队列
V0入队队列空吗队头 V出队 访问 w,置 标志
w入队
N
a
a
Y
例 1
42 3
5
1
2
3
4
1
3
4
2
vexdata firstarc
5
5
4 3 ^
^
^
adjvex next
5 5
1 ^5
1
1
4 3 ^
2
2
0 1 2 3 4 5
1
f
r
遍历序列,1
0 1 2 3 4 5
4
f
r
遍历序列,1 4
0 1 2 3 4 5
4 3
f
r
遍历序列,1 4 3
例 1
42 3
5
1
2
3
4
1
3
4
2
vexdata firstarc
5
5
4 3 ^
^
^
adjvex next
5 5
1 ^5
1
1
4 3 ^
2
2
0 1 2 3 4 5
4 3 2
f
r
遍历序列,1 4 3 2
0 1 2 3 4 5
3 2
f
r
遍历序列,1 4 3 2
0 1 2 3 4 5
3 2 5
f
r
遍历序列,1 4 3 2 5
0 1 2 3 4 5
2 5
f
r
遍历序列,1 4 3 2 5
0 1 2 3 4 5
5
f
r
遍历序列,1 4 3 2 5
0 1 2 3 4 5
f
r
遍历序列,1 4 3 2 5
例 1
42 3
5
1
2
3
4
1
3
4
2
vexdata firstarc
5
5
4 3 ^
^
^
adjvex next
5 5
1 ^5
1
1
4 3 ^
2
2
§ 6.4 最短路径
问题提出用带权的有向图表示一个交通运输网，图中：
顶点 —— 表示城市边 —— 表示城市间的交通联系权 —— 表示此线路的长度或沿此线路运输所花的时间或费用等问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中，
各边上权值之和最小的一条路径 —— 最短路径
从某个源点到其余各顶点的最短路径
5
1
6
4
3
2
0
8
5
6 2
30
13
7
17
32
9
13
长度最短路径
<V0,V1>
<V0,V2>
<V0,V2,V3>
<V0,V2,V3,V4>
<V0,V2,V3,V4,V5>
<V0,V1,V6>
8
13
19
21
20
单源最短路径问题
问题的提法,给定一个带权有向图 D与源点 v，
求从 v 到 D中其它顶点的最短路径。 限定各边上的权值大于或等于 0。
为求得这些最短路径,Dijkstra提出按路径长度的递增次序,逐步产生最短路径的算法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点 v
到其它各顶点的最短路径全部求出为止。
举例说明
Dijkstra逐步求解的过程
1
0
4
32
10 100
30
50
20
60
10
源点 终点 最短路径 路径长度
v0 v1 (v0,v1) 10
v2 (v0,v1,v2) (v0,v3,v2)?,60,50
v3 (v0,v3) 30
v4 (v0,v4) (v0,v1,v2,v4)(v0,v3,v4) (v0,v3,v2,v4)
100,70,90,60
引入辅助数组 dist。它的每一个分量 dist[i]表示当前找到的从 源点 v0到 终点 vi 的最短路径的长度。初始状态：
若从源点 v0到顶点 vi 有边,则 dist[i]为该边上的权值；
若从源点 v0到顶点 vi 无边,则 dist[i]为? 。
假设 S 是已求得的最短路径的终点的集合，
则可证明,下一条最短路径必然是从 v0 出发，
中间只经过 S 中的顶点便可到达的那些顶点
vx (vx?V-S )的路径中的一条。
每次求得一条最短路径后,其终点 vk加入集合 S，然后 对所有的 vi?V-S，修改其 dist[i]
值 。
Dijkstra算法可描述如下：
① 初始化,S ← { v0 };
dist[j] ← Edge[0][j],j = 1,2,…,n-1;
// n为图中顶点个数
② 求出最短路径的长度：
dist[k] ← min { dist[ i] },i? V- S ;
S ← S U { k };
③ 修改：
dist[i] ← min{ dist[ i],dist[k] + Edge[k][i] },
对于每一个 i? V- S ;
④ 判断：若 S = V,则算法结束，否则转 ② 。
Dijkstra算法中各辅助数组的最终结果从表中读取源点 0到终点 v的最短路径的方法,举顶点 4为例
path[4] = 2 path[2] = 3
path[3] = 0,反过来排列，得到路径 0,3,2,4,这就是源点 0
到终点 4的最短路径。
0
41
2 3
10
50 10
20
60
30
100
序号 顶点 1 顶点 2 顶点 3 顶点 4
Dist 10 50 30 60
path 0 3 0 2
迪杰斯特拉 (Dijkstra)算法思想按路径长度递增次序产生最短路径算法：
把 V分成两组：
（ 1） S,已求出最短路径的顶点的集合
（ 2） V-S=T,尚未确定最短路径的顶点集合将 T中顶点按最短路径递增的次序加入到 S中，
保证：（ 1）从源点 V0到 S中各顶点的最短路径长度都不大于从 V0到 T中任何顶点的最短路径长度
（ 2）每个顶点对应一个距离值
S中顶点：从 V0到此顶点的最短路径长度
T中顶点：从 V0到此顶点的只包括 S中顶点作中间顶点的最短路径长度依据：可以证明 V0到 T中顶点 Vk的最短路径，或是从 V0到 Vk的直接路径的权值；或是从 V0经 S中顶点到 Vk的路径权值之和
（反证法可证）
求最短路径步骤
初使时令 S={V0},T={其余顶点 },T中顶点对应的距离值
若存在 <V0,Vi>，为 <V0,Vi>弧上的权值
若不存在 <V0,Vi>,为?
从 T中选取一个其距离值为最小的顶点 W，加入 S
对 T中顶点的距离值进行修改：若加进 W作中间顶点，从 V0
到 Vi的距离值比不加 W的路径要短，则修改此距离值
重复上述步骤，直到 S中包含所有顶点，即 S=V为止
算法实现
图用带权邻接矩阵存储 ad[][]
数组 dist[]存放当前找到的从源点 V0到每个终点的最短路径长度，其初态为图中直接路径权值
数组 pre[]表示从 V0到各终点的最短路径上，
此顶点的前一顶点的序号；若从 V0到某终点无路径，则用 0作为其前一顶点的序号
算法描述
6
2
7
5
4
3
1
8
5
6 2
30
13
7
17
32
9
0
170
20
60
50
790
32308131
[ ] [ ]ad
dist
0 1 2 3 4 5 6
0 13 8? 30? 32
pre
0 1 2 3 4 5 6
0 1 1 0 1 0 1
(1)k=1
Ch6_5.c
1
13
3
1
22 20
2 2
19
4
1
21
5
1
1
1
长度最短路径
13<V1,V2>
8<V1,V3>
13<V1,V3,V4>
19<V1,V3,V4,V5>
21<V1,V3,V4,V5,V6>
20<V1,V2,V7>
算法分析,T(n)=O(n2)
void shortpath_DIJ(int ad[][M],int k,int pre[],int dist[],int n)
{ int i,j,p,wm; k=k-1;
for(i=0;i<n;i++) { dist[i]=ad[k][i]; if(dist[i]<MAX) pre[i]=k+1;
else pre[i]=0; }
pre[k]=0; dist[k]=0; ad[k][k]=1;
for(j=0;j<(n-1);j++) { wm=MAX; p=-1;
for(i=0;i<n;i++) /*找到 v的最小距离 */
if((ad[i][i]==0)&&(dist[i]<wm)) {p=i; wm=dist[i]; }
if(p==-1) break; else{ ad[p][p]=1;
for(i=0;i<n;i++)
if(ad[i][i]==0) if(dist[p]+ad[p][i]<dist[i])
{ dist[i]=dist[p]+ad[p][i]; pre[i]=p+1; }
} } }
每一对顶点之间的最短路径
方法：每次以一个顶点为源点，重复执行 Dijkstra算法
n次 —— T(n)=O(n3)
方法二：弗洛伊德 (Floyd)算法
算法思想：逐个顶点试探法
求最短路径步骤
初始时设置一个 n阶方阵，令其对角线元素为 0，若存在弧 <Vi,Vj>,则对应元素为权值；否则为?
逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值
所有顶点试探完毕，算法结束例
A
C
B
2
6
4
3 11
0 4 11
6 0 2
3? 0
初始,路径,AB ACBA BC
CA
0 4 6
6 0 2
3 7 0
加入 V2,路径：
AB ABC
BA BC
CA CAB
0 4 11
6 0 2
3 7 0
加入 V1,路径：
AB AC
BA BC
CA CAB
0 4 6
5 0 2
3 7 0
加入 V3,路径：
AB ABC
BCA BC
CA CAB
算法实现
图用邻接矩阵存储
length[][]存放最短路径长度
path[i][j]是从 Vi到 Vj的最短路径上 Vj前一顶点序号
算法描述例
1
3
2
2
6
4
3 11
初始：
0 4 11
6 0 2
3? 0
length=
0 1 1
2 0 2
3 0 0
path=
加入 V1,0 4 11
6 0 2
3 7 0
length=
0 1 1
2 0 2
3 1 0
path=
加入 V2,0 4 6
6 0 2
3 7 0
length=
0 1 2
2 0 2
3 1 0
path=
加入 V3,0 4 6
5 0 2
3 7 0
length=
0 1 2
3 0 2
3 1 0
path=
Ch6_6.c
算法分析,T(n)=O(n3)
生成树
定义：所有顶点均由边连接在一起，但不存在回路的图叫 ~
深度优先生成树与广度优先生成树
生成森林：非连通图每个连通分量的生成树一起组成非连通图的 ~
说明
一个图可以有许多棵不同的生成树
所有生成树具有以下共同特点：
生成树的顶点个数与图的顶点个数相同
生成树是图的极小连通子图
一个有 n个顶点的连通图的生成树有 n-1条边
生成树中任意两个顶点间的路径是唯一的
在生成树中再加一条边必然形成回路
含 n个顶点 n-1条边的图不一定是生成树
G
H
K I
(补充 ) 生成树
V1
V2
V4 V5
V3
V7V6
V8
例 深度遍历,V1?V2?V4?V8?V5?V3?V6?V7
V1
V2
V4
V5
V3
V7
V6
V8
深度优先生成树
V1
V2
V4 V5
V3
V7V6
V8
广度优先生成树
V1
V2
V4 V5
V3
V7V6
V8V1
V2
V4 V5
V3
V7V6
V8
广度遍历,V1?V2?V3?V4?V5?V6?V7?V8
例
A B
L M
C
F
D E
G H
KI
J
A
B
L
M
C F
J
D
E
G
H
K I
深度优先生成森林
最小生成树
问题提出要在 n个城市间建立通信联络网，
顶点 —— 表示城市权 —— 城市间建立通信线路所需花费代价希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小 ——— 最小代价生成树
问题分析
1
65
43
27
13
17
9
18
12
7 5
24
10
n个城市间，最多可设置 n(n-1)/2条线路
n个城市间建立通信网，只需 n-1条线路问题转化为：如何在可能的线路中选择 n-1条，能把所有城市（顶点）均连起来，且总耗费
（各边权值之和）最小
构造最小生成树方法
方法一：普里姆 (Prim)算法
算法思想：设 N=(V,{E})是连通网,TE是 N上最小生成树中边的集合
初始令 U={u0},(u0?V),TE=?
在所有 u?U,v?V-U的边 (u,v)?E中，找一条代价最小的边 (u0,v0)
将 (u0,v0)并入集合 TE,同时 v0并入 U
重复上述操作直至 U=V为止，则 T=(V,{TE})为 N的最小生成树
算法实现：图用邻接矩阵表示
算法描述
算法评价,T(n)=O(n2)
Ch6_3.c
例 1
65
4
3
2
6 5
1
3
5
6
6
4 2
5
1
3
1
1
6
3
1
4
1
6
4
3
1
4 2
1
1
6
4
3
2 1
4 2
5
1
65
4
3
2 1
4 2
5
3
1
0624
6063
2055
465051
3506
5160
0 1 2 3 4 5
0
1
2
3
4
5
1
-2
1
-4
1
-1
例 1
65
4
3
2
6 5
1
3
5
6
6
4 2
5
1
-5
1-3
1
65
4
3
2
6 5
1
3
5
6
6
4 2
5
1
65
4
3
2 1
4 2
5
3
方法二：克鲁斯卡尔 (Kruskal)算法
算法思想：设连通网 N=(V,{E}),令最小生成树
初始状态为只有 n个顶点而无边的非连通图 T=(V,{?})，每个顶点自成一个连通分量
在 E中选取代价最小的边，若该边依附的顶点落在 T中不同的连通分量上，则将此边加入到 T中；否则，舍去此边，选取下一条代价最小的边
依此类推，直至 T中所有顶点都在同一连通分量上为止例 1
65
4
3
2
6 5
1
3
5
6
6
4 2
5
1
65
4
3
2 1
23 4
5
（ 0）用顶点数组和边数组存放顶点和边信息
（ 1）初始时，令每个顶点的 jihe互不相同；每个边的 flag为 0
（ 2）选出权值最小且 flag为 0的边
（ 3）若该边依附的两个顶点的 jihe 值不同，即非连通，则令该边的 flag=1,选中该边；再令该边依附的两顶点的 jihe
以及两集合中所有顶点的 jihe 相同若该边依附的两个顶点的 jihe 值相同，即连通，则令该边的 flag=2,即舍去该边
（ 4）重复上述步骤，直到选出 n-1条边为止顶点结点：
typedef struct
{ int data; //顶点信息
int jihe;
}VEX;
边结点：
typedef struct
{ int vexh,vext; //边依附的两顶点
int weight; //边的权值
int flag; //标志域
}EDGE;
算法实现：
例 1
65
4
3
2
6 5
1
3
5
6
6
4 2
5
Ch6_30.c
算法描述：
data jihe
1
2
4
5
3
6
1
2
4
5
3
6
1
2
4
5
3
6
vexh weight
1
1
2
2
1
3
2
3
3
5
4
4
vext flag
6
1
5
3
5
5
0
0
0
0
0
0
0
1
3
4
2
5
6
7
8
9
3
3
4
5
5
6
6
6
6
4
2
6
0
0
0
0
1
1
1
1
1
4
2
1
1
1
2
2
2
2
21
65
4
3
2 1
23 4
5
§ 6.1 图的定义和术语
图 (Graph)—— 图 G是由两个集合 V(G)和 E(G)组成的,
记为 G=(V,E)
其中,V(G)是顶点的非空有限集
E(G)是边的有限集合，边是顶点的无序对或有序对
有向图 —— 有向图 G是由两个集合 V(G)和 E(G)组成的其中,V(G)是顶点的非空有限集
E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为 <v,w>,v,w是顶点,v为弧尾,w为弧头
无向图 —— 无向图 G是由两个集合 V(G)和 E(G)组成的其中,V(G)是顶点的非空有限集
E(G)是边的有限集合，边是顶点的无序对，记为（ v,w）
或（ w,v),并且（ v,w)=(w,v)
例
2 4 5
1 3 6
G1
图 G1中,V(G1)={1,2,3,4,5,6}
E(G1)={<1,2>,<2,1>,<2,3>,<2,4>,<3,5>,<5,6>,<6,3>}
例
1 5 7
3 2 4
G2
6
图 G2中,V(G2)={1,2,3,4,5,6,7}
E(G1)={(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)}
有向完备图 —— n个顶点的有向图最大边数是 n(n-1)
无向完备图 —— n个顶点的无向图最大边数是 n(n-1)/2
权 —— 与图的边或弧相关的数叫 ~
网 —— 带权的图叫 ~
子图 —— 如果图 G(V,E)和图 G‘(V’,E‘),满足：
V’?V
E’?E
则称 G‘为 G的子图
顶点的度
无向图中，顶点的度为与每个顶点相连的边数
有向图中，顶点的度分成入度与出度
入度：以该顶点为头的弧的数目
出度：以该顶点为尾的弧的数目
路径 —— 路径是顶点的序列 V={Vi0,Vi1,……V in},满足
(Vij-1,Vij)?E 或 <Vij-1,Vij>?E,(1<j?n)
路径长度 —— 沿路径边的数目或沿路径各边权值之和
回路 —— 第一个顶点和最后一个顶点相同的路径叫 ~
简单路径 —— 序列中顶点不重复出现的路径叫 ~
简单回路 —— 除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫 ~
连通 —— 从顶点 V到顶点 W有一条路径，则说 V和 W是连通的
连通图 —— 图中任意两个顶点都是连通的叫 ~
连通分量 —— 非连通图的每一个连通部分叫 ~
强连通图 —— 有向图中，如果对每一对 Vi,Vj?V,Vi?Vj,
从 Vi到 Vj 和从 Vj到 Vi都存在路径，则称 G是 ~
例 2
1 3
2
1 3
有向完备图 无向完备图
3
5
6
例
2 4 5
1 3 6
图与子图 例
2 4 5
1 3 6
G1
顶点 2入度,1 出度,3
顶点 4入度,1 出度,0
例
1 5 7
3 2 4
G2
6
顶点 5的度,3
顶点 2的度,4
例
1 5 7
3 2 4
G2
6
例
2 4 5
1 3 6
G1
路径,1,2,3,5,6,3
路径长度,5
简单路径,1,2,3,5
回路,1,2,3,5,6,3,1
简单回路,3,5,6,3
路径,1,2,5,7,6,5,2,3
路径长度,7
简单路径,1,2,5,7,6
回路,1,2,5,7,6,5,2,1
简单回路,1,2,3,1
连通图例
2 4 5
1 3 6
强连通图3
5
6
例非连通图连通分量例
2 4 5
1 3 6
§ 6.2 图的存储结构
多重链表例
G1
2
4
1
3
例 1
5
3
2
4 G2
V1
V2 ^ ^V4 ^
V3 ^
^ V1 V2
V4 ^ V5 ^
V3
邻接矩阵 —— 表示顶点间相联关系的矩阵
定义,设 G=(V,E)是有 n?1个顶点的图,G的邻接矩阵 A是具有以下性质的 n阶方阵
，其它0
E ( G )v,v或)v,(v若1,],[ jijijiA
例
G1
2
4
1
3
例 1
5
3
2
4 G2
00110
00101
11010
10101
01010
0001
1000
0000
0110?
特点：
无向图的邻接矩阵对称，可压缩存储；有 n个顶点的无向图需存储空间为 n(n+1)/2
有向图邻接矩阵不一定对称；有 n个顶点的有向图需存储空间为 n2
无向图中顶点 Vi的度 TD(Vi)是邻接矩阵 A中第 i行元素之和
有向图中，
顶点 Vi的出度是 A中第 i行元素之和
顶点 Vi的入度是 A中第 i列元素之和
网络的邻接矩阵可定义为：
，其它0
E ( G )v,v或)v,(v若,],[ jijiijjiA?
06183
60240
12007
84005
30750
例 1
4
5
2
3
7
5
3
1
8
6
4
2
关联矩阵 —— 表示顶点与边的关联关系的矩阵
定义,设 G=(V,E)是有 n?1个顶点,e?0条边的图,G的关联矩阵 A是具有以下性质的 n?e阶矩阵
为头边相连，且顶点与边不相连顶点与为尾边相连，且顶点与有向图：
iji
ji
iji
jiA
,1
,0
,1
],[
边不相连顶点与，
边相连顶点与，无向图：
ji
jijiA
0
1],[
1100
0110
0001
1011?
4321
例
G1
2
4
1
3
1
2
3
4
例 1
5
3
2
4 G2
1
2
3
4
5
6
110000
000110
011100
101001
000011
4321 5 6
例 B
D
A C
1
2
3
4
5
6
A
B
C
D
4321 5 6
101011
110000
011100
000111
特点
关联矩阵每列只有两个非零元素，是稀疏矩阵； n越大，零元素比率越大
无向图中顶点 Vi的度 TD(Vi)是关联矩阵 A中第 i行元素之和
有向图中，
顶点 Vi的出度是 A中第 i行中,1”的个数
顶点 Vi的入度是 A中第 i行中,-1”的个数
邻接表
实现：为图中每个顶点建立一个单链表，第 i个单链表中的结点表示依附于顶点 Vi的边（有向图中指以 Vi为尾的弧）
typedef struct node
{ int adjvex; //邻接点域，存放与 Vi邻接的点在表头数组中的位置
struct node *next; //链域，指示下一条边或弧
}JD;
adjvex next
表头接点：
typedef struct tnode
{ int vexdata; //存放顶点信息
struct node *firstarc; //指示第一个邻接点
}TD;
TD ga[M]; //ga[0]不用
vexdata firstarc
例
G1
b
d
a
c
例 a
e
c
b
d G2
1
2
3
4
a
c
d
b
vexdata firstarc
3 2
4
1
^
^
^
^
adjvex next
1
2
3
4
a
c
d
b
vexdata firstarc
4
2
1
2 ^
^
^
adjvex next
5 e
4
3 5 ^1
5
3
2 3 ^
特点
无向图中顶点 Vi的度为第 i个单链表中的结点数
有向图中
顶点 Vi的出度为第 i个单链表中的结点个数
顶点 Vi的入度为整个 单链表中邻接点域值是 i的结点个数
逆邻接表：有向图中对每个结点建立以 Vi为头的弧的单链表例
G1
b
d
a
c
1
2
3
4
a
c
d
b
vexdata firstarc
4
1 ^
1 ^
^
3 ^
adjvex next
有向图的十字链表表示法弧结点：
typedef struct arcnode
{ int tailvex,headvex; //弧尾、弧头在表头数组中位置
struct arcnode *hlink； //指向弧头相同的下一条弧
struct arcnode *tlink; //指向弧尾相同的下一条弧
}AD;
tailvex headvex hlink tlink
顶点结点：
typedef struct dnode
{ int data; //存与顶点有关信息
struct arcnode *firstin； //指向以该顶点为弧头的第一个弧结点
struct arcnode *firstout; //指向以该顶点为弧尾的第一个弧结点
}DD;
DD g[M]; //g[0]不用
data firstin firstout
例 b
d
a
c
a
b
c
d
1
2
3
4
1 31 2
3 43 1
4 34 24 1
^
^
^
^^ ^ ^
^
无向图的邻接多重表表示法顶点结点：
typedef struct dnode
{ int data; //存与顶点有关的信息
struct node *firstedge; //指向第一条依附于该顶点的边
}DD;
DD ga[M]; //ga[0]不用 data firstedge
边结点：
typedef struct node
{ int mark; //标志域
int ivex,jvex; //该边依附的两个顶点在表头数组中位置
struct node *ilink,*jlink; //分别指向依附于 ivex和 jvex的下一条边
}JD;
mark ivex ilink jvex jlink
例 a
e
c
b
d
1
2
3
4
a
c
d
b
5 e
1 2 1 4
3 43 2
3 5 5 2
^
^
^
^^
6.3 图的遍历
从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历 ( Graph
Traversal )。
图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。
为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组 visited [ ]。
辅助数组 visited [ ] 的初始状态为 0,在图的遍历过程中,一旦某一个顶点 i 被访问,就立即让 visited [i] 为 1,防止它被多次访问。
图的遍历的分类,
深度优先搜索
DFS (Depth First Search)
广度优先搜索
BFS (Breadth First Search)
深度优先搜索 DFS ( Depth First Search )
深度优先搜索的示例
A
CD
E
G
B
F IH
A
CD
E
G
B
F IH
1 2 3
45
6
7
8 9
1 2 3
45
6
7
8 9前进 回退深度优先搜索过程 深度优先生成树
DFS 在访问图中某一 起始顶点 v 后,由 v
出发,访问它的任一 邻接顶点 w1; 再从 w1
出发,访问 与 w1邻 接 但还 没有访问过的顶点
w2; 然后再从 w2 出发,进行类似的访问,…
如此进行下去,直至到达所有的邻接顶点都被访问过的顶点 u 为止 。接着,退回一步,
退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。 如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问 ; 如果没有,就再退回一步进行搜索。重复上述过程,直到连通图中所有顶点都被访问过为止。
V1
V2
V4 V5
V3
V7V6
V8
例深度遍历,V1?V2?V4?V8?V5?V3?V6?V7
例 V1
V2
V4
V5 V3
V7
V6
V8
深度遍历,V1?V2?V4?V8?V5?V6?V3?V7
深度优先遍历算法
递归算法开始访问 V0,置 标志求 V0邻接点有邻接点 w
求下一邻接点w?V0
W访问过结束
N
Y
N
Y
DFS
开始标志数组初始化
Vi=1
Vi访问过
DFS
Vi=Vi+1
Vi==Vexnums
结束
N
N
Y
Y
Ch6_1.c
V1
V2
V4 V5
V3
V7V6
V8
例深度遍历,V1?
1
2
3
4
1
3
4
2
vexdata firstarc
2
7
8
3 ^
^
^
adjvex next
5 5
6
4 1 ^5
1
2
8 2 ^
6
7
8
6
7
8
7 3
6 3
5 4
^
^
^
V3?V7?V6?V2?V5?V8?V4
V1
V2
V4 V5
V3
V7V6
V8
例
1
2
3
4
1
3
4
2
vexdata firstarc
2
7
8
3 ^
^
^
adjvex next
5 5
6
^4
8 2 ^
6
7
8
6
7
8
7 ^
^
^
深度遍历,V1?V3?V7?V6?V2?V4?V8?V5
广度优先搜索 BFS ( Breadth First Search )
广度优先搜索的示例
A
CD
E
G
B
F IH
A
CD
E
G
B
F H
1 2
34
5
6
7
8 9
1 2
34
5
6
7
8 9
广度优先搜索过程 广度优先生成树
I
BFS在访问了 起始顶点 v 之后,由 v 出发,
依次访问 v 的各个 未被访问过的邻接顶点
w1,w2,…,wt,然后再顺序访问 w1,w2,…,
wt 的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点,… 如此做下去，
直到图中所有顶点都被访问到为止。
广度优先搜索是一种分层的搜索过程,每向前走一步可能访问一批顶点,不像深度优先搜索那样有往回退的情况。因此,广度优先搜索不是一个递归的过程。
为了实现逐层访问,算法中使用了一个 队列,
以记忆正在访问的这一层和上一层的顶点,
以便于向下一层访问。
为避免重复访问,需要一个辅助数组
visited [ ]，给被访问过的顶点加标记。
V1
V2
V4 V5
V3
V7V6
V8
例例 V1
V2
V4
V5 V3
V7
V6
V8
广度遍历,V1?V2?V3?V4?V5?V6?V7?V8
广度遍历,V1?V2?V3?V4?V5?V6?V7?V8
广度优先遍历算法开始标志数组初始化
Vi=1
Vi访问过
BFS
Vi=Vi+1
Vi==Vexnums
结束
N
N
Y
Y
Ch6_2.c
开始访问 V0,置 标志求 V邻接点 w
w存在吗 V下一邻接点?w
w访问过结束
N
Y
N
Y
BFS
初始化队列
V0入队队列空吗队头 V出队 访问 w,置 标志
w入队
N
a
a
Y
例 1
42 3
5
1
2
3
4
1
3
4
2
vexdata firstarc
5
5
4 3 ^
^
^
adjvex next
5 5
1 ^5
1
1
4 3 ^
2
2
0 1 2 3 4 5
1
f
r
遍历序列,1
0 1 2 3 4 5
4
f
r
遍历序列,1 4
0 1 2 3 4 5
4 3
f
r
遍历序列,1 4 3
例 1
42 3
5
1
2
3
4
1
3
4
2
vexdata firstarc
5
5
4 3 ^
^
^
adjvex next
5 5
1 ^5
1
1
4 3 ^
2
2
0 1 2 3 4 5
4 3 2
f
r
遍历序列,1 4 3 2
0 1 2 3 4 5
3 2
f
r
遍历序列,1 4 3 2
0 1 2 3 4 5
3 2 5
f
r
遍历序列,1 4 3 2 5
0 1 2 3 4 5
2 5
f
r
遍历序列,1 4 3 2 5
0 1 2 3 4 5
5
f
r
遍历序列,1 4 3 2 5
0 1 2 3 4 5
f
r
遍历序列,1 4 3 2 5
例 1
42 3
5
1
2
3
4
1
3
4
2
vexdata firstarc
5
5
4 3 ^
^
^
adjvex next
5 5
1 ^5
1
1
4 3 ^
2
2
§ 6.4 最短路径
问题提出用带权的有向图表示一个交通运输网，图中：
顶点 —— 表示城市边 —— 表示城市间的交通联系权 —— 表示此线路的长度或沿此线路运输所花的时间或费用等问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中，
各边上权值之和最小的一条路径 —— 最短路径
从某个源点到其余各顶点的最短路径
5
1
6
4
3
2
0
8
5
6 2
30
13
7
17
32
9
13
长度最短路径
<V0,V1>
<V0,V2>
<V0,V2,V3>
<V0,V2,V3,V4>
<V0,V2,V3,V4,V5>
<V0,V1,V6>
8
13
19
21
20
单源最短路径问题
问题的提法,给定一个带权有向图 D与源点 v，
求从 v 到 D中其它顶点的最短路径。 限定各边上的权值大于或等于 0。
为求得这些最短路径,Dijkstra提出按路径长度的递增次序,逐步产生最短路径的算法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点 v
到其它各顶点的最短路径全部求出为止。
举例说明
Dijkstra逐步求解的过程
1
0
4
32
10 100
30
50
20
60
10
源点 终点 最短路径 路径长度
v0 v1 (v0,v1) 10
v2 (v0,v1,v2) (v0,v3,v2)?,60,50
v3 (v0,v3) 30
v4 (v0,v4) (v0,v1,v2,v4)(v0,v3,v4) (v0,v3,v2,v4)
100,70,90,60
引入辅助数组 dist。它的每一个分量 dist[i]表示当前找到的从 源点 v0到 终点 vi 的最短路径的长度。初始状态：
若从源点 v0到顶点 vi 有边,则 dist[i]为该边上的权值；
若从源点 v0到顶点 vi 无边,则 dist[i]为? 。
假设 S 是已求得的最短路径的终点的集合，
则可证明,下一条最短路径必然是从 v0 出发，
中间只经过 S 中的顶点便可到达的那些顶点
vx (vx?V-S )的路径中的一条。
每次求得一条最短路径后,其终点 vk加入集合 S，然后 对所有的 vi?V-S，修改其 dist[i]
值 。
Dijkstra算法可描述如下：
① 初始化,S ← { v0 };
dist[j] ← Edge[0][j],j = 1,2,…,n-1;
// n为图中顶点个数
② 求出最短路径的长度：
dist[k] ← min { dist[ i] },i? V- S ;
S ← S U { k };
③ 修改：
dist[i] ← min{ dist[ i],dist[k] + Edge[k][i] },
对于每一个 i? V- S ;
④ 判断：若 S = V,则算法结束，否则转 ② 。
Dijkstra算法中各辅助数组的最终结果从表中读取源点 0到终点 v的最短路径的方法,举顶点 4为例
path[4] = 2 path[2] = 3
path[3] = 0,反过来排列，得到路径 0,3,2,4,这就是源点 0
到终点 4的最短路径。
0
41
2 3
10
50 10
20
60
30
100
序号 顶点 1 顶点 2 顶点 3 顶点 4
Dist 10 50 30 60
path 0 3 0 2
迪杰斯特拉 (Dijkstra)算法思想按路径长度递增次序产生最短路径算法：
把 V分成两组：
（ 1） S,已求出最短路径的顶点的集合
（ 2） V-S=T,尚未确定最短路径的顶点集合将 T中顶点按最短路径递增的次序加入到 S中，
保证：（ 1）从源点 V0到 S中各顶点的最短路径长度都不大于从 V0到 T中任何顶点的最短路径长度
（ 2）每个顶点对应一个距离值
S中顶点：从 V0到此顶点的最短路径长度
T中顶点：从 V0到此顶点的只包括 S中顶点作中间顶点的最短路径长度依据：可以证明 V0到 T中顶点 Vk的最短路径，或是从 V0到 Vk的直接路径的权值；或是从 V0经 S中顶点到 Vk的路径权值之和
（反证法可证）
求最短路径步骤
初使时令 S={V0},T={其余顶点 },T中顶点对应的距离值
若存在 <V0,Vi>，为 <V0,Vi>弧上的权值
若不存在 <V0,Vi>,为?
从 T中选取一个其距离值为最小的顶点 W，加入 S
对 T中顶点的距离值进行修改：若加进 W作中间顶点，从 V0
到 Vi的距离值比不加 W的路径要短，则修改此距离值
重复上述步骤，直到 S中包含所有顶点，即 S=V为止
算法实现
图用带权邻接矩阵存储 ad[][]
数组 dist[]存放当前找到的从源点 V0到每个终点的最短路径长度，其初态为图中直接路径权值
数组 pre[]表示从 V0到各终点的最短路径上，
此顶点的前一顶点的序号；若从 V0到某终点无路径，则用 0作为其前一顶点的序号
算法描述
6
2
7
5
4
3
1
8
5
6 2
30
13
7
17
32
9
0
170
20
60
50
790
32308131
[ ] [ ]ad
dist
0 1 2 3 4 5 6
0 13 8? 30? 32
pre
0 1 2 3 4 5 6
0 1 1 0 1 0 1
(1)k=1
Ch6_5.c
1
13
3
1
22 20
2 2
19
4
1
21
5
1
1
1
长度最短路径
13<V1,V2>
8<V1,V3>
13<V1,V3,V4>
19<V1,V3,V4,V5>
21<V1,V3,V4,V5,V6>
20<V1,V2,V7>
算法分析,T(n)=O(n2)
void shortpath_DIJ(int ad[][M],int k,int pre[],int dist[],int n)
{ int i,j,p,wm; k=k-1;
for(i=0;i<n;i++) { dist[i]=ad[k][i]; if(dist[i]<MAX) pre[i]=k+1;
else pre[i]=0; }
pre[k]=0; dist[k]=0; ad[k][k]=1;
for(j=0;j<(n-1);j++) { wm=MAX; p=-1;
for(i=0;i<n;i++) /*找到 v的最小距离 */
if((ad[i][i]==0)&&(dist[i]<wm)) {p=i; wm=dist[i]; }
if(p==-1) break; else{ ad[p][p]=1;
for(i=0;i<n;i++)
if(ad[i][i]==0) if(dist[p]+ad[p][i]<dist[i])
{ dist[i]=dist[p]+ad[p][i]; pre[i]=p+1; }
} } }
每一对顶点之间的最短路径
方法：每次以一个顶点为源点，重复执行 Dijkstra算法
n次 —— T(n)=O(n3)
方法二：弗洛伊德 (Floyd)算法
算法思想：逐个顶点试探法
求最短路径步骤
初始时设置一个 n阶方阵，令其对角线元素为 0，若存在弧 <Vi,Vj>,则对应元素为权值；否则为?
逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值
所有顶点试探完毕，算法结束例
A
C
B
2
6
4
3 11
0 4 11
6 0 2
3? 0
初始,路径,AB ACBA BC
CA
0 4 6
6 0 2
3 7 0
加入 V2,路径：
AB ABC
BA BC
CA CAB
0 4 11
6 0 2
3 7 0
加入 V1,路径：
AB AC
BA BC
CA CAB
0 4 6
5 0 2
3 7 0
加入 V3,路径：
AB ABC
BCA BC
CA CAB
算法实现
图用邻接矩阵存储
length[][]存放最短路径长度
path[i][j]是从 Vi到 Vj的最短路径上 Vj前一顶点序号
算法描述例
1
3
2
2
6
4
3 11
初始：
0 4 11
6 0 2
3? 0
length=
0 1 1
2 0 2
3 0 0
path=
加入 V1,0 4 11
6 0 2
3 7 0
length=
0 1 1
2 0 2
3 1 0
path=
加入 V2,0 4 6
6 0 2
3 7 0
length=
0 1 2
2 0 2
3 1 0
path=
加入 V3,0 4 6
5 0 2
3 7 0
length=
0 1 2
3 0 2
3 1 0
path=
Ch6_6.c
算法分析,T(n)=O(n3)
生成树
定义：所有顶点均由边连接在一起，但不存在回路的图叫 ~
深度优先生成树与广度优先生成树
生成森林：非连通图每个连通分量的生成树一起组成非连通图的 ~
说明
一个图可以有许多棵不同的生成树
所有生成树具有以下共同特点：
生成树的顶点个数与图的顶点个数相同
生成树是图的极小连通子图
一个有 n个顶点的连通图的生成树有 n-1条边
生成树中任意两个顶点间的路径是唯一的
在生成树中再加一条边必然形成回路
含 n个顶点 n-1条边的图不一定是生成树
G
H
K I
(补充 ) 生成树
V1
V2
V4 V5
V3
V7V6
V8
例 深度遍历,V1?V2?V4?V8?V5?V3?V6?V7
V1
V2
V4
V5
V3
V7
V6
V8
深度优先生成树
V1
V2
V4 V5
V3
V7V6
V8
广度优先生成树
V1
V2
V4 V5
V3
V7V6
V8V1
V2
V4 V5
V3
V7V6
V8
广度遍历,V1?V2?V3?V4?V5?V6?V7?V8
例
A B
L M
C
F
D E
G H
KI
J
A
B
L
M
C F
J
D
E
G
H
K I
深度优先生成森林
最小生成树
问题提出要在 n个城市间建立通信联络网，
顶点 —— 表示城市权 —— 城市间建立通信线路所需花费代价希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小 ——— 最小代价生成树
问题分析
1
65
43
27
13
17
9
18
12
7 5
24
10
n个城市间，最多可设置 n(n-1)/2条线路
n个城市间建立通信网，只需 n-1条线路问题转化为：如何在可能的线路中选择 n-1条，能把所有城市（顶点）均连起来，且总耗费
（各边权值之和）最小
构造最小生成树方法
方法一：普里姆 (Prim)算法
算法思想：设 N=(V,{E})是连通网,TE是 N上最小生成树中边的集合
初始令 U={u0},(u0?V),TE=?
在所有 u?U,v?V-U的边 (u,v)?E中，找一条代价最小的边 (u0,v0)
将 (u0,v0)并入集合 TE,同时 v0并入 U
重复上述操作直至 U=V为止，则 T=(V,{TE})为 N的最小生成树
算法实现：图用邻接矩阵表示
算法描述
算法评价,T(n)=O(n2)
Ch6_3.c
例 1
65
4
3
2
6 5
1
3
5
6
6
4 2
5
1
3
1
1
6
3
1
4
1
6
4
3
1
4 2
1
1
6
4
3
2 1
4 2
5
1
65
4
3
2 1
4 2
5
3
1
0624
6063
2055
465051
3506
5160
0 1 2 3 4 5
0
1
2
3
4
5
1
-2
1
-4
1
-1
例 1
65
4
3
2
6 5
1
3
5
6
6
4 2
5
1
-5
1-3
1
65
4
3
2
6 5
1
3
5
6
6
4 2
5
1
65
4
3
2 1
4 2
5
3
方法二：克鲁斯卡尔 (Kruskal)算法
算法思想：设连通网 N=(V,{E}),令最小生成树
初始状态为只有 n个顶点而无边的非连通图 T=(V,{?})，每个顶点自成一个连通分量
在 E中选取代价最小的边，若该边依附的顶点落在 T中不同的连通分量上，则将此边加入到 T中；否则，舍去此边，选取下一条代价最小的边
依此类推，直至 T中所有顶点都在同一连通分量上为止例 1
65
4
3
2
6 5
1
3
5
6
6
4 2
5
1
65
4
3
2 1
23 4
5
（ 0）用顶点数组和边数组存放顶点和边信息
（ 1）初始时，令每个顶点的 jihe互不相同；每个边的 flag为 0
（ 2）选出权值最小且 flag为 0的边
（ 3）若该边依附的两个顶点的 jihe 值不同，即非连通，则令该边的 flag=1,选中该边；再令该边依附的两顶点的 jihe
以及两集合中所有顶点的 jihe 相同若该边依附的两个顶点的 jihe 值相同，即连通，则令该边的 flag=2,即舍去该边
（ 4）重复上述步骤，直到选出 n-1条边为止顶点结点：
typedef struct
{ int data; //顶点信息
int jihe;
}VEX;
边结点：
typedef struct
{ int vexh,vext; //边依附的两顶点
int weight; //边的权值
int flag; //标志域
}EDGE;
算法实现：
例 1
65
4
3
2
6 5
1
3
5
6
6
4 2
5
Ch6_30.c
算法描述：
data jihe
1
2
4
5
3
6
1
2
4
5
3
6
1
2
4
5
3
6
vexh weight
1
1
2
2
1
3
2
3
3
5
4
4
vext flag
6
1
5
3
5
5
0
0
0
0
0
0
0
1
3
4
2
5
6
7
8
9
3
3
4
5
5
6
6
6
6
4
2
6
0
0
0
0
1
1
1
1
1
4
2
1
1
1
2
2
2
2
21
65
4
3
2 1
23 4
5
