第 7章 图
数据结构（ C++描述）
目录
7.6拓扑排序
7.1 图的基本概念
7.2 图的存贮结构
7.3 图的遍历
7.4 生成树和最小生成树
7.5最短路径
退出
7.1 图的基本概念
7.1.1 图的定义
图是由顶点集 V和顶点间的关系集合 E（ 边的集合 ） 组成
的一种数据结构, 可以用二元组定义为,G=（ V,E） 。
例如, 对于图 7-1所示的无向图 G1和有向图 G2,它们的数
据结构可以描述为,G1=(V1,E1),其中
V1={a,b,c,d},E1={(a,b),(a,c),(a,d),(b,d),(c,d)},而 G2=(V2,E2),
其中 V2={1,2,3},E2={<1,2>,<1,3>,<2,3>,<3,1>}。
d A
A
c
A
b a
2 1
3
( a) 无向图 G1 (b) 有向图 G2
图 7 - 1 无向图和有向图
7.1.2 图的基本术语
1,有向图和无向图
在图中, 若用箭头标明了边是有方向性的, 则称这样的
图为有向图, 否则称为无向图 。 如图 7-1中, G1为无向图,
G2为有向图 。
在无向图中，一条边（ x,y）与（ y,x）表示的结果相同，
用圆括号表示，在有向图中，一条边 <x,y>与 <y,x>表示
的结果不相同，故用尖括号表示。 〈 x,y>表示从顶点 x发
向顶点 y的边,x为始点,y为终点。有向边也称为弧,x
为弧尾,y为弧头,则 〈 x,y>表示为一条弧,而 〈 y,x>表示 y
为弧尾,x为弧头的另一条弧 。
2,完全图、稠密图、稀疏图
具有 n个顶点, n(n-1)/2条边的图, 称为完全无向图, 具有
n个顶点, n(n-1) 条弧的有向图,称为完全有向图 。 完全无
向图和完全有向图都称为完全图 。
对于一般无向图, 顶点数为 n,边数为 e,则 0≤e ≤n(n-
1)/2。
对于一般有向图, 顶点数为 n,弧数为 e,则 0≤e≤n(n-
1) 。
当一个图接近完全图时, 则称它为稠密图, 相反地,
当一个图中含有较少的边或弧时, 则称它为稀疏图 。
3,度, 入度, 出度
在图中, 一个顶点依附的边或弧的数目, 称为该顶点的
度 。 在有向图中, 一个顶点依附的弧头数目, 称为该顶
点的入度 。 一个顶点依附的弧尾数目, 称为该顶点的出
度, 某个顶点的入度和出度之和称为该顶点的度 。
另外，若图中有 n个顶点,e条边或弧，第 i个顶点的度为 di，
则有 e=
21 ?
?
n
i
id
1
4,子图
若有两个图 G1和 G2,G1=(V1,E1),G2=(V2,E2),满足
如下条件,V2?V1, E2? E1,即 V2为 V1的子集, E2为
E1的子集, 称图 G2为图 G1的子图 。
图和子图的示例具体见图 7-2。
4 3
1 2
4 3
1 2
4
1 2
( a) 图 G ( b ) 图 G 的两个子图
图 7 - 2 图与子图示意
5,权
在图的边或弧中给出相关的数, 称为权 。 权可以代
表一个顶点到另一个顶点的距离, 耗费等, 带权图
一般称为网 。
带权图的示例具体见图 7-3。
(a ) 无向网 ( b ) 有向网
图 7 - 3 无向带权图和有向带权图
5
3
1 2
4
4
1
6
7
2
3
5
8
A B
C
2
1
5
3
4
6,连通图和强连通图
在无向图中，若从顶点 i到顶点 j有路径，则称顶点 i和
顶点 j是连通的。若任意两个顶点都是连通的，则称此
无向图为连通图，否则称为非连通图。
连通图和非连通图示例见图 7-4。
3
1 2
4
1
2
3
4 5
（ a ） 连通图 (b ) 非连通图
图 7 - 4 连通图和非连通图
在有向图中，若从顶点 i到顶点 j有路径，则称从顶点 i
和顶点 j是连通的，若图中任意两个顶点都是连通的，
则称此有向图为强连通图，否则称为非强连通图。
强连通图和非强连通图示例见图 7-5。
A B
D C
1 2
1
6 5 4
3
(a) 强连通图 ( b ) 非强连通图
图 7 - 5 强连通图和非强连通图
7,连通分量和强连通分量
无向图中, 极大的连通子图为该图的连通分量 。
显然, 任何连通图的连通分量只有一个, 即它本
身, 而非连通图有多个连通分量 。
对于图 7-4 中的非连通图，它的连通分量见图 7-6。
1 2
3
5 4
图 7 - 6 图 7 - 4(b) 的连通分量
有向图中, 极大的强连通子图为该 图的强连通分量 。
显然, 任何强连通图的强连通分量只有一个, 即它
本身, 而非强连通图有多个强连通分量 。
对于图 7-5 中的非强连通图，它的强连通分量见图 7-7。
6
3
5
图 7 - 7 图 7 - 5 ( b ) 的强连通分量
2 1
4
8．路径、回路
在无向图 G中, 若存在一个顶点序列 Vp,Vi1,Vi2,…, Vin，
Vq,使得 （ Vp,Vi1）,(Vi1,Vi2),…,.,(Vin,Vq)均属于 E（ G）,
则称顶点 Vp到 Vq存在一条路径 。 若一条路径上除起点和终
点可以相同外, 其余顶点均不相同, 则称此路径为简单路
径 。 起点和终点相同的路径称为回路, 简单路径组成的回
路称为简单回路 。 路径上经过的边的数目称为该路径的路
径长度 。
9,有根图
在一个有向图中, 若从顶点 V有路径可以到达图中的
其它所有顶点, 则称此有向图为有根图, 顶点 V称作
图的根 。
10,生成树、生成森林
连通图的生成树是一个极小连通子图, 它包含图中全部 n
个顶点和 n-1条不构成回路的边 。 非边通图的生成树则组
成一个生成森林 。 若图中有 n个顶点, m个连通分量, 则
生成森林中有 n-m条边 。
7.2 图的存贮结构
7.2.1 邻接矩阵
1,图的邻接矩阵表示
在邻接矩阵表示中, 除了存放顶点本身信息外, 还
用一个矩阵表示各个顶点之间的关系 。 若 （ i,j）
∈ E(G)或 〈 i,j〉 ∈ E(G),则矩阵中第 i行 第 j列元素值为
1,否则为 0 。
图的邻接矩阵定义为：
1 若 （ i,j） ∈ E(G)或 〈 i,j〉 ∈ E(G)
A[i][j]=
0 其它情形
例如,对图 7-8所示的无向图和有向图,它们的邻接矩阵
见图 7-9。
3
1
2
( a) 无向图 G 3 (b ) 有向图 G4
图 7 - 8 无向图 G3 及有向图 G4
1 2
4 3
0111
1010
1101
1010
001
100
110
( a ) G 3 的邻接矩阵 ( b ) G 4 的邻接矩
图 7 - 9 邻接矩阵表示
2,从无向图的邻接矩阵可以得出如下结论
（ 1） 矩阵是对称的 ;
（ 2） 第 i行或第 i 列 1的个数为顶点 i 的度 ;
（ 3） 矩阵中 1的个数的一半为图中边的数目 ;
（ 4） 很容易判断顶点 i 和顶点 j之间是否有边相连 (看
矩阵中 i行 j列值是否为 1)。
3,从有向图的邻接矩阵可以得出如下结论
（ 1） 矩阵不一定是对称的 ;
（ 2） 第 i 行中 1的个数为顶点 i 的出度 ;
（ 3） 第 i列中 1的个数为顶点 i的入度 ;
（ 4） 矩阵中 1的个数为图中弧的数目 ;
（ 5） 很容易判断顶点 i 和顶点 j 是否有弧相连,
4,网的邻接矩阵表示
类似地可以定义网的邻接矩阵为：
wij 若 （ i,j） ∈ E(G)或 〈 i,j〉 ∈ E(G)
A[i][j]= 0 若 i=j
∞ 其它情形
网及网的邻接矩阵见图 7-10。
?
??
??
??
??
7493
728
421
986
316
( a) 网 G5 ( b ) 网 G5 的邻接矩阵示意图
图 7 - 10 网及邻接矩阵示意图
5
3
1 2
4
3
6
1
2
4
8
9
7
5,图的邻接矩阵数据类型描述
图的邻接矩阵数据类型描述如下,
const int n= maxn； // 图中顶点数
const int e=maxe ； // 图中边数
struct graph
{
elemtype V[n+1]; // 存放顶点信息
v1,v2,…,vn,不使用 v[0]存储空间
int arcs[n+1][n+1] // 邻接矩阵
};
6,建立无向图的邻接矩阵
void creatadj(graph &g)
{ int i,j,k ;
for (k=1; k<=n; k++)
cin>>g.v[k]; //输入顶点信息
for (i=1; i<=n; i++ )
for (j=1; j<=n; j++)
g.arcs[i][j]=0;
for (k=1; k<=e; k++)
{ cin>>i>>j; //输入一条边 (i,j)
g.arcs[i][j]=1;g.arcs[j][i]=1;}}
该算法的时间复杂度为 O（ n2）。
7.建立有向图的邻接矩阵
void creatadj(graph &g)
{ int i,j,k ;
for (k=1; k<=n; k++)
cin>>g.v[k]; //输入顶点信息
for (i=1; i<=n; i++ )
for (j=1; j<=n; j++)
g.arcs[i][j]=0;
for (k=1; k<=e; k++)
{ cin>>i>>j; //输入一条弧 <i,j>
g.arcs[i][j]=1;}}
该算法的时间复杂度为 O（ n2） 。
8.建立无向网的邻接矩阵
void creatadj(graph &g)
{ int i,j,k ; float w;
for (k=1; k<=n; k++)
cin>>g.v[k]; //输入顶点信息
for (i=1; i<=n; i++ )
for (j=1; j<=n; j++)
if (i==j) g.arcs[i][j]=0; else g.arcs[i][j]=∞;
for (k=1; k<=e; k++)
{ cin>>i>>j>>w; //输入一条边 (i,j) 及权值 w
g.arcs[i][j]=w;g.arcs[j][i]=w;}}
该算法的时间复杂度为 O（ n2）。
9.建立有向网的邻接矩阵
void creatadj(graph &g)
{ int i,j,k ; float w;
for (k=1; k<=n; k++)
cin>>g.v[k]; //输入顶点信息
for (i=1; i<=n; i++ )
for (j=1; j<=n; j++)
if (i==j) g.arcs[i][j]=0; else g.arcs[i][j]=∞;
for (k=1; k<=e; k++)
{ cin>>i>>j>>w; //输入一条弧 <i,j> 及权值 w
g.arcs[i][j]=w;}}
该算法的时间复杂度为 O（ n2） 。
7.2.2 邻接表
1,图的邻接表表示
将每个结点的边用一个单链表链接起来, 若干个结点
可以得到若干个单链表, 每个单链表都有一个头结点,
所有头结点组成一个一维数组, 称这样的链表为邻接
表 。
例如，图 7-8所示的无向图 G3和有向图 G4的邻接表见
图 7-11所示
1
2
3
4
2 4 ^
1 3 4 ^
2 4 ^
1 2 3 ^
( a) 无向图 G3 的邻接表
1
2
3
2 3 ^
3 ^
1 ^
1
2
3
3 ^
1 ^
1 3 ^
( b ) 有向图 G4 的邻接表 (c) 有向图 G4 的逆邻接表
图 7 - 11 邻接表示例
1 2
4 3
2,从无向图的邻接表可以得到如下结论
（ 1） 第 i 个链表中结点数目为顶点 i的度；
（ 2） 所有链表中结点数目的一半为图中边数；
（ 3） 占用的存储单元数目为 n+2e 。
3,从有向图的邻接表可以得到如下结论
（ 1） 第 i 个链表中结点数目为顶点 i的出度；
（ 2） 所有链表中结点数目为图中弧数；
（ 3） 占用的存储单元数目为 n+e 。
从有向图的邻接表可知，不能求出顶点的入度。为此，
我们必须另外建立有向图的逆邻接表，以便求出每一
个顶点的入度。逆邻接表在图 7-11(c)中已经给出，从
该图中可知。有向图的逆邻接表与邻接表类似，只是
它是从入度考虑结点，而不是从出度考虑结点。
4,图的邻接表数据类型描述
图的邻接表数据类型描述如下：
const int n =maxn； // maxn表示图中最大顶点
数
const int e= maxe ； // maxe图中最大边数
struct link //定义链表类型
{ elemtype data ;
link *next ;};
struct node //定义邻接表的表头类型
{ elemtype v; //顶点信息
link *next;
}a[n+1];
5.无向图的邻接表建立
void creatlink( )
{ int i,j,k ; link *s ;
for(i=1; i<=n;i++) //建立邻接表头结点
{ a[i].v=i ; a[i].next=NULL; }
for(k=1; k<=e;k++)
{ cin>>i>>j ; //输入一条边 (i,j)
s=new link; //申请一个动态存储单元
s–>data=j ;
s->next=a[i].next ;a[i].next=s ;
s=new link; s->data=i ;
s->next=a[j].next ;a[j].next=s ;}}
该算法的时间复杂度为 O（ n+e）。
6.有向图的邻接表建立
void creatlink( )
{ int i,j,k ; link *s ;
for(i=1; i<=n;i++) //建立邻接表头结点
{ a[i].v=i ; a[i].next=NULL; }
for(k=1; k<=e;k++)
{ cin>>i>>j ; //输入一条边 <i,j>
s=new link; //申请一个动态存储单元
s–>data=j ;s->next=a[i].next ;
a[i].next=s ;}}
该算法的时间复杂度为 O（ n+e） 。
7.网的邻接表的数据类型描述
网的邻接表的数据类型可描述如下：
const int n =maxn； // maxn表示网中最大顶点数
const int e= maxe ； // maxe网中最大边数
struct link //定义链表类型
{ elemtype data ;
float w; //定义网上的权值类型为浮点型
link *next ;};
struct node //定义邻接表的表头类型
{ elemtype v; //顶点信息
link *next;
}a[n+1];
8,无向网的邻接表建立
void creatlink( )
{ float w; int i,j,k ; link *s ;
for(i=1; i<=n;i++) //建立邻接表头结点
{ a[i].v=i ; a[i].next=NULL; }
for(k=1; k<=e;k++)
{ cin>>i>>j>>w ; //输入一条边 (i,j)及该边上的权值
s=new link; //申请一个动态存储单元
s–>data=j ;s->w=w;
s->next=a[i].next ;a[i].next=s ;s=new link;
s->data=i ;s->w=w;s->next=a[j].next ;
a[j].next=s ;}}
该算法的时间复杂度为 O（ n+e） 。
9,有向网的邻接表建立
void creatlink( )
{ float w;int i,j,k ; link *s ;
for(i=1; i<=n;i++) //建立邻接表头结点
{ a[i].v=i ; a[i].next=NULL; }
for(k=1; k<=e;k++)
{ cin>>i>>j>>w ; //输入一条弧 <i,j>及该弧上的权值
s=new link; //申请一个动态存储单元
s–>data=j ;s->w=w;
s->next=a[i].next ;
a[i].next=s ;}}
该算法的时间复杂度为 O（ n+e） 。
另外, 请注意上面的算法中, 建立的邻接表不是唯一
的,与你从键盘输入边的顺序有关, 输入的边的顺序不
同, 则得到的链表也不同 。
7.2.3 邻接多重表
在无向图的邻接表中, 每条边 （ Vi,Vj） 由两个结点表示,
一个结点在第 i个链表中, 另一个结点在第 j个链表中, 当
需要对边进行操作时, 就需要找到表示同一条边的两个
结点, 这给操作带来不便, 在这种情况下采用邻接多重
表较方便 。
在邻接多重表中，每条边用一个结点表示，每个结点由
五个域组成，其结点结构为,
M a r k i n e x t 1 j n e x t 2
其中 mark为标志域, 用来标记这条边是否被访问过,
i和 j域为一条边的两个顶点, next1 和 next2为两个指
针域, 分别指向依附于 i顶点的下一条边和 j顶点的下
一条边 。 而表头与邻接表的表头类似 。
邻接多重表的形式见图 7-12。
1 3
4 2
(a) 无向图 G6 （ b ） G6 的邻接多重表
图 7 - 12 邻接多重表示例
1
2
3
4 2 ^ 4 ^
1 ^ 3 ^
1 2
7.3 图的遍历
和树的遍历类似, 图的遍历也是从某个顶点出发, 沿
着某条搜索路径对图中所有顶点各作一次访问 。 若给
定的图是连通图, 则从图中任一顶点出发顺着边可以
访问到该图中所有的顶点, 但是, 在图中有回路, 从
图中某一顶点出发访问图中其它顶点时, 可能又会回
到出发点, 而图中可能还剩余有顶点没有访问到, 因
此, 图的遍历较树的遍历更复杂 。 我们可以设置一个
全局型标志数组 visited来标志某个顶点是否被访过,
未访问的值为 0,访问过的值为 1。 根据搜索路径的方
向不同, 图的遍历有两种方法：深度优先搜索遍历和
广度优先搜索遍历 。
7.3.1深度优先搜索遍历
1,深度优先搜索思想
深度优先搜索遍历类似于树的先序遍历 。 假定给定
图 G的初态是所有顶点均未被访问过, 在 G中任选一
个顶点 i作为遍历的初始点, 则深度优先搜索遍历可
定义如下：
(1) 首先访问顶点 i,并将其访问标记置为访问过,
即 visited[i]=1；
(2) 然后搜索与顶点 i有边相连的下一个顶点 j,若 j
未被访问过, 则访问它, 并将 j的访问标记置为访问
过, visited[j]=1,然后从 j开始重复此过程, 若 j已访
问, 再看与 i有边相连的其它顶点；
(3) 若与 i有边相连的顶点都被访问过, 则退回到前
一个访问顶点并重复刚才过程, 直到图中所有顶点
都被访问完止 。
例如, 对图 7-13所示无向图 G7,从顶点 1出发的深
度优先搜索遍历序列可有多种, 下面仅给出三种,
其它可作类似分析 。
在无向图 G7中，从顶点 1出发的深度优先搜索遍历
序列举三种为：
1,2,4,8,5,6,3,7
1,2,5,8,4,7,3,6
1,3,6,8,7,4,2,5
3
1
2
4
5
7
6
8
7 - 1 3 无向图 G 7
2,连通图的深度优先搜索
若图是连通的或强连通的, 则从图中某一个顶点出发可
以访问到图中所有顶点, 否则只能访问到一部分顶点 。
另外，从刚才写出的遍历结果可以看出，从某一个顶
点出发的遍历结果是不唯一的。但是,若我们给定图的
存贮结构,则从某一顶点出发的遍历结果应是唯一的。
(1) 用邻接矩阵实现图的深度优先搜索
以图 7-13中无向图 G7 为例, 来说明算法的实现, G7的
邻接矩阵见图 7-14。
01111000
10000100
10000100
10000010
10000010
01100001
00011001
00000110
图 7 - 14 无向图 G 7 的邻接矩阵
3
1
2
4
5
7
6
8
7 - 1 3 无向图 G 7
算法描述为下面形式：
void dfs (int i) // 从顶点 i
出发遍历
{ int j;
cout<<g.v[i]; //输出访问
顶点
visited[i]=1; //全局数组访
问标记置 1表示已经访问
for(j=1; j<=n; j++)
if ((g.arcs[i ][j]= =1)&&(!visited[j]))
dfs(j); }
用上述算法和无向图 G7,可以描述从顶点 1出发的深
度优先搜索遍历过程, 示意图见图 7-15,其中实线表
示下一层递归调用, 虚线表示递归调用的返回 。
从图 7-15中, 可以得到从顶点 1的遍历结果为 1,2,4,8,
5,6,3,7。 同样可以分析出从其它顶点出发的遍历结果 。
D F S (1) D F S (2) D F S (4) D F S (8) D F S (5)
D F S (6) D F S (3) D F S (7)
图 7 - 15 邻接矩阵深度优先搜索示意图
(2)用邻接表实现图的深度优先搜索
仍以图 7-13中无向图 G7 为例，来说明算法的实现,G7
的邻接表见图 7-16，
3
1
2
4
5
7
6
8
7 - 1 3 无向图 G 7
1
2
3
4
5
6
7
8
2 3 ^
1 4
1 6
2 8 ^
2 8 ^
3 8 ^
3 8 ^
4 5 6
7 ^
7 ^
5 ^
图 7 - 16 G 7 的邻接表
算法描述为下面形式：
void dfs1(int i)
{ link *p; cout<<a[i].v ; //输出访问顶点
visted[i]=1; //全局数组访问标记置为 1表示
已访问
p=a[i].next;
while (p!=NULL)
{ if (!visited[p->data])
dfs1(p->data);p=p->next;
}
}
用刚才算法及图 7-16,可以描述从顶点 7出发的深度优
先搜索遍历示意图, 见图 7-17,其中实线表示下一层递
归, 虚线表示递归返回, 箭头旁边数字表示调用的步
骤 。
于是, 从顶点 7出发的深度优先搜索遍历序列, 从图 7-
17中可得出为 7,3,1,2,4,8,5,6。 从其它
顶点出发的深度优先搜索序列, 请读者自已写出 。
D F S 1(7) D F S 1(3) D F S 1(1) D F S 1(2) D F S 1(4)
D F S 1(8)
D F S 1(5)
D F S 1(6)
2 1
14 13 12
11 10
3 4 5 6
9
8
7
7 - 17 邻接表深度优先搜索示意图
3．非连通图的深度优先搜索
若图是非连通的或非强连通图, 则从图中某一个顶点出
发 。 不能用深度优先搜索访问到图中所有顶点, 而只能
访问到一个连通子图 （ 既连通分量 ） 或只能访问到一个
强连通子图 （ 既强连通分量 ） 。 这时, 可以在每个连通
分量或每个强连通分量中都选一个顶点, 进行深度优先
搜索遍历, 最后将每个连通分量或每个强连通分量的遍
历结果合起来, 则得到整个非连通图的遍历结果 。
遍历算法实现与连通图的只有一点不同, 即对所有顶点
进行循环, 反复调用连通图的深度优先搜索遍历算法即
可 。 具体实现如下：
for(int i=1;i<=n;i++)
if(!visited[i])
dfs(i) ;
for(int i=1;i<=n;i++)
if(!visited[i])
dfs1(i);
或者
7.3.2 广度优先搜索遍历
1,广度优先搜索的思想
广度优先搜索遍历类似于树的按层次遍历 。 设图 G的初
态是所有顶点均未访问, 在 G 中任选一顶点 i作为初始点,
则广度优先搜索的基本思想是：
(1) 首先访问顶点 i,并将其访问标志置为已被访问,
即 visited[i]=1；
(2) 接着依次访问与顶点 i有边相连的所有顶点 W1，
W2,…, Wt；
(3) 然后再按顺序访问与 W1,W2,…, Wt有边相连又
未曾访问过的顶点；
依此类推，直到图中所有顶点都被访问完为止 。
例如, 对图 7-13所示无向图 G7,从顶点 1出发的广
度优先搜索遍历序列可有多种, 下面仅给出三种,
其它可作类似分析 。
在无向图 G7中, 从顶点 1出发的广度优先搜索遍历序列
举三种为：
1,2,3,4,5,6,7,8
1,3,2,7,6,5,4,8
1,2,3,5,4,7,6,8
3
1
2
4
5
7
6
8
7 - 1 3 无向图 G 7
2,连通图的广度优先搜索
(1) 用邻接矩阵实现图的广度优先搜索遍历
仍以图 7-13中无向图 G7及 7-14所示的邻接矩阵来说明对
无向图 G7的遍历过程
3
1
2
4
5
7
6
8
7 - 1 3 无向图 G 7
01111000
10000100
10000100
10000010
10000010
01100001
00011001
00000110
图 7 - 14 无向图 G 7 的邻接矩阵
根据该算法用及图 7-14中的邻接矩阵, 可以得到图 7-13
的无向图 G7 的广度优先搜索序列, 若从顶点 1 出发, 广
度优先搜索序列为,1,2,3,4,5,6,7,8。 若从顶
点 3出发, 广度优先搜索序列为,3,1,6,7,2,8，
4,5,从其它点出发的广度优先搜索序列可根据同样类似
方法分析 。
算法描述如下：
void bfs( int i) //从顶点 i出发遍历
{ int Q[n+1] ; //Q为队列
int f,r,j ; // f,r分别为队列头, 尾指针
f=r=0 ; //设置空队列
cout<<g.v[i] ; // 输出访问顶点
visited[i]=1 ; //全局数组标记置 1表示已经访问
r++; q[r]=i ; //入队列
while (f<r) { f++; i=q[f] ; //出队列
for (j=1; j<=n; j++)
if ((g.arcs[i][j]==1)&&(!visited[j]))
{ cout<<g.v[j] ; visited[j]=1 ; r++; q[r]=j ;} } }
（ 2） 用邻接表实现图的广序优先搜索遍历
仍以无向图 G7及图 7-16所示邻接表来说明邻接表上实
现广度优先搜索遍历的过程
3
1
2
4
5
7
6
8
7 - 1 3 无向图 G 7
1
2
3
4
5
6
7
8
2 3 ^
1 4
1 6
2 8 ^
2 8 ^
3 8 ^
3 8 ^
4 5 6
7 ^
7 ^
5 ^
图 7 - 16 G 7 的邻接表
根据该算法及图 7-16,可以得到图 G7的广度优先搜索序
列, 若从顶点 1出发, 广度优先搜索序列为,1,2,3，
4,5,6,7,8,若从顶点 7出发, 广度优先搜索序列为：
7,3,8,1,6,4,5,2,从其它顶点出发的广度优先
搜索序列可根据同样类似方法分析 。
算法描述如下：
void BFS1(int i)
{ int q[n+1] ; //定义队列
int f,r ; link *p ; //P为搜索指针
f=r=0 ; cout<<a[i].v ;
visited[i]=1 ; r++; q[r]=i ; //进队
while (f<r)
{ f++ ; i=q[f] ; //出队 p=a[i].next ;
while (p!=NULL)
{ if (!visited[p->data]){ cout<<a[p->data].v;
visited[p->data]=1 ; r++;q[r]=p->data ;}
p=p->next;}} }
3.非连通图的广度优先搜索
若图是非连通的或非强连通图, 则从图中某一个顶点
出发 。 不能用广度优先搜索遍历访问到图中所有顶点,
而只能访问到一个连通子图 （ 既连通分量 ） 或只能访
问到一个强连通子图 （ 既强连通分量 ） 。 这时, 可以
在每个连通分量或每个强连通分量中都选一个顶点,
进行广度优先搜索遍历, 最后将每个连通分量或每个
强连通分量的遍历结果合起来, 则得到整个非连通图
或非强连通图的广度优先搜索遍历序列 。
遍历算法实现与连通图的只有一点不同, 即对所有顶
点进行循环, 反复调用连通图的广度优先搜索遍历算
法即可 。 具体可以表示如下：
for(int i=1;i<=n;i++) for(int i=1;i<=n;i++)
if(!visited[i]) 或 if(!visited[i])
bfs(i) ; bfs1(i);
7.4 生成树和最小生成树
7.4.1 基本概念
1,生成树
在图论中，常常将树定义为一个无回路连通图。例如，
图 7-18中的两个图就是无回路的连通图。乍一看它似乎不
是不是树，但只要选定某个顶点做根并以树根为起点对
每条边定向，就可以将它们变为通常的树。
3
1 2
4 5
1 2
4 3
5
7 - 1 8 两个无回路的连通图
在一个连通图中, 有 n个顶点, 若存在这样一个子图,
含有 n个顶点, n-1条不构成回路的边, 则这个子图称
为生成树, 或者定义为：一个连通图 G的子图如果是
一棵包含 G的所有顶点的树, 则该子图为图 G 的生成
树 。
由于 n个顶点的连通图至少有 n-1条边，而所有包含 n-1
条边及 n个顶点的连通图都是无回路的树，所以生成树
是连通图中的极小连通子图，所谓极小是指边数最少，
若在生成树中去掉任何一条边，都会使之变为非连通图，
若在生成树上任意增加一条边，就会构成回路。那么，
对给定的连通图，如何求得它的生成树呢？回到我们前
面提到的图的遍历，访问过图中一个顶点后，要访问下
一个顶点,一般要求两个顶点有边相连，即必须经过
图中的一条边，要遍历图中 n 个顶点且每个顶点都只遍
历一次，则必须经过图中的 n-1条边，这 n-1条边构成连
通图的一个极小连通子图，所以它是连通图的生成树，
由于遍历结果可能不唯一，所以得到的生成树也是不唯
一的。
要求得生成树, 可考虑用刚才讲过的深度优先搜索遍
历算法及广度优先搜索遍历算法 。 对于深度优先搜索
算法 DFS或 DFS1,由 DFS（ i） 递归到 DFS（ j）, 中间
必经过一条边 （ i,j）, 因此, 只需在 DFS(j)调用前输出
这条边或保存这条边, 即可求得生成树的一条边, 整
个递归完成后, 则可求得生成树的所有边 。 对于广度
优先搜索算法 BFS或 BFS1,若 i 出队, j 入队, 则 (i,j)为
一条树边 。 因此, 可以在算法的 if 语句中输出这条边,
算法完成后, 将会输出 n-1条边, 也可求得生成树 。 由
深度优先搜索遍历得到的生成树, 称为深度优先生成
树, 由广度优先搜索遍历得到的生成树, 称为广度优
先生成树 。 图 7-13中无向图 G7的两种生成树见 图 7-19。
若一个图是强连通的有向图, 同样可以得到它的生成
树 。 生成树可以利用连通图的深度优先搜索遍历或连
通图的广度优先搜索遍历算法得到 。
1
4
2
5
3
6
8
7
2
7 6
8
3
5
4
1
(a) 深度优先生成树 (b ) 广度优先生成树
图 7 - 1 9 两种生成树示意图
3
1
2
4
5
7
6
8
7 - 1 3 无向图 G 7
2．生成森林
若一个图是非连通图或非强连通图, 但有若干个连通分量
或若干个强连通分量, 则通过深度优先搜索遍历或广度优
先搜索遍历, 不可以得到生成树, 但可以得到生成森林,
且若非连通图有 n 个顶点, m 个连通分量或强连通分量,
则可以遍历得到 m棵生成树, 合起来为生成森林, 森林中
包含 n-m条树边 。
生成森林可以利用非连通图的深度优先搜索遍历或非连通
图的广度优先搜索遍历算法得到 。
3,最小生成树
在一般情况下, 图中的每条边若给定了权, 这时, 我们
所关心的不是生成树, 而是生成树中边上权值之和 。 若
生成树中每条边上权值之和达到最小, 称为最小生成树 。
下面将介绍求最小生成树的两种方法：普里姆算法和克
鲁斯卡尔算法 。
7.4.2 普里姆算法
1,普里姆 (prim)算法思想
下面仅讨论无向网的最小生成树问题 。
普里姆方法的思想是：在图中任取一个顶点 K作为开始点，
令 U={k},W=V-U，其中 V为图中所有顶点集，然后找一
个顶点在 U中，另一个顶点在 W中的边中最短的一条，找
到后，将该边作为最小生成树的树边保存起来，并将该边
顶点全部加入 U集合中，并从 W中删去这些顶点，然后重
新调整 U中顶点到 W中顶点的距离,使之保持最小，再重
复此过程，直到 W为空集止。求解过程参见图 7-20 。
假设开始顶点就选为顶点 1,故首先有 U={1},W={2，
3,4,5,6}
( a ) 无向网 ( b ) u = { 1 } w = { 2,3,4,5,6 }
6
4
1
2
4
6
3
6
2
1
3
5
7
6
5
5
5
1
2
3
4
5
6
6
?
5
1 ?
3
1
2
4
6
5 6
1
4
5
5
5
3
1
2
4
6
5 6
4
2
1
5
5
(c ) u ={ 1,3} w ={ 2,4,5,6} (d ) u ={ 1,3,6 } w ={ 2,4,5 }
3
1
2
4
6
5 6
4
2
1
5
5
( e) u ={ 1,3,6,4 } w ={ 2,5 } ( f ) u ={ 1,3,6,4,2 } w ={ 5 }
1
2
4
6
3
5
6
4
2
1
5
3
(g) u={1,3,6,4,2,5} w ={ }
5
4
2
1
3
1
2
4
6
3
5
6
图 7 - 20 prim 方法构造最小生成树的过程
7.4.3 克鲁斯卡尔 （ kruskal） 算法
1,克鲁斯卡尔算法基本思想
克鲁斯卡尔算法的基本思想是：将图中所有边按权值递
增顺序排列，依次选定取权值较小的边，但要求后面选
取的边不能与前面选取的边构成回路，若构成回路，则
放弃该条边，再去选后面权值较大的边,n个顶点的图中，
选够 n-1条边即可。
例如，对图 7-20（ a） 中无向网，用克鲁斯卡尔算法求
最小生成树的过程见图 7-22。
2
4
6
5
6
1
3
1
2
5
1
3
1
4
6
2
6
(a) 选第 1 条边 ( b ) 选第 2 条边
(c ) 选第 3 条边 (d ) 选第 4 条边
2
3
5
1
3
1
4
6
2
6
4
2
1
2
3
5
1
4
6
3
6
1
2
4
6
3
5 6
4
2
1
3
5
(e ) 选第 5 条边 ( 不能选（ 1,4 ）边，会构成回路，但可选（ 2,3 ）或 (5,3) 中之一 )
5
1
2
4
6
3
6
4
2
1
3 5
或者
图 7 - 22 克鲁斯卡尔方法求最小生成树的过程
7.5最短路径
交通网络中常常提出这样的问题：从甲地到乙地之间
是否有公路连通?在有多条通路的情况下, 哪一条路最
短? 交通网络可用带权图来表示 。 顶点表示城市名称,
边表示两个城市有路连通, 边上权值可表示两城市之
间的距离, 交通费或途中所花费的时间等 。 求两个顶
点之间的最短路径, 不是指路径上边数之和最少, 而
是指路径上各边的权值之和最小 。
另外, 若两个顶点之间没有边, 则认为两个顶点无通
路, 但有可能有间接通路 (从其它顶点达到 )。 路径上的
开始顶点 (出发点 )称为源点, 路径上的最后一个顶点称
为终点, 并假定讨论的权值不能为负数 。
7.5.1单源点最短路径
1,单源点最短路径
单源点最短路径是指：给定一个出发点 (单源点 )和一个
有向网 G=(V,E),求出源点到其它各顶点之间的最短路径 。
那么怎样求出单源点的最短路径呢?我们可以将源点到终
点的所有路径都列出来,然后在里面选最短的一条即可 。
但是这样做,用手工方式可以,当路径特别多时,显得特别
麻烦,并且没有什么规律,不能用计算机算法实现 。
迪杰斯特拉 (Dijkstra)在做了大量观察后,首先提出了按路
长度递增序产生各顶点的最短路径算法,我们称之为迪杰
斯特拉算法 。
2,迪杰斯特拉算法的基本思想
算法的基本思想是,设置并逐步扩充一个集合 S，存放已
求出其最短路径的顶点，则尚未确定最短路径的顶点集
合是 V-S，其中 V为网中所有顶点集合。按最短路径长度
递增的顺序逐个以 V-S中的顶点加到 S中，直到 S中包含全
部顶点，而 V-S为空。
具体做法是,设源点为 Vl,则 S中只包含顶点 Vl，令 W=V-S，则
W中包含除 Vl外图中所有顶点,Vl对应的距离值为 0,W中
顶点对应的距离值是这样规定的：若图中有弧 <Vl,Vj>则 Vj
顶点的距离为此弧权值，否则为 ∞(一个很大的数 )，然后每
次从 W中的顶点中选一个其距离值为最小的顶点 Vm加入到 S
中，每往 S中加入一个顶点 Vm，就要对 W中的各个顶点的距
离值进行一次修改。若加进 Vm做中间顶点，使
<Vl,Vm>+<Vm,Vj>的值小于 <Vl,Vj>值，则用
<Vl,Vm>+<Vm,Vj>代替原来 Vj的距离，修改后再在 W中选
距离值最小的顶点加入到 S中，如此进行下去，直到 S中包含
了图中所有顶点为止
迪杰斯特拉算法的求解过程
10
3
5
20
8
25
4
30 3
30
1
2
3
5
4
?
?
(a) 一个有向网点 (b) 源点 1 到其它顶点的初始距离
1
2
3
5
4
12
3
8
25
30
1
2
3
5
4
(c) 第一次求得的结果 (d) 第二次求得的结果
3
8
12
4
1
2
3
5
4
3
8
12
4
3
8
12
4
(e) 第三次求得的结果 (f) 第四次求得的结果
1
2
3
5
4
1
2
3
5
4
图 7 - 27 迪杰斯特拉算法求最短路径过程及结果
7.5.2所有顶点对之间的最短路径
1,顶点对之间的最短路径概念
所有顶点对之间的最短路径是指：对于给定的有向网
G=(V,E),要对 G中任意一对顶点有序对 V,W(V≠W),找出 V
到 W的最短距离和 W到 V的最短距离 。
解决此问题的一个有效方法是,轮流以每一个顶点为源点,
重复执行迪杰斯特拉算法 n次,即可求得每一对顶点之间的
最短路径,总的时间复杂度为 O(n3)。
下面将介绍用弗洛伊德 (Floyd)算法来实现此功能,时
间复杂度仍为 O(n3),但该方法比调用 n次迪杰斯特拉
方法更直观一些 。
2,弗洛伊德算法的基本思想
弗洛伊德算法仍然使用前面定义的图的邻接矩阵
arcs[n+1][n+1]来存储带权有向图。算法的基本思想是,设置
一个 nxn的矩阵 A(k)，其中除对角线的元素都等于 0外，其它
元素 a(k)[i][j]表示顶点 i到顶点 j的路径长度,K表示运算步骤。
开始时，以任意两个顶点之间的有向边的权值作为路径长度，
没有有向边时，路径长度为 ∞，当 K=O时,A (0)[i][j]=arcs[i][j],
以后逐步尝试在原路径中加入其它顶点作为中间顶点, 如果
增加中间顶点后, 得到的路径比原来的路径长度减少了, 则
以此新路径代替原路径, 修改矩阵元素 。 具体做法为：
第一步, 让 所 有 边 上 加 入 中 间 顶 点 1, 取 A[i][j] 与
A[i][1]+A[1][j]中较小的值作 A[i][j]的值, 完成后得到 A(1)，
因此, 弗洛伊德算法可以描述为,
A(0)[i][j]=arcs[i][j]; //arcs为图的邻接矩阵
A(k)[i][j]=min{A(k-1) [i][j],A(k-1) [i][k]+A(k-1) [k][j]}
其中 k=1,2,…,n
第二步, 让所有边上加入中间顶点 2,取 A[i][j]与
A[i][2]+A[2][j]中较小的值, 完成后得到 A(2)…, 如此
进行下去, 当第 n步完成后, 得到 A(n),A(n)即为我们所
求结果,A(n)[i][j]表示顶点 i到顶点 j的最短距离 。
3,弗洛伊德算法实现
在用弗洛伊德算法求最短路径时,为方便求出中间经
过的路径,增设一个辅助二维数组 path[n+1][n+1],其
中 path[i][j]是相应路径上顶点 j的前一顶点的顶点号 。
算法描述如下：
Void floyd ( const int n)
{ for (int i=1;i<=n;i++)
for (int j=1;j<=n; j++)
{ a[i][j]=arcs[i][j]
if(i!=j)&&(a[i][j]<∞)
path[i][j]=i;else path[i][j]=0;
}
for (int k=1; k<=n;k++)
for i=1;i<=n;i++)
for (j=1;j<=n;j++)
if (a[i][k]+a[k][j]<a[i][j])
{a[i][j]=a[i][k]+a[k][j]; path[i][j]=path[k][j];}
for (i=1;i<=n;i++) //输出路径长度及路径
for (j=1;j<=n;j++)
{ if(i!=j) {cout<<a[i][j]<<“:” ;
int next=path[i][j]; cout<<j;
while (next !=i)
{ cout<<“←”<<next ; next=path[i][next];}
cout<<“←”<<i<<endl ;}}}
7.6拓扑排序
7.6.1 实现规则
1,基本概念
通常我们把计划、施工过程、生产流程、程序流程等都当
成一个工程，一个大的工程常常被划分成许多较小的子工
程，这些子工程称为活动，这些活动完成时，整个工程也
就完成了。例如，计算机专业学生的课程开设可看成是一
个工程，每一门课程就是工程中的活动，图 7-30给出了若
干门所开设的课程，其中有些课程的开设有先后关系，有
些则没有先后关系，有先后关系的课程必须按先后关系开
设，如开设数据结构课程之前必须先学完程序设计基础及
离散数学，而开设离散数学则必须先并行学完高等数学、
程序设计基础课程。 ……………….,….,
课程代码 课程名称 先修课程
C1 高等数学
C2 程序设计基础
C3 离散数学 C 1,C 2
C4 数据结构 C 2,C 3
C5 高级语言程序设计 C2
C6 编译方法 C 5,C 4
C7 操作系统 C 4,C 9
C8 普遍物理 C1
C9 计算机原理 C8
( a) 课程开设 ( b) 课程开设优先关系的有向图
图 7 - 3 0 学生课程开 设工程图
C8
C6
C5
C4 C3
C2
C1
C9
C7
在图 7-30(b)中, 我们用一种有向图来表示课程开设,
在这种有向图中, 顶点表示活动, 有向边表示活动
的优先关系, 这有向图叫做顶点表示活动的网络
(Actire On Vertices)简称为 AOV网 。
在 AOV网中,<i,j>有向边表示 i活动应先于 j活动开始，
即 i活动必须完成后,j活动才可以开始，并称 i为 j的直接
前驱,j为 i的直接后继。这种前驱与后继的关系有传递
性，此外，任何活动 i不能以它自己作为自己的前驱或后
继，这叫做反自反性。从前驱和后继的传递性和反自反
性来看,AOV网中不能出现有向回路 (或称有向环 )。在
AOV网中如果出现了有向环，则意味着某项活动应以自
己作为先决条件，这是不对的，工程将无法进行。对程
序流程而言，将出现死循环。
因此, 对给定的 AOV网, 应先判断它是否存在有向
环 。 判断 AOV网是否有有向环的方法是对该 AOV网
进行拓扑排序, 将 AOV网中顶点排列成一个线性有
序序列, 若该线性序列中包含 AOV网全部顶点, 则
AOV网无环, 否则, AOV网中存在有向环, 该 AOV
网所代表的工程是不可行的 。
2,拓扑排序
下面将介绍怎样实现拓扑排序,实现步骤如下：
（ 1） 在 AOV网中选一个入度为 0的顶点且输出之；
（ 2） 从 AOV网中删除此顶点及该顶点发出来的所有有
向边；
（ 3） 重复 （ 1）, （ 2） 两步, 直到 AOV网中所有顶点
都被输出或网中不存在入度为 0的顶点 。
从拓扑排序步骤可知, 若在第 3步中, 网中所有顶点都
被输出, 则表明网中无有向环, 拓扑排序成功 。 若仅
输出部分顶点, 网中已不存在入度为 0的顶点, 则表明
网中有有向环, 拓扑排序不成功 。 例如, 对图 7-31中
AOV网, 可以得到的拓扑序列有,1,2,3,4,5或 2,1,3,4,5。
因此, 一个 AOV网的拓扑序列是不唯一的 。
数据结构（ C++描述）
目录
7.6拓扑排序
7.1 图的基本概念
7.2 图的存贮结构
7.3 图的遍历
7.4 生成树和最小生成树
7.5最短路径
退出
7.1 图的基本概念
7.1.1 图的定义
图是由顶点集 V和顶点间的关系集合 E（ 边的集合 ） 组成
的一种数据结构, 可以用二元组定义为,G=（ V,E） 。
例如, 对于图 7-1所示的无向图 G1和有向图 G2,它们的数
据结构可以描述为,G1=(V1,E1),其中
V1={a,b,c,d},E1={(a,b),(a,c),(a,d),(b,d),(c,d)},而 G2=(V2,E2),
其中 V2={1,2,3},E2={<1,2>,<1,3>,<2,3>,<3,1>}。
d A
A
c
A
b a
2 1
3
( a) 无向图 G1 (b) 有向图 G2
图 7 - 1 无向图和有向图
7.1.2 图的基本术语
1,有向图和无向图
在图中, 若用箭头标明了边是有方向性的, 则称这样的
图为有向图, 否则称为无向图 。 如图 7-1中, G1为无向图,
G2为有向图 。
在无向图中，一条边（ x,y）与（ y,x）表示的结果相同，
用圆括号表示，在有向图中，一条边 <x,y>与 <y,x>表示
的结果不相同，故用尖括号表示。 〈 x,y>表示从顶点 x发
向顶点 y的边,x为始点,y为终点。有向边也称为弧,x
为弧尾,y为弧头,则 〈 x,y>表示为一条弧,而 〈 y,x>表示 y
为弧尾,x为弧头的另一条弧 。
2,完全图、稠密图、稀疏图
具有 n个顶点, n(n-1)/2条边的图, 称为完全无向图, 具有
n个顶点, n(n-1) 条弧的有向图,称为完全有向图 。 完全无
向图和完全有向图都称为完全图 。
对于一般无向图, 顶点数为 n,边数为 e,则 0≤e ≤n(n-
1)/2。
对于一般有向图, 顶点数为 n,弧数为 e,则 0≤e≤n(n-
1) 。
当一个图接近完全图时, 则称它为稠密图, 相反地,
当一个图中含有较少的边或弧时, 则称它为稀疏图 。
3,度, 入度, 出度
在图中, 一个顶点依附的边或弧的数目, 称为该顶点的
度 。 在有向图中, 一个顶点依附的弧头数目, 称为该顶
点的入度 。 一个顶点依附的弧尾数目, 称为该顶点的出
度, 某个顶点的入度和出度之和称为该顶点的度 。
另外，若图中有 n个顶点,e条边或弧，第 i个顶点的度为 di，
则有 e=
21 ?
?
n
i
id
1
4,子图
若有两个图 G1和 G2,G1=(V1,E1),G2=(V2,E2),满足
如下条件,V2?V1, E2? E1,即 V2为 V1的子集, E2为
E1的子集, 称图 G2为图 G1的子图 。
图和子图的示例具体见图 7-2。
4 3
1 2
4 3
1 2
4
1 2
( a) 图 G ( b ) 图 G 的两个子图
图 7 - 2 图与子图示意
5,权
在图的边或弧中给出相关的数, 称为权 。 权可以代
表一个顶点到另一个顶点的距离, 耗费等, 带权图
一般称为网 。
带权图的示例具体见图 7-3。
(a ) 无向网 ( b ) 有向网
图 7 - 3 无向带权图和有向带权图
5
3
1 2
4
4
1
6
7
2
3
5
8
A B
C
2
1
5
3
4
6,连通图和强连通图
在无向图中，若从顶点 i到顶点 j有路径，则称顶点 i和
顶点 j是连通的。若任意两个顶点都是连通的，则称此
无向图为连通图，否则称为非连通图。
连通图和非连通图示例见图 7-4。
3
1 2
4
1
2
3
4 5
（ a ） 连通图 (b ) 非连通图
图 7 - 4 连通图和非连通图
在有向图中，若从顶点 i到顶点 j有路径，则称从顶点 i
和顶点 j是连通的，若图中任意两个顶点都是连通的，
则称此有向图为强连通图，否则称为非强连通图。
强连通图和非强连通图示例见图 7-5。
A B
D C
1 2
1
6 5 4
3
(a) 强连通图 ( b ) 非强连通图
图 7 - 5 强连通图和非强连通图
7,连通分量和强连通分量
无向图中, 极大的连通子图为该图的连通分量 。
显然, 任何连通图的连通分量只有一个, 即它本
身, 而非连通图有多个连通分量 。
对于图 7-4 中的非连通图，它的连通分量见图 7-6。
1 2
3
5 4
图 7 - 6 图 7 - 4(b) 的连通分量
有向图中, 极大的强连通子图为该 图的强连通分量 。
显然, 任何强连通图的强连通分量只有一个, 即它
本身, 而非强连通图有多个强连通分量 。
对于图 7-5 中的非强连通图，它的强连通分量见图 7-7。
6
3
5
图 7 - 7 图 7 - 5 ( b ) 的强连通分量
2 1
4
8．路径、回路
在无向图 G中, 若存在一个顶点序列 Vp,Vi1,Vi2,…, Vin，
Vq,使得 （ Vp,Vi1）,(Vi1,Vi2),…,.,(Vin,Vq)均属于 E（ G）,
则称顶点 Vp到 Vq存在一条路径 。 若一条路径上除起点和终
点可以相同外, 其余顶点均不相同, 则称此路径为简单路
径 。 起点和终点相同的路径称为回路, 简单路径组成的回
路称为简单回路 。 路径上经过的边的数目称为该路径的路
径长度 。
9,有根图
在一个有向图中, 若从顶点 V有路径可以到达图中的
其它所有顶点, 则称此有向图为有根图, 顶点 V称作
图的根 。
10,生成树、生成森林
连通图的生成树是一个极小连通子图, 它包含图中全部 n
个顶点和 n-1条不构成回路的边 。 非边通图的生成树则组
成一个生成森林 。 若图中有 n个顶点, m个连通分量, 则
生成森林中有 n-m条边 。
7.2 图的存贮结构
7.2.1 邻接矩阵
1,图的邻接矩阵表示
在邻接矩阵表示中, 除了存放顶点本身信息外, 还
用一个矩阵表示各个顶点之间的关系 。 若 （ i,j）
∈ E(G)或 〈 i,j〉 ∈ E(G),则矩阵中第 i行 第 j列元素值为
1,否则为 0 。
图的邻接矩阵定义为：
1 若 （ i,j） ∈ E(G)或 〈 i,j〉 ∈ E(G)
A[i][j]=
0 其它情形
例如,对图 7-8所示的无向图和有向图,它们的邻接矩阵
见图 7-9。
3
1
2
( a) 无向图 G 3 (b ) 有向图 G4
图 7 - 8 无向图 G3 及有向图 G4
1 2
4 3
0111
1010
1101
1010
001
100
110
( a ) G 3 的邻接矩阵 ( b ) G 4 的邻接矩
图 7 - 9 邻接矩阵表示
2,从无向图的邻接矩阵可以得出如下结论
（ 1） 矩阵是对称的 ;
（ 2） 第 i行或第 i 列 1的个数为顶点 i 的度 ;
（ 3） 矩阵中 1的个数的一半为图中边的数目 ;
（ 4） 很容易判断顶点 i 和顶点 j之间是否有边相连 (看
矩阵中 i行 j列值是否为 1)。
3,从有向图的邻接矩阵可以得出如下结论
（ 1） 矩阵不一定是对称的 ;
（ 2） 第 i 行中 1的个数为顶点 i 的出度 ;
（ 3） 第 i列中 1的个数为顶点 i的入度 ;
（ 4） 矩阵中 1的个数为图中弧的数目 ;
（ 5） 很容易判断顶点 i 和顶点 j 是否有弧相连,
4,网的邻接矩阵表示
类似地可以定义网的邻接矩阵为：
wij 若 （ i,j） ∈ E(G)或 〈 i,j〉 ∈ E(G)
A[i][j]= 0 若 i=j
∞ 其它情形
网及网的邻接矩阵见图 7-10。
?
??
??
??
??
7493
728
421
986
316
( a) 网 G5 ( b ) 网 G5 的邻接矩阵示意图
图 7 - 10 网及邻接矩阵示意图
5
3
1 2
4
3
6
1
2
4
8
9
7
5,图的邻接矩阵数据类型描述
图的邻接矩阵数据类型描述如下,
const int n= maxn； // 图中顶点数
const int e=maxe ； // 图中边数
struct graph
{
elemtype V[n+1]; // 存放顶点信息
v1,v2,…,vn,不使用 v[0]存储空间
int arcs[n+1][n+1] // 邻接矩阵
};
6,建立无向图的邻接矩阵
void creatadj(graph &g)
{ int i,j,k ;
for (k=1; k<=n; k++)
cin>>g.v[k]; //输入顶点信息
for (i=1; i<=n; i++ )
for (j=1; j<=n; j++)
g.arcs[i][j]=0;
for (k=1; k<=e; k++)
{ cin>>i>>j; //输入一条边 (i,j)
g.arcs[i][j]=1;g.arcs[j][i]=1;}}
该算法的时间复杂度为 O（ n2）。
7.建立有向图的邻接矩阵
void creatadj(graph &g)
{ int i,j,k ;
for (k=1; k<=n; k++)
cin>>g.v[k]; //输入顶点信息
for (i=1; i<=n; i++ )
for (j=1; j<=n; j++)
g.arcs[i][j]=0;
for (k=1; k<=e; k++)
{ cin>>i>>j; //输入一条弧 <i,j>
g.arcs[i][j]=1;}}
该算法的时间复杂度为 O（ n2） 。
8.建立无向网的邻接矩阵
void creatadj(graph &g)
{ int i,j,k ; float w;
for (k=1; k<=n; k++)
cin>>g.v[k]; //输入顶点信息
for (i=1; i<=n; i++ )
for (j=1; j<=n; j++)
if (i==j) g.arcs[i][j]=0; else g.arcs[i][j]=∞;
for (k=1; k<=e; k++)
{ cin>>i>>j>>w; //输入一条边 (i,j) 及权值 w
g.arcs[i][j]=w;g.arcs[j][i]=w;}}
该算法的时间复杂度为 O（ n2）。
9.建立有向网的邻接矩阵
void creatadj(graph &g)
{ int i,j,k ; float w;
for (k=1; k<=n; k++)
cin>>g.v[k]; //输入顶点信息
for (i=1; i<=n; i++ )
for (j=1; j<=n; j++)
if (i==j) g.arcs[i][j]=0; else g.arcs[i][j]=∞;
for (k=1; k<=e; k++)
{ cin>>i>>j>>w; //输入一条弧 <i,j> 及权值 w
g.arcs[i][j]=w;}}
该算法的时间复杂度为 O（ n2） 。
7.2.2 邻接表
1,图的邻接表表示
将每个结点的边用一个单链表链接起来, 若干个结点
可以得到若干个单链表, 每个单链表都有一个头结点,
所有头结点组成一个一维数组, 称这样的链表为邻接
表 。
例如，图 7-8所示的无向图 G3和有向图 G4的邻接表见
图 7-11所示
1
2
3
4
2 4 ^
1 3 4 ^
2 4 ^
1 2 3 ^
( a) 无向图 G3 的邻接表
1
2
3
2 3 ^
3 ^
1 ^
1
2
3
3 ^
1 ^
1 3 ^
( b ) 有向图 G4 的邻接表 (c) 有向图 G4 的逆邻接表
图 7 - 11 邻接表示例
1 2
4 3
2,从无向图的邻接表可以得到如下结论
（ 1） 第 i 个链表中结点数目为顶点 i的度；
（ 2） 所有链表中结点数目的一半为图中边数；
（ 3） 占用的存储单元数目为 n+2e 。
3,从有向图的邻接表可以得到如下结论
（ 1） 第 i 个链表中结点数目为顶点 i的出度；
（ 2） 所有链表中结点数目为图中弧数；
（ 3） 占用的存储单元数目为 n+e 。
从有向图的邻接表可知，不能求出顶点的入度。为此，
我们必须另外建立有向图的逆邻接表，以便求出每一
个顶点的入度。逆邻接表在图 7-11(c)中已经给出，从
该图中可知。有向图的逆邻接表与邻接表类似，只是
它是从入度考虑结点，而不是从出度考虑结点。
4,图的邻接表数据类型描述
图的邻接表数据类型描述如下：
const int n =maxn； // maxn表示图中最大顶点
数
const int e= maxe ； // maxe图中最大边数
struct link //定义链表类型
{ elemtype data ;
link *next ;};
struct node //定义邻接表的表头类型
{ elemtype v; //顶点信息
link *next;
}a[n+1];
5.无向图的邻接表建立
void creatlink( )
{ int i,j,k ; link *s ;
for(i=1; i<=n;i++) //建立邻接表头结点
{ a[i].v=i ; a[i].next=NULL; }
for(k=1; k<=e;k++)
{ cin>>i>>j ; //输入一条边 (i,j)
s=new link; //申请一个动态存储单元
s–>data=j ;
s->next=a[i].next ;a[i].next=s ;
s=new link; s->data=i ;
s->next=a[j].next ;a[j].next=s ;}}
该算法的时间复杂度为 O（ n+e）。
6.有向图的邻接表建立
void creatlink( )
{ int i,j,k ; link *s ;
for(i=1; i<=n;i++) //建立邻接表头结点
{ a[i].v=i ; a[i].next=NULL; }
for(k=1; k<=e;k++)
{ cin>>i>>j ; //输入一条边 <i,j>
s=new link; //申请一个动态存储单元
s–>data=j ;s->next=a[i].next ;
a[i].next=s ;}}
该算法的时间复杂度为 O（ n+e） 。
7.网的邻接表的数据类型描述
网的邻接表的数据类型可描述如下：
const int n =maxn； // maxn表示网中最大顶点数
const int e= maxe ； // maxe网中最大边数
struct link //定义链表类型
{ elemtype data ;
float w; //定义网上的权值类型为浮点型
link *next ;};
struct node //定义邻接表的表头类型
{ elemtype v; //顶点信息
link *next;
}a[n+1];
8,无向网的邻接表建立
void creatlink( )
{ float w; int i,j,k ; link *s ;
for(i=1; i<=n;i++) //建立邻接表头结点
{ a[i].v=i ; a[i].next=NULL; }
for(k=1; k<=e;k++)
{ cin>>i>>j>>w ; //输入一条边 (i,j)及该边上的权值
s=new link; //申请一个动态存储单元
s–>data=j ;s->w=w;
s->next=a[i].next ;a[i].next=s ;s=new link;
s->data=i ;s->w=w;s->next=a[j].next ;
a[j].next=s ;}}
该算法的时间复杂度为 O（ n+e） 。
9,有向网的邻接表建立
void creatlink( )
{ float w;int i,j,k ; link *s ;
for(i=1; i<=n;i++) //建立邻接表头结点
{ a[i].v=i ; a[i].next=NULL; }
for(k=1; k<=e;k++)
{ cin>>i>>j>>w ; //输入一条弧 <i,j>及该弧上的权值
s=new link; //申请一个动态存储单元
s–>data=j ;s->w=w;
s->next=a[i].next ;
a[i].next=s ;}}
该算法的时间复杂度为 O（ n+e） 。
另外, 请注意上面的算法中, 建立的邻接表不是唯一
的,与你从键盘输入边的顺序有关, 输入的边的顺序不
同, 则得到的链表也不同 。
7.2.3 邻接多重表
在无向图的邻接表中, 每条边 （ Vi,Vj） 由两个结点表示,
一个结点在第 i个链表中, 另一个结点在第 j个链表中, 当
需要对边进行操作时, 就需要找到表示同一条边的两个
结点, 这给操作带来不便, 在这种情况下采用邻接多重
表较方便 。
在邻接多重表中，每条边用一个结点表示，每个结点由
五个域组成，其结点结构为,
M a r k i n e x t 1 j n e x t 2
其中 mark为标志域, 用来标记这条边是否被访问过,
i和 j域为一条边的两个顶点, next1 和 next2为两个指
针域, 分别指向依附于 i顶点的下一条边和 j顶点的下
一条边 。 而表头与邻接表的表头类似 。
邻接多重表的形式见图 7-12。
1 3
4 2
(a) 无向图 G6 （ b ） G6 的邻接多重表
图 7 - 12 邻接多重表示例
1
2
3
4 2 ^ 4 ^
1 ^ 3 ^
1 2
7.3 图的遍历
和树的遍历类似, 图的遍历也是从某个顶点出发, 沿
着某条搜索路径对图中所有顶点各作一次访问 。 若给
定的图是连通图, 则从图中任一顶点出发顺着边可以
访问到该图中所有的顶点, 但是, 在图中有回路, 从
图中某一顶点出发访问图中其它顶点时, 可能又会回
到出发点, 而图中可能还剩余有顶点没有访问到, 因
此, 图的遍历较树的遍历更复杂 。 我们可以设置一个
全局型标志数组 visited来标志某个顶点是否被访过,
未访问的值为 0,访问过的值为 1。 根据搜索路径的方
向不同, 图的遍历有两种方法：深度优先搜索遍历和
广度优先搜索遍历 。
7.3.1深度优先搜索遍历
1,深度优先搜索思想
深度优先搜索遍历类似于树的先序遍历 。 假定给定
图 G的初态是所有顶点均未被访问过, 在 G中任选一
个顶点 i作为遍历的初始点, 则深度优先搜索遍历可
定义如下：
(1) 首先访问顶点 i,并将其访问标记置为访问过,
即 visited[i]=1；
(2) 然后搜索与顶点 i有边相连的下一个顶点 j,若 j
未被访问过, 则访问它, 并将 j的访问标记置为访问
过, visited[j]=1,然后从 j开始重复此过程, 若 j已访
问, 再看与 i有边相连的其它顶点；
(3) 若与 i有边相连的顶点都被访问过, 则退回到前
一个访问顶点并重复刚才过程, 直到图中所有顶点
都被访问完止 。
例如, 对图 7-13所示无向图 G7,从顶点 1出发的深
度优先搜索遍历序列可有多种, 下面仅给出三种,
其它可作类似分析 。
在无向图 G7中，从顶点 1出发的深度优先搜索遍历
序列举三种为：
1,2,4,8,5,6,3,7
1,2,5,8,4,7,3,6
1,3,6,8,7,4,2,5
3
1
2
4
5
7
6
8
7 - 1 3 无向图 G 7
2,连通图的深度优先搜索
若图是连通的或强连通的, 则从图中某一个顶点出发可
以访问到图中所有顶点, 否则只能访问到一部分顶点 。
另外，从刚才写出的遍历结果可以看出，从某一个顶
点出发的遍历结果是不唯一的。但是,若我们给定图的
存贮结构,则从某一顶点出发的遍历结果应是唯一的。
(1) 用邻接矩阵实现图的深度优先搜索
以图 7-13中无向图 G7 为例, 来说明算法的实现, G7的
邻接矩阵见图 7-14。
01111000
10000100
10000100
10000010
10000010
01100001
00011001
00000110
图 7 - 14 无向图 G 7 的邻接矩阵
3
1
2
4
5
7
6
8
7 - 1 3 无向图 G 7
算法描述为下面形式：
void dfs (int i) // 从顶点 i
出发遍历
{ int j;
cout<<g.v[i]; //输出访问
顶点
visited[i]=1; //全局数组访
问标记置 1表示已经访问
for(j=1; j<=n; j++)
if ((g.arcs[i ][j]= =1)&&(!visited[j]))
dfs(j); }
用上述算法和无向图 G7,可以描述从顶点 1出发的深
度优先搜索遍历过程, 示意图见图 7-15,其中实线表
示下一层递归调用, 虚线表示递归调用的返回 。
从图 7-15中, 可以得到从顶点 1的遍历结果为 1,2,4,8,
5,6,3,7。 同样可以分析出从其它顶点出发的遍历结果 。
D F S (1) D F S (2) D F S (4) D F S (8) D F S (5)
D F S (6) D F S (3) D F S (7)
图 7 - 15 邻接矩阵深度优先搜索示意图
(2)用邻接表实现图的深度优先搜索
仍以图 7-13中无向图 G7 为例，来说明算法的实现,G7
的邻接表见图 7-16，
3
1
2
4
5
7
6
8
7 - 1 3 无向图 G 7
1
2
3
4
5
6
7
8
2 3 ^
1 4
1 6
2 8 ^
2 8 ^
3 8 ^
3 8 ^
4 5 6
7 ^
7 ^
5 ^
图 7 - 16 G 7 的邻接表
算法描述为下面形式：
void dfs1(int i)
{ link *p; cout<<a[i].v ; //输出访问顶点
visted[i]=1; //全局数组访问标记置为 1表示
已访问
p=a[i].next;
while (p!=NULL)
{ if (!visited[p->data])
dfs1(p->data);p=p->next;
}
}
用刚才算法及图 7-16,可以描述从顶点 7出发的深度优
先搜索遍历示意图, 见图 7-17,其中实线表示下一层递
归, 虚线表示递归返回, 箭头旁边数字表示调用的步
骤 。
于是, 从顶点 7出发的深度优先搜索遍历序列, 从图 7-
17中可得出为 7,3,1,2,4,8,5,6。 从其它
顶点出发的深度优先搜索序列, 请读者自已写出 。
D F S 1(7) D F S 1(3) D F S 1(1) D F S 1(2) D F S 1(4)
D F S 1(8)
D F S 1(5)
D F S 1(6)
2 1
14 13 12
11 10
3 4 5 6
9
8
7
7 - 17 邻接表深度优先搜索示意图
3．非连通图的深度优先搜索
若图是非连通的或非强连通图, 则从图中某一个顶点出
发 。 不能用深度优先搜索访问到图中所有顶点, 而只能
访问到一个连通子图 （ 既连通分量 ） 或只能访问到一个
强连通子图 （ 既强连通分量 ） 。 这时, 可以在每个连通
分量或每个强连通分量中都选一个顶点, 进行深度优先
搜索遍历, 最后将每个连通分量或每个强连通分量的遍
历结果合起来, 则得到整个非连通图的遍历结果 。
遍历算法实现与连通图的只有一点不同, 即对所有顶点
进行循环, 反复调用连通图的深度优先搜索遍历算法即
可 。 具体实现如下：
for(int i=1;i<=n;i++)
if(!visited[i])
dfs(i) ;
for(int i=1;i<=n;i++)
if(!visited[i])
dfs1(i);
或者
7.3.2 广度优先搜索遍历
1,广度优先搜索的思想
广度优先搜索遍历类似于树的按层次遍历 。 设图 G的初
态是所有顶点均未访问, 在 G 中任选一顶点 i作为初始点,
则广度优先搜索的基本思想是：
(1) 首先访问顶点 i,并将其访问标志置为已被访问,
即 visited[i]=1；
(2) 接着依次访问与顶点 i有边相连的所有顶点 W1，
W2,…, Wt；
(3) 然后再按顺序访问与 W1,W2,…, Wt有边相连又
未曾访问过的顶点；
依此类推，直到图中所有顶点都被访问完为止 。
例如, 对图 7-13所示无向图 G7,从顶点 1出发的广
度优先搜索遍历序列可有多种, 下面仅给出三种,
其它可作类似分析 。
在无向图 G7中, 从顶点 1出发的广度优先搜索遍历序列
举三种为：
1,2,3,4,5,6,7,8
1,3,2,7,6,5,4,8
1,2,3,5,4,7,6,8
3
1
2
4
5
7
6
8
7 - 1 3 无向图 G 7
2,连通图的广度优先搜索
(1) 用邻接矩阵实现图的广度优先搜索遍历
仍以图 7-13中无向图 G7及 7-14所示的邻接矩阵来说明对
无向图 G7的遍历过程
3
1
2
4
5
7
6
8
7 - 1 3 无向图 G 7
01111000
10000100
10000100
10000010
10000010
01100001
00011001
00000110
图 7 - 14 无向图 G 7 的邻接矩阵
根据该算法用及图 7-14中的邻接矩阵, 可以得到图 7-13
的无向图 G7 的广度优先搜索序列, 若从顶点 1 出发, 广
度优先搜索序列为,1,2,3,4,5,6,7,8。 若从顶
点 3出发, 广度优先搜索序列为,3,1,6,7,2,8，
4,5,从其它点出发的广度优先搜索序列可根据同样类似
方法分析 。
算法描述如下：
void bfs( int i) //从顶点 i出发遍历
{ int Q[n+1] ; //Q为队列
int f,r,j ; // f,r分别为队列头, 尾指针
f=r=0 ; //设置空队列
cout<<g.v[i] ; // 输出访问顶点
visited[i]=1 ; //全局数组标记置 1表示已经访问
r++; q[r]=i ; //入队列
while (f<r) { f++; i=q[f] ; //出队列
for (j=1; j<=n; j++)
if ((g.arcs[i][j]==1)&&(!visited[j]))
{ cout<<g.v[j] ; visited[j]=1 ; r++; q[r]=j ;} } }
（ 2） 用邻接表实现图的广序优先搜索遍历
仍以无向图 G7及图 7-16所示邻接表来说明邻接表上实
现广度优先搜索遍历的过程
3
1
2
4
5
7
6
8
7 - 1 3 无向图 G 7
1
2
3
4
5
6
7
8
2 3 ^
1 4
1 6
2 8 ^
2 8 ^
3 8 ^
3 8 ^
4 5 6
7 ^
7 ^
5 ^
图 7 - 16 G 7 的邻接表
根据该算法及图 7-16,可以得到图 G7的广度优先搜索序
列, 若从顶点 1出发, 广度优先搜索序列为,1,2,3，
4,5,6,7,8,若从顶点 7出发, 广度优先搜索序列为：
7,3,8,1,6,4,5,2,从其它顶点出发的广度优先
搜索序列可根据同样类似方法分析 。
算法描述如下：
void BFS1(int i)
{ int q[n+1] ; //定义队列
int f,r ; link *p ; //P为搜索指针
f=r=0 ; cout<<a[i].v ;
visited[i]=1 ; r++; q[r]=i ; //进队
while (f<r)
{ f++ ; i=q[f] ; //出队 p=a[i].next ;
while (p!=NULL)
{ if (!visited[p->data]){ cout<<a[p->data].v;
visited[p->data]=1 ; r++;q[r]=p->data ;}
p=p->next;}} }
3.非连通图的广度优先搜索
若图是非连通的或非强连通图, 则从图中某一个顶点
出发 。 不能用广度优先搜索遍历访问到图中所有顶点,
而只能访问到一个连通子图 （ 既连通分量 ） 或只能访
问到一个强连通子图 （ 既强连通分量 ） 。 这时, 可以
在每个连通分量或每个强连通分量中都选一个顶点,
进行广度优先搜索遍历, 最后将每个连通分量或每个
强连通分量的遍历结果合起来, 则得到整个非连通图
或非强连通图的广度优先搜索遍历序列 。
遍历算法实现与连通图的只有一点不同, 即对所有顶
点进行循环, 反复调用连通图的广度优先搜索遍历算
法即可 。 具体可以表示如下：
for(int i=1;i<=n;i++) for(int i=1;i<=n;i++)
if(!visited[i]) 或 if(!visited[i])
bfs(i) ; bfs1(i);
7.4 生成树和最小生成树
7.4.1 基本概念
1,生成树
在图论中，常常将树定义为一个无回路连通图。例如，
图 7-18中的两个图就是无回路的连通图。乍一看它似乎不
是不是树，但只要选定某个顶点做根并以树根为起点对
每条边定向，就可以将它们变为通常的树。
3
1 2
4 5
1 2
4 3
5
7 - 1 8 两个无回路的连通图
在一个连通图中, 有 n个顶点, 若存在这样一个子图,
含有 n个顶点, n-1条不构成回路的边, 则这个子图称
为生成树, 或者定义为：一个连通图 G的子图如果是
一棵包含 G的所有顶点的树, 则该子图为图 G 的生成
树 。
由于 n个顶点的连通图至少有 n-1条边，而所有包含 n-1
条边及 n个顶点的连通图都是无回路的树，所以生成树
是连通图中的极小连通子图，所谓极小是指边数最少，
若在生成树中去掉任何一条边，都会使之变为非连通图，
若在生成树上任意增加一条边，就会构成回路。那么，
对给定的连通图，如何求得它的生成树呢？回到我们前
面提到的图的遍历，访问过图中一个顶点后，要访问下
一个顶点,一般要求两个顶点有边相连，即必须经过
图中的一条边，要遍历图中 n 个顶点且每个顶点都只遍
历一次，则必须经过图中的 n-1条边，这 n-1条边构成连
通图的一个极小连通子图，所以它是连通图的生成树，
由于遍历结果可能不唯一，所以得到的生成树也是不唯
一的。
要求得生成树, 可考虑用刚才讲过的深度优先搜索遍
历算法及广度优先搜索遍历算法 。 对于深度优先搜索
算法 DFS或 DFS1,由 DFS（ i） 递归到 DFS（ j）, 中间
必经过一条边 （ i,j）, 因此, 只需在 DFS(j)调用前输出
这条边或保存这条边, 即可求得生成树的一条边, 整
个递归完成后, 则可求得生成树的所有边 。 对于广度
优先搜索算法 BFS或 BFS1,若 i 出队, j 入队, 则 (i,j)为
一条树边 。 因此, 可以在算法的 if 语句中输出这条边,
算法完成后, 将会输出 n-1条边, 也可求得生成树 。 由
深度优先搜索遍历得到的生成树, 称为深度优先生成
树, 由广度优先搜索遍历得到的生成树, 称为广度优
先生成树 。 图 7-13中无向图 G7的两种生成树见 图 7-19。
若一个图是强连通的有向图, 同样可以得到它的生成
树 。 生成树可以利用连通图的深度优先搜索遍历或连
通图的广度优先搜索遍历算法得到 。
1
4
2
5
3
6
8
7
2
7 6
8
3
5
4
1
(a) 深度优先生成树 (b ) 广度优先生成树
图 7 - 1 9 两种生成树示意图
3
1
2
4
5
7
6
8
7 - 1 3 无向图 G 7
2．生成森林
若一个图是非连通图或非强连通图, 但有若干个连通分量
或若干个强连通分量, 则通过深度优先搜索遍历或广度优
先搜索遍历, 不可以得到生成树, 但可以得到生成森林,
且若非连通图有 n 个顶点, m 个连通分量或强连通分量,
则可以遍历得到 m棵生成树, 合起来为生成森林, 森林中
包含 n-m条树边 。
生成森林可以利用非连通图的深度优先搜索遍历或非连通
图的广度优先搜索遍历算法得到 。
3,最小生成树
在一般情况下, 图中的每条边若给定了权, 这时, 我们
所关心的不是生成树, 而是生成树中边上权值之和 。 若
生成树中每条边上权值之和达到最小, 称为最小生成树 。
下面将介绍求最小生成树的两种方法：普里姆算法和克
鲁斯卡尔算法 。
7.4.2 普里姆算法
1,普里姆 (prim)算法思想
下面仅讨论无向网的最小生成树问题 。
普里姆方法的思想是：在图中任取一个顶点 K作为开始点，
令 U={k},W=V-U，其中 V为图中所有顶点集，然后找一
个顶点在 U中，另一个顶点在 W中的边中最短的一条，找
到后，将该边作为最小生成树的树边保存起来，并将该边
顶点全部加入 U集合中，并从 W中删去这些顶点，然后重
新调整 U中顶点到 W中顶点的距离,使之保持最小，再重
复此过程，直到 W为空集止。求解过程参见图 7-20 。
假设开始顶点就选为顶点 1,故首先有 U={1},W={2，
3,4,5,6}
( a ) 无向网 ( b ) u = { 1 } w = { 2,3,4,5,6 }
6
4
1
2
4
6
3
6
2
1
3
5
7
6
5
5
5
1
2
3
4
5
6
6
?
5
1 ?
3
1
2
4
6
5 6
1
4
5
5
5
3
1
2
4
6
5 6
4
2
1
5
5
(c ) u ={ 1,3} w ={ 2,4,5,6} (d ) u ={ 1,3,6 } w ={ 2,4,5 }
3
1
2
4
6
5 6
4
2
1
5
5
( e) u ={ 1,3,6,4 } w ={ 2,5 } ( f ) u ={ 1,3,6,4,2 } w ={ 5 }
1
2
4
6
3
5
6
4
2
1
5
3
(g) u={1,3,6,4,2,5} w ={ }
5
4
2
1
3
1
2
4
6
3
5
6
图 7 - 20 prim 方法构造最小生成树的过程
7.4.3 克鲁斯卡尔 （ kruskal） 算法
1,克鲁斯卡尔算法基本思想
克鲁斯卡尔算法的基本思想是：将图中所有边按权值递
增顺序排列，依次选定取权值较小的边，但要求后面选
取的边不能与前面选取的边构成回路，若构成回路，则
放弃该条边，再去选后面权值较大的边,n个顶点的图中，
选够 n-1条边即可。
例如，对图 7-20（ a） 中无向网，用克鲁斯卡尔算法求
最小生成树的过程见图 7-22。
2
4
6
5
6
1
3
1
2
5
1
3
1
4
6
2
6
(a) 选第 1 条边 ( b ) 选第 2 条边
(c ) 选第 3 条边 (d ) 选第 4 条边
2
3
5
1
3
1
4
6
2
6
4
2
1
2
3
5
1
4
6
3
6
1
2
4
6
3
5 6
4
2
1
3
5
(e ) 选第 5 条边 ( 不能选（ 1,4 ）边，会构成回路，但可选（ 2,3 ）或 (5,3) 中之一 )
5
1
2
4
6
3
6
4
2
1
3 5
或者
图 7 - 22 克鲁斯卡尔方法求最小生成树的过程
7.5最短路径
交通网络中常常提出这样的问题：从甲地到乙地之间
是否有公路连通?在有多条通路的情况下, 哪一条路最
短? 交通网络可用带权图来表示 。 顶点表示城市名称,
边表示两个城市有路连通, 边上权值可表示两城市之
间的距离, 交通费或途中所花费的时间等 。 求两个顶
点之间的最短路径, 不是指路径上边数之和最少, 而
是指路径上各边的权值之和最小 。
另外, 若两个顶点之间没有边, 则认为两个顶点无通
路, 但有可能有间接通路 (从其它顶点达到 )。 路径上的
开始顶点 (出发点 )称为源点, 路径上的最后一个顶点称
为终点, 并假定讨论的权值不能为负数 。
7.5.1单源点最短路径
1,单源点最短路径
单源点最短路径是指：给定一个出发点 (单源点 )和一个
有向网 G=(V,E),求出源点到其它各顶点之间的最短路径 。
那么怎样求出单源点的最短路径呢?我们可以将源点到终
点的所有路径都列出来,然后在里面选最短的一条即可 。
但是这样做,用手工方式可以,当路径特别多时,显得特别
麻烦,并且没有什么规律,不能用计算机算法实现 。
迪杰斯特拉 (Dijkstra)在做了大量观察后,首先提出了按路
长度递增序产生各顶点的最短路径算法,我们称之为迪杰
斯特拉算法 。
2,迪杰斯特拉算法的基本思想
算法的基本思想是,设置并逐步扩充一个集合 S，存放已
求出其最短路径的顶点，则尚未确定最短路径的顶点集
合是 V-S，其中 V为网中所有顶点集合。按最短路径长度
递增的顺序逐个以 V-S中的顶点加到 S中，直到 S中包含全
部顶点，而 V-S为空。
具体做法是,设源点为 Vl,则 S中只包含顶点 Vl，令 W=V-S，则
W中包含除 Vl外图中所有顶点,Vl对应的距离值为 0,W中
顶点对应的距离值是这样规定的：若图中有弧 <Vl,Vj>则 Vj
顶点的距离为此弧权值，否则为 ∞(一个很大的数 )，然后每
次从 W中的顶点中选一个其距离值为最小的顶点 Vm加入到 S
中，每往 S中加入一个顶点 Vm，就要对 W中的各个顶点的距
离值进行一次修改。若加进 Vm做中间顶点，使
<Vl,Vm>+<Vm,Vj>的值小于 <Vl,Vj>值，则用
<Vl,Vm>+<Vm,Vj>代替原来 Vj的距离，修改后再在 W中选
距离值最小的顶点加入到 S中，如此进行下去，直到 S中包含
了图中所有顶点为止
迪杰斯特拉算法的求解过程
10
3
5
20
8
25
4
30 3
30
1
2
3
5
4
?
?
(a) 一个有向网点 (b) 源点 1 到其它顶点的初始距离
1
2
3
5
4
12
3
8
25
30
1
2
3
5
4
(c) 第一次求得的结果 (d) 第二次求得的结果
3
8
12
4
1
2
3
5
4
3
8
12
4
3
8
12
4
(e) 第三次求得的结果 (f) 第四次求得的结果
1
2
3
5
4
1
2
3
5
4
图 7 - 27 迪杰斯特拉算法求最短路径过程及结果
7.5.2所有顶点对之间的最短路径
1,顶点对之间的最短路径概念
所有顶点对之间的最短路径是指：对于给定的有向网
G=(V,E),要对 G中任意一对顶点有序对 V,W(V≠W),找出 V
到 W的最短距离和 W到 V的最短距离 。
解决此问题的一个有效方法是,轮流以每一个顶点为源点,
重复执行迪杰斯特拉算法 n次,即可求得每一对顶点之间的
最短路径,总的时间复杂度为 O(n3)。
下面将介绍用弗洛伊德 (Floyd)算法来实现此功能,时
间复杂度仍为 O(n3),但该方法比调用 n次迪杰斯特拉
方法更直观一些 。
2,弗洛伊德算法的基本思想
弗洛伊德算法仍然使用前面定义的图的邻接矩阵
arcs[n+1][n+1]来存储带权有向图。算法的基本思想是,设置
一个 nxn的矩阵 A(k)，其中除对角线的元素都等于 0外，其它
元素 a(k)[i][j]表示顶点 i到顶点 j的路径长度,K表示运算步骤。
开始时，以任意两个顶点之间的有向边的权值作为路径长度，
没有有向边时，路径长度为 ∞，当 K=O时,A (0)[i][j]=arcs[i][j],
以后逐步尝试在原路径中加入其它顶点作为中间顶点, 如果
增加中间顶点后, 得到的路径比原来的路径长度减少了, 则
以此新路径代替原路径, 修改矩阵元素 。 具体做法为：
第一步, 让 所 有 边 上 加 入 中 间 顶 点 1, 取 A[i][j] 与
A[i][1]+A[1][j]中较小的值作 A[i][j]的值, 完成后得到 A(1)，
因此, 弗洛伊德算法可以描述为,
A(0)[i][j]=arcs[i][j]; //arcs为图的邻接矩阵
A(k)[i][j]=min{A(k-1) [i][j],A(k-1) [i][k]+A(k-1) [k][j]}
其中 k=1,2,…,n
第二步, 让所有边上加入中间顶点 2,取 A[i][j]与
A[i][2]+A[2][j]中较小的值, 完成后得到 A(2)…, 如此
进行下去, 当第 n步完成后, 得到 A(n),A(n)即为我们所
求结果,A(n)[i][j]表示顶点 i到顶点 j的最短距离 。
3,弗洛伊德算法实现
在用弗洛伊德算法求最短路径时,为方便求出中间经
过的路径,增设一个辅助二维数组 path[n+1][n+1],其
中 path[i][j]是相应路径上顶点 j的前一顶点的顶点号 。
算法描述如下：
Void floyd ( const int n)
{ for (int i=1;i<=n;i++)
for (int j=1;j<=n; j++)
{ a[i][j]=arcs[i][j]
if(i!=j)&&(a[i][j]<∞)
path[i][j]=i;else path[i][j]=0;
}
for (int k=1; k<=n;k++)
for i=1;i<=n;i++)
for (j=1;j<=n;j++)
if (a[i][k]+a[k][j]<a[i][j])
{a[i][j]=a[i][k]+a[k][j]; path[i][j]=path[k][j];}
for (i=1;i<=n;i++) //输出路径长度及路径
for (j=1;j<=n;j++)
{ if(i!=j) {cout<<a[i][j]<<“:” ;
int next=path[i][j]; cout<<j;
while (next !=i)
{ cout<<“←”<<next ; next=path[i][next];}
cout<<“←”<<i<<endl ;}}}
7.6拓扑排序
7.6.1 实现规则
1,基本概念
通常我们把计划、施工过程、生产流程、程序流程等都当
成一个工程，一个大的工程常常被划分成许多较小的子工
程，这些子工程称为活动，这些活动完成时，整个工程也
就完成了。例如，计算机专业学生的课程开设可看成是一
个工程，每一门课程就是工程中的活动，图 7-30给出了若
干门所开设的课程，其中有些课程的开设有先后关系，有
些则没有先后关系，有先后关系的课程必须按先后关系开
设，如开设数据结构课程之前必须先学完程序设计基础及
离散数学，而开设离散数学则必须先并行学完高等数学、
程序设计基础课程。 ……………….,….,
课程代码 课程名称 先修课程
C1 高等数学
C2 程序设计基础
C3 离散数学 C 1,C 2
C4 数据结构 C 2,C 3
C5 高级语言程序设计 C2
C6 编译方法 C 5,C 4
C7 操作系统 C 4,C 9
C8 普遍物理 C1
C9 计算机原理 C8
( a) 课程开设 ( b) 课程开设优先关系的有向图
图 7 - 3 0 学生课程开 设工程图
C8
C6
C5
C4 C3
C2
C1
C9
C7
在图 7-30(b)中, 我们用一种有向图来表示课程开设,
在这种有向图中, 顶点表示活动, 有向边表示活动
的优先关系, 这有向图叫做顶点表示活动的网络
(Actire On Vertices)简称为 AOV网 。
在 AOV网中,<i,j>有向边表示 i活动应先于 j活动开始，
即 i活动必须完成后,j活动才可以开始，并称 i为 j的直接
前驱,j为 i的直接后继。这种前驱与后继的关系有传递
性，此外，任何活动 i不能以它自己作为自己的前驱或后
继，这叫做反自反性。从前驱和后继的传递性和反自反
性来看,AOV网中不能出现有向回路 (或称有向环 )。在
AOV网中如果出现了有向环，则意味着某项活动应以自
己作为先决条件，这是不对的，工程将无法进行。对程
序流程而言，将出现死循环。
因此, 对给定的 AOV网, 应先判断它是否存在有向
环 。 判断 AOV网是否有有向环的方法是对该 AOV网
进行拓扑排序, 将 AOV网中顶点排列成一个线性有
序序列, 若该线性序列中包含 AOV网全部顶点, 则
AOV网无环, 否则, AOV网中存在有向环, 该 AOV
网所代表的工程是不可行的 。
2,拓扑排序
下面将介绍怎样实现拓扑排序,实现步骤如下：
（ 1） 在 AOV网中选一个入度为 0的顶点且输出之；
（ 2） 从 AOV网中删除此顶点及该顶点发出来的所有有
向边；
（ 3） 重复 （ 1）, （ 2） 两步, 直到 AOV网中所有顶点
都被输出或网中不存在入度为 0的顶点 。
从拓扑排序步骤可知, 若在第 3步中, 网中所有顶点都
被输出, 则表明网中无有向环, 拓扑排序成功 。 若仅
输出部分顶点, 网中已不存在入度为 0的顶点, 则表明
网中有有向环, 拓扑排序不成功 。 例如, 对图 7-31中
AOV网, 可以得到的拓扑序列有,1,2,3,4,5或 2,1,3,4,5。
因此, 一个 AOV网的拓扑序列是不唯一的 。
