1
第 6 章 图结构
? 若干个结点与若干条边构成的结构
– 结点是一些具体对象的抽象
– 边是对象间的关系
? 图是一种复杂的非线性结构，它有极强的表达
能力
? 图中结点可有多个前趋和多个后继
? 这里着重讨论图的存贮结构与基本操作的实现
2
§ 6.1 图的基本概念
§ 6.1.1 图的概念
1,图
? 图是由若干个结点和若干条边构成的结构，每个结点
具有任意多个前驱和后继。
– 结点集合：结点代表对象
– 边集合：两结点之间的边表示它们代表的对象之间的关系
? 在具体应用中，结点与边要被赋予具体的含意,如
– 结点代表城市
– 边代表城市之间的行程。
1
2 5
4 3
a
b
c
d
3
§ 6.1.1 图的概念
1,图
图是形为
G=(V,R)
的数据结构, 其中,
V={x|x属于数据对象 }
R={VR}
VR={<x,y> | p(x,y)∧ x∈ V∧ y∈ V}
这里,p(x,y)是 V上的一个谓词,p(x,y)为真当且仅当 x与 y
存在问题世界中的关系。
图的形式化
定义
4
§ 6.1.1 图的概念
2,有向 /无向图
若二元关系 VR是对称的 （ 即对任意 x与 y,若有
<x,y>∈ VR,则必有 <y,x>∈ VR）, 则称图 G是
无向图, 否则称 有向图 。 对无向图, 我们用
(x,y)表示 <x,y>。
1
2 5
4 3
a
b
c
d
5
§ 6.1.1 图的概念
? 3,结点、边、弧
? 图中的数据元素称为 结点 （或顶点）
? 有时为了强调，对有向图，称 <x,y>为 弧, x与 y分别为 弧尾 与 弧
头,
? 称 x与 y分别为 <x,y>的 始点 与 终点,
? 称 y为 x的 出点 /可达邻接点,
? 称 x为 y的 入点,称 <x,y>为 x的 出边 /出弧, <x,y>为 y的 入边 /入
弧 。
? 对无向图，称 <x,y>为 边 。
? 在讨论图中，一般用自然数串给结点编号。
1
2 5
4 3
a
b
c
d
6
【 例 6-1】 设有两个二元组 G1=(V1,R1)与 G2=(V2,R2),其中,
V1={1,2,3,4,5}
R1={VR1}
VR1={<1,2>,<1,5>,<2,1>,<2,4>,<3,5>,<4,1>}
V2={a,b,c,d}
R2={VR2}
VR2={(a,b),(a,d),(b,d),(d,c)}
1
2 5
4 3
a
b
c
d
(a) 有向图 (a) 无向图
【 图 -】 图示例
7
§ 6.1.1 图的概念
4,邻接, 关联
? 对图中任意结点 x与 y，若它们之间存在边的关
系（即有 <x,y>，或 <y,x>），则称 x与 y邻接,
它们互为 邻接点 。同时称 x或 y与边 <x,y>（或
<y,x>或 (x,y)） 关联 。
1
2 5
4 3
a
b
c
d
8
§ 6.1.1 图的概念
5,度
? 对任一结点 x,称以它为头的弧的个数为它的 入度
? 称以它为尾的弧的个数为它的 出度
? 称它的入度与出度之和为它的 度 。
? 对无向图, 无出度入度之分, 直接称与它关联的边的
个数为它的 度 。
1
2 5
4 3
a
b
c
d
9
§ 6.1.1 图的概念
6,权
? 权是一个数值量, 是某些信息的数字化抽象 。
? 权分边权与结点权, 分别是边与结点的问题世界所关
心的信息的数值化表示 。
? 例如, 若结点代表城市, 则边权可代表城市之间的交
通费用 。
1
2 5
4 3
60
70200
170 70
90
10
§ 6.1.1 图的概念
7,路径 （ 通路 ）
? 对有向图, 若存在弧序列
<x0,x1>,<x1,x2>,…, <xn-1,xn>
且 n≥1,则称从 x0到 xn有通路 （ 路径 ） 。 上列序列称为
x0到 xn的 路径 。 该路径也可表示为
(x0,x1,…,xn)
1
2 5
4 3
11
§ 6.1.1 图的概念
7,路径 （ 通路 ） （ 续 ）
? 对无向图, 若有边序列
(x0,x1),(x1,x2),…, (xn-1,xn)
且 n≥1,则称 x0与 xn之间 有路径 （ 通路 ）, 该路径可用
上列边序列表示, 亦可用下列结点序列表示
(x0,x1,…,xn)
a
b
c
d
12
§ 6.1.1 图的概念
7,路径 （ 通路 ） （ 续 ）
? 路径中边的数目称为 路径长 。
? 若 x0=xn,则称相应的路径为 回路 /环路 。
? 若在路径 (x0,x1,…,xn)中, 除 x0与 xn外, 任意其它结
点均不相同, 则称该路径为 简单路径 。 起点与终点重合
的简单路径称为 简单回路 。
a
b
c
d
1
2 5
4 3
13
§ 6.1.1 图的概念
8,子图 /生成图
? 若某图 G'的结点集合与边集合分别是另一图的 G的结
点集合和边集合的子集, 则称 G'为 G的 子图 。
? 设有两个图 G与 G',若它们的结点集合相同, 但 G'的
边集合是 G的边集合的子集, 则称 G'是 G的 生成图 。
? 显然, 生成图一定是子图, 但反之未必 。
a
b
c
d
1
2 5
4 3
14
§ 6.1.1 图的概念
9,连通
? 若图中任意两结点间均有通路 （ x到 y与 y到 x）, 则称
该图是 （ 强 ） 连通的 。
? 若图中某子图是连通的, 则称该子图为一个 连通分量 。
? 若 G的某子图 G'是连通的, 并且, 若有 G的另一子图
G''包含图 G',则 G''必不连通,则称 G'是 极大连通分量 。
a
b
c
d
1
2 5
4 3
15
§ 6.1.1 图的概念
9,连通 （ 续 ）
? 对于有向图, 若任意两结点间至少有单向通路, 但有
些结点无双向通路, 则称该图为 弱连图 。
? 类似地, 也有 弱连通分量 的概念 。
1
2 5
4 3
16
§ 6.1.1 图的概念
10,生成树
无回路的连通的无向图的生成图, 称为该无
向图的 生成树 。
【 定理 6-1】 生成树中边的个数为结点个数
减 1.
a
b
c
d
a
b
c
d
a
b
c
d
17
§ 6.1.2 图的基本操作
① 检索：
·按结点 （ 编号或内容 ） 检索结点 （ 位置 ）
·按边的两顶点检索边
② 插入：
·插入结点
·插入边
③ 删除：
·删除结点及与其关联的边
·删除边
18
§ 6.1.2 图的基本操作
④ 求邻接点, 关联边
⑤ 求度 （ 入度与出度 ）
⑥ 求路径
⑦ 求子图
⑧ 求生成图
⑨ 求生成树
⑩ 求连通分量
19
§ 6.1.2 图的基本操作
⑾ 求拓扑序列 （ 有向图 ）
⑿ 图的遍历
⒀ 求关键路径
⒁ 求最短路径
⒂ 求最小生成树
…………
20
§ 6.2 图的抽象对象模型
? 考虑仅从逻辑关系出发时，图结点和整个图对
象应具有的性质
? 由于图结点的关系不象其他结构中结点那样有
限制，所以它的抽象结构比较复杂。
21
§ 6.2.1 图结点抽象模型
template <class TElem>
struct TGraphNode0
{
long no;
TElem info;
virtual long GetNo ( ) {return no;}; //返回本结点的编号
virtual void SetNo(long mNo) {no = mNo;}; //为本结点设置编号值
virtual TElem& GetElem ( ) {return info;}; //返回本结点的值
virtual TElem& SetElem (TELem &e)
{ info = e; return info;}; //为本结点设置元素值
22
§ 6.2.1 图结点抽象模型
virtual TGrphNode0 *GetSucc (long sucNo)=0;
//返回本结点的第 sucNo个后继结点的地址
virtual TGrphNode0 *GetPrior (long preNo)=0;
//返回本结点的第 pre个前驱结点的地址
virtual TGrphNode0 *SetSucc (long sucNo,TGrphNode* pNode)=0;
//为本结点设置第 sucNo个后继
virtual TGrphNode0 *SetPrior (long preNo,TGrphNode* pNode)=0;
//为本结点设置第 preNo个前驱
virtual long GetInDegree ( )=0;
//返回本结点的入度值
virtual long GetOutDegree ( )=0;
//返回本结点的出度值
};
23
§ 6.2.2 图的边对象抽象模型
template <class TElem>
struct TGrphEdge
{
long startNo,endNo;
TELem info;
virtual TElem &GetElem ( ) { return info;};
virtual TElem &SetElem (TElem &e) { info = e; return info;};
virtual long GetStartNo ( ) { return startNo;};
virtual long GetEndNo ( ) { return endNo;};
virtual void SetStartNo (long mNo) { startNo = mNo; };
virtual void SetEndNo (long mNo) { endNo = mNo; };
};
24
§ 6.2.3 图抽象对象模型
template <class TELem,class TEdgeElem>
class TGrph0
{
public:
virtual TGrphEdge<TEdgeElem> *AddEdge(long startNo,long endNo,
TEdgeElem &ee)=0;
virtual TGrphNode0<TElem> *AddNode(long mNo,TElem &nodeInfo) =0;
virtual TGrphNode0<TElem> *DeleteNode(long mNo) =0;
virtual TGrphEdge<TElem> *DeleteEdge(long startNo,long endNo) =0;
25
virtual long Cluster(TGrphNode0<TElem>* pStartNode,TElem**e,
TTraverseMode tm)=0;
virtual long Cluster(TGrphNode0<TElem>* pStartNode,long**nos,
TTraverseMode tm)=0;
virtual long Cluster(TGrphNode0<TElem>* pStartNode,
TGrphNode0<TElem>* pNodes,TTraverseMode tm)=0;
virtual TGrphNode<TElem> *Locate(longnNo)=0;
virtual TGrphEdge<TEdgeElem> *Locate(longstartNo,long endNo)=0;
virtual TGrphNode<TElem> *Locate(TElem *e,long sn=1)=0;
26
virtual long GetPath(long startNo,long endNo,long sn,long
*pathNodeNo)=0;
virtual long GetPath(longstartNo,long endNo,long sn,
TGrphNode0<TElem>* pathNode) =0;
virtual long GetPathShortest(longstartNo,TDijkPath *path) =0;
virtual long GetPathShortest(long**path) =0;
};
struct TDijkPath
{
float len;
long pre;
};
27
§ 6.3 图的存贮结构
? 必须显式地存贮结点之间的关系 （ 即边 ） 的信
息 。 一般有两大类方法：
① 用边的集合表示图；
②用链接关系表示图。
邻接矩阵法
邻接表
十字链表
邻接多重表
28
§ 6.3.1 邻接矩阵法
（一）存贮方法
? 用边的集合表示图的方法
? 边集合用一个二维数组表示
? 数组每个元素表示一条边，它的两个下标分别表示边
的两个端点的编号
? 结点编号要用连续的自然数，使得能与数组下标对应
29
§ 6.3.1 邻接矩阵法
（一）存贮方法
边 <i,j>的权：若 <i,j>是边
A[i][j]=
特殊标志,若 <i,j>不是边
若不考虑边的权, 则 A[i][j]只表示边 <i,j>是否存在, 即
1,若 <i,j>是边
A[i][j]=
0或 ∞,若 <i,j>不是边
?同样适合于无向图
?用 (i,j)代替 <i,j>
?对无向图，邻接矩阵是个
对称矩阵，可按对称矩阵
的压缩存贮方法存贮
30
1 2 3 4 5 a b c d
1 0 1 0 0 1
2 1 0 0 1 0 a 1 0 1 0 1
3 0 0 0 0 5 b 2 1 0 0 1
4 1 0 0 0 0 c 3 0 0 0 0
5 0 0 0 0 0 d 4 1 1 0 0
下图的邻接矩阵
a
b
c
d
1
2 5
4 3
空间复杂度正
比于图的结点
个数的平方
31
§ 6.3.1 邻接矩阵法
（二） 算法实现的考虑
1,结点, 边的增删
? 对邻接矩阵, 结点或边的增删的算法校简单, 但一般要移动元素 。
? 删除边：删除一条边比较简单, 只需将对应元素置无边标志；
? 删除点：删除一个结点, 要将与它关联的边一同删除, 即删除结
点在矩阵中对应的行与列 。
? 增加边：为现有两结点间增加一条边, 只需将对应矩阵元素置边
信息 。
? 增加点：增加一个新结点, 要在矩阵中相应位置插入一行一列 。
? 增加新结点边：插入带新结点的边，先插入新结点，然后置边信
息。
32
§ 6.3.1 邻接矩阵法
（二） 算法实现的考虑
2,度的计算
出度：结点 i的出度, 等于 i所对应的行上的非特殊元素的个数 。
入度：结点 i的入度等于 i所对应的列上的非特殊元素的个数 。
3,找邻接点 /判别是否有边
对邻接矩阵, 判别是否有边是直接的, 即要知结点 i到 j是否有边,
只要测试元素 A[i][j]即可 。 至于找邻接点, 则是个依次判别是否有边
的问题 。
33
§ 6.3.1 邻接矩阵法
（二） 算法实现的考虑
4,找路径
要找出结点 x到结点 y之间的路径, 即 path(x,y),按下列方法进行：
Path(x,y)
{
if (x==y) return x; //所找的路径为 (x)，
if (若 x到 y有边 ) return (x,y); //所找的路径为 (x,y)
for (x的每个直接可达点 u)
{
if (u尚未试探过 )
if (Path(u,y)存在 ) return (x)+Path(u,y);
}
return (); //空路径
}
可适合于
任意存贮
结构
34
§ 6.3.2 邻接表
（一） 存贮方法
? 图的邻接表存贮法与树及树的邻接表存贮法类
似, 其具体方法为：
·为图中每个结点 x建立一个线性链表
·对无向图, x的线性链表的每个元素, 分别存放存放
与 x的各邻接点构成的边的信息 。
·对有向图, x的线性链表的每个元素, 分别存放以 x
为始点的各个弧的信息 。
35
§ 6.3.2 邻接表
（一） 存贮方法
? 线性链表的结点结构为：
?
·为每个图结点, 设立一个如下形式的结点：
? 各结点可以存储在一个一维数组 （ 称为头数组 ） 中
（ 每个数组元素分别对应一个图结点 ）, 也可以增设一
个链指针, 使各结点链在一起, 形成另一个单链表 。
边终点编号 边内容 链指针
结点编号 结点内容 链头指针
36
2 5 ^
1 4 ^
5 ^
1 ^
1
2
3
4
^5
下图对应的邻接矩阵
当边数较少时，
该存贮方式的存
贮利用率更高
a
b
c
d
1
2 5
4 3
37
§ 6.3.2 邻接表
（二） 存储结构的高级语言描述
图的边 （ 邻接表中的链结点 ） 的 C++描述为：
template <class TEdgeInfo>
struct TGrphEdge
{
long edgeEndIdx; //边终点编号
TEdgeInfo edgeInfo; //边信息
TGrphEdge *next; //链指针
};
38
§ 6.3.2 邻接表
（二） 存储结构的高级语言描述
图结点的 C++描述为：
template <class TElem>
struct TGrphNode
{
long nodeIdx; //结点编号
TElem nodeInfo; //结点信息
TGrphEdge * firstOutEdge; //第一条出边的指针
};
39
§ 6.3.2 邻接表
（三） 算法实现的考虑
1,求邻接点, 关联边
? 求以 x为始点 （ 尾 ） 的边时, 只需搜索 x的线性链表；
? 求以 x为终点 （ 头 ） 的结点时, 则要搜索各结点的线性
链表, 检查其中是否有以 x为终点的链表结点, 若 i的线性
链表中有终点为 x的结点, 则 <i,x>就是一条边, 其中 i为
始点 。
40
§ 6.3.2 邻接表
（三） 算法实现的考虑
2,结点, 边的增删
·删除一条边：对有向图, 删除边 <x,y>时, 从 x的线性链表中找到
终点为 y的结点, 并删除之；对无向图, 删除边 (x,y)时, 先在 x的线
性链表中找到终点为 y的结点, 并删除之, 然后在 y的线性链表中找
到终点为 x的结点并删除之 。
·增加新结点：在头数组中增加一个元素即可 。
·增加边：设要增加边 <x,y>,若 x与 y是已存在结点, 则在 x的线性
链表中增加一个结点, 置其终点为 y；对无向图, 还要按同样方法增
加 <y,x>。 若 x或 y是新结点, 则先在头数组中增加对应的元素, 然后
按上法将边 <x,y>加到链表中 。
·删除一个结点：是上述几项操作的复合 。 先删除与待删结点关联
的各个边, 然后再在头数组中删除该结点 。
41
§ 6.3.2 邻接表
（三） 算法实现的考虑
3,求度
·出度：结点 x的出度等于 x的单链表中结点个数 。
·入度：结点 x的入度等于各结点的线性链表中所含的以 x为终点的
链表结点的个数 。 故求入度时要扫描整个邻接表 。
4,路径
基本思想同邻接矩阵 。
? 有时为了操作方便, 对图采用逆邻接表存贮法 。 所谓逆邻接表,
是指将有向图中的各弧的方向掉转后所对应的邻接表 。 对逆邻接表
求入度与出度的方法, 正好与邻接表情况相反 。
42
§ 6.3.3 十字链表（有向图）
（一） 存贮方法
? 基本思想
– 将图中某结点的各前趋视为与它同, 行, 的元素, 而将它的
各后继视为与它同, 列, 的元素, 则可沿用矩阵的十字链表
存贮法存贮图
? 通常, 图的十字链表的, 行, 链表与, 列, 链表不使
用循环结构 。
? 在图的十字链表中, i―行, 对应的线性链表中的元素是
以 i为始点 （ 尾 ） 的边, 而 i―列, 对应的线性链表中的结
点是以 i为终点 （ 头 ） 的边
43
§ 6.3.3 十字链表（有向图）
（一） 存贮方法
? 对于图中的每条边，用如下结构的一个结点描述（称为边结点）：
其中,
边信息：描述对应边的有关信息, 如权 。
起点：边的起点的编号 。
终点：边的终点的编号 。
射入链：指向终点相同的下条边
射出链：指向起点相同的下条边
边信息 起点 终点 射入链 射出链
44
§ 6.3.3 十字链表（有向图）
（一） 存贮方法
? 对于每个图结点，设一个顶点结点，其结构为：
其中：
结点编号：存放结点的编号；
结点信息：存放结点的有关信息；
射入链头：指向该结点的射入链 （ 即以该结点为终点的弧构成的
链 ） 中的第一个结点；
射出链头：指向该结点的射出链（即以该结点为始头的弧构成的
链）中的第一个结点；
? 为了快速访问，可设一个一维数组（称为头数组），存放上述的各顶
点结点。也可在顶点结点中增设一个链域，使各顶点结点链为一条链。
结点编号 射入链头 射出链头结点信息
45
1
2 5
4 3
(a) 一个有向图
1
2
3
4
5
^
3 5 ^ ^
1 3 ^ 1 5 ^1 2 ^
2 1 2 4 ^ ^
4 1 ^
(b) 图（ a）的十字链表
图 -有向图十字链表示例
46
§ 6.3.3 十字链表（有向图）
（二） 高级语言描述
? 有向图的十字链表存贮结构可用 C++描述如下 。
? 边结点定义为：
template <class TEdgeInfo>
struct TGrphEdge
{
TEdgeInfo edgeInfo; //边信息
long startNodeIdx; //边起点编号
long endNodeIdx; //边终点编号
TGrphEdge *nextOut; //指向下一条射出边
TGrphEdge *nextIn; //指向下一条射入边
} ;
47
§ 6.3.3 十字链表（有向图）
（二） 高级语言描述
? 边顶点结点定义为：
template <class TElem>
struct TGrphNode
{
TElem nodeInfo; //边信息
long nodeIdx; //结点编号
TGrphEdge *firstOut; //指向第一条射出边
TGrphEdge *firstIn; //指向第一条射入边
}
48
§ 6.3.3 十字链表（有向图）
（二） 算法实现的考虑
? 图的十字链表是对图的邻接表的一种扩展
– 与邻接表相同的是，它也是对每条边设立一个链表结点。
– 不同的是，它的链表结点增设了一个用于将终点相同的弧链接在一
起的链指针。
? 十字链表实质上是邻接表与逆邻接表的结合
? 由于十字链表中每个链表结点（图中的边对应的结点）有两个链
域，所以它的存贮效率要比邻接表低
? 图的十字链表是图的邻接矩阵的十字链表的变形,二者的主要差别
是
– ①前者的链表结点不需按起点与终点（相当于行号与列号）的大小
排列；
– ②前者的, 行, 与, 列, 链表一般不需构成循环结构。
49
§ 6.3.4 邻接多重表（无向图）
? 邻接多重表是面向无向图的一种链式存贮结构，可视
为由有向图的十字链表演变而来
? 对于无向图，若要按邻接表或十字链表的方法存贮，
则图中每条边对应两个链表结点（边 (x,y)相当于 <x,y>
与 <y,x>），这不仅造成存贮浪费，而且给图的操作维护
带来 麻烦 。
? 限制每个图边对应一个链表结点，将此限制应用于图
的十字链表存贮法上，就导出了图的邻接多重表存贮法。
50
§ 6.3.4 邻接多重表（无向图）
? 邻接多重表的规则
? 图中每条边 (x,y)设一个边结点, 格式为
这里：
边信息：存贮有关边 (x,y)的信息；
起点, 终点：边 （ x,y） 的两个端点的编号；
link1,link2：分别为关联于 x和 y的下条边的指针 。 即 link1
指向关联于结点 x的下条边, 而 link2指向关联于结点 y的下条边 。
边信息 起点 x 终点 y link1 link2
51
§ 6.3.4 邻接多重表（无向图）
? 每个图结点设立一个如下形式的结点（顶点结点）：
这里：
结点编号：图结点的编号；
结点信息：存储有关图结点的信息；
首边指针：指向关联于该结点的第一条边的边结点。
? 为了快速查找顶点结点，可设一个一维数组，存放各顶点结点。
也可在顶点结点中增设链域，将各顶点结点链接在一起。
结点编号 首边指针结点信息
52
1
2
4
3
1
2
3
4
3 1 ^ ^2 1 ^
4 2 ^3 2 ^
4 3
图 - 无向图邻接多重表示例
对无向图，每条边的起点与终点没有指定，所以邻接多重表
在形式上是不唯一的
53
§ 6.4 图的遍历
? 图的遍历的含意是，从图中某结点出发，按某既定方
式访问图中各个可访问到的结点，使每个可访问到的
结点恰被访问一次。
? 图的遍历方式有两种：
– 深度优先
– 广度优先
? 在遍历中，应为每个结点设立一个访问标志
§ 6.4,1 概述
54
? 访问标志的设置有两种方法：
– ①在描述图结的记录中增设一个访问标志位。
– ②另设一个, 访问数组,,令它的每个元素对应于一个图结点访
问标志。这种方法的访问标志很容易多次初始化。
? 从图中某一结点出发，一趟只能遍历到它所在的极大连通分量中
的结点，要想遍历到图中各结点，需进行多趟遍历（每趟遍历一
个极大连通分量）。
? 该过程可描述为：
for (图中每个结点发 v)
if (v尚未被访问过 )
从 v出发遍历该图 ;
§ 6.4,1 概述
55
§ 6.4,2 深度优先遍历
(一 )遍历规则
– 从图中某结点 v0出发,深度优先遍历 （ Depth First Search）图
的规则为：
– 访问 v0；
– 对 v0的各个出点 v01,v02,…, v0m，每次从它们中按一定方式
（也可任选）选取一个未被访问过的结点，从该结点出发按
深度优先遍历方式遍历。
? 显然，因为我们没有规定对出点的遍历次序，所以，
图的深度优先遍历结果一般不唯一。
56
§ 6.4,2 深度优先遍历
?一些遍历结果 （ 结点访问次序 ） 为：
?左图：从 1出发,1,2,4,5；或 1,5,2,4
? 从 2出发,2,1,5,4；或 2,4,1,5
? 右图：从 a出发,a,b,c,d；或 a,b,d,c; … …
1
2 5
4 3
a
b
c
d
图 - 一个有向图（左）和无向图
57
§ 6.4,2 深度优先遍历
(一 )遍历规则
?从图中某结点 v0出发, 深度优先遍历 （ Depth
First Search） 图的规则为：
– 访问 v0；
– 对 v0的各个出点 v01,v02,…, v0m，每次从它们中按
一定方式（也可任选）选取一个未被访问过的结点，
从该结点出发按深度优先遍历方式遍历。
58
1
2 5
4 3
a
b
c
d
图 - 一个有向图（左）和无向图
例如, 对 图 6-0给出的有向图与无向图, 一些遍历结果 （ 结点
访问次序 ） 为：
左图：从 1出发,1,2,4,5；或 1,5,2,4
从 2出发,2,1,5,4；或 2,4,1,5
右图：从 a出发,a,b,c,d；或 a,b,d,c; … …
59
§ 6.4,2 深度优先遍历
(二 )实现方法
?图的深度优先遍历与二叉树的前序遍历相似 。
不同之处有：
① 二叉树每个结点至多有两个可达邻接点 （ 左右儿
子 ）, 而图的可达邻接点数且不定；
② 对二叉树, 沿可达邻接点搜索时不会发生回绕, 但
对图, 若不加特别控制, 就有可能回绕 。
60
?图的深度优先遍历递归算法
longDFS(图 g,结点 v0)
{ //从结点 v0出发, 深度优先遍历图 g,返回访问到的结点总数
int nNodes; //寄存访问到的结点数且
nNodes=1;
访问 v0;
为 v0置已访问标志 ;
求出 v0的第 1个可达邻接点 v;
while (v存在 )
{
if (v未被访问过 ) nNodes=nNodes+DFS(g,v);
求出 v0的下个可达邻接点 v;
}
return nNodes;
}
61
long DFS1(TGrphEdge **g,long n,long v0)
{
long nNodes,i;
nNodex=1;
VisitGrphNode(g,v0); //设该函数用于访问图 g的结点 v0
GgphNodeSetVisited(g,v0,1);
//设该函数用于设置图 g中的结点 v0的访问标志 （ 第三个参数 0/1—未 /已访问 ）
for (i=0; i<n; i++)
{
if (g[v0][i]!=无边标志 )
if (!GrphGetVisited(g,i))
//设 GrphGetVisited(g,i)返回 g中结点 i的访问标志 (0—未访问 )
nNodes = nNodes+DFS1(g,i);
} //for
return nNodes;
}
针对邻接矩阵
的 深度优先遍
历递归算法
62
long DFS2(TGrphNode *g,long v0)
{
long nNodes,i;
TGrphEdge *p;
nNodex=1;
VisitGrphNode(g,v0); //设该函数用于访问图 g的结点 v0
GgphNodeSetVisited(g,v0,1);
//设该函数用于设置图 g中的结点 v0的访问标志 （ 第三个参数 0/1—未 /已访问 ）
p = g[v0].firstOutEdge;
while (p!=NULL)
{
if (!GrphGetVisited(g,p->edgeEndIdx))
//设 GrphGetVisited(g,k)返回 g中结点 k的访问标志 (0—未访问 )
nNodes = nNodes+FDS2(g,p->edgeEndIdx);
p = p->next;
}
return nNodes;
}
针对邻接表 的
深度优先遍历
递归算法
63
§ 6.4,3 广度优先遍历
(一 )图的分层
?图的分层就是要识别出图中每个结点属于的层次, 即给
每个结点编一个层次号
?分层时, 应先确定一个或几个参考点
?以结点 v0为参考点的图的分层的定义 （ 非过程化 ）, 这
里用 Level(v)表示结点 v的层号：
– 令 Level(v0) = 1
– 对任意的 v≠v0,若存在 v0到 v的通路, 则令
Level(v)=1+MIN{ Level(u) | <u,v>是图的边 }
– 否则令 Level(v)=∞
64
1
2 5
4 3
a
b
c
d
图 - 一个有向图（左）和无向图
左图：从 1出发分层：层号
为 1的结点,1
层号为 2的结点,2,5
层号为 3的结点,4
层号为 ∞的结点,3
左图：从 2出发分层：层号
为 1的结点,2
层号为 2的结点,1,4
层号为 3的结点,5
层号为 ∞ 的结点,3
右图：
从 a出发分层：层号为 1
的结点,a
层号为 2的结点,b,d
层号为 3的结点,c
65
§ 6.4,3 广度优先遍历
(二 )图的广度优先遍历方法
? 从结点 v0 出发, 广 度 优 先 遍 历
（ Breadth/Width First Search） 图的方法是
按从 v0出发对图的分层的层次号的大小次序访问结
点, 即先访问第一层上结点, 然后访问第二层上结
点, … 等等, 同层上次序可按邻接点次序或任意 。
66
1
2 5
4 3
a
b
c
d
图 - 一个有向图（左）和无向图
左图：从 1出发广度优先遍历结果,1,2,5,4
左图：从 2出发广度优先遍历,2,1,4,5
右图：从 a出发广度优先遍历,a,b,d,c
67
§ 6.4,3 广度优先遍历
(三 )算法实现
? 广度优先遍历是一种分层处理, 对这种分层处理,
使用队列是自然的 。 我们设立一个队列, 任何时刻, 均
保证它满足下列条件：
– 队中元素是已访问过的结点的可达邻接点；
– 队中元素是尚未被访问过的；
– 队中元素按它们所处的层次的先后排列 。
? 这样, 我们就可不断地每次从队中取出一个元素并
访问之, 然后再将该元素的尚未被访问过的邻接点进队,
直至队空 。
68
§ 6.4,3 广度优先遍历
(三 )算法实现
longBFS(图 g,结点 v0）
{ //在图 g中从 v0出发按广度优先遍历方式遍历 g,返回遍历到的结点
数目
longnNodes=0;
初始化队 Q;
if （ v0存在 ）
{ v0入 Q;
置 v为已访问标志 ;
}
未涉及到具体
的存贮结构 的
广度优先遍历
算法
69
while (Q不空 )
{
队 Q头元素出队并送 v;
访问 v;
nNodes++; //对已访问元素计数
求出 v的第一个可达邻接点 w;
while (w存在 )
{
if (w尚未被访问过 )
{
w入 Q;
置 w为已访问标志 ;
}
求 v的下个可达邻接点 w;
}
return nNodes;
}
70
long BFS1(TGrphEdge **g,long n,long v0)
{
long nNodes=0;
long v,w;
char *visited;
TQueue<long> Q(n);
visited = new char[n];
for (i=0; i<n; i++) visited[i] = 0; //初始化访问标志数组
针对邻接矩阵
的
广度优先遍历
算法
71
if (v0>0 && v0<n) Q.QPush(v0);
while (!Q.Empty())
{
v = Q.QPop();
VisitGrphNode (g,v); //访问结点 v
nNodes++;
for (w=0; w<n; w++)
if (g[v][w]!=无边标志 )
if (!visited[w]) Q.QPush(w);
} //while
} //while
delete [] visited;
return nNodes;
}
72
long BFS2(TGrphNode *g,long n,long v0)
{
long nNodes=0;
TGrphEdge *p;
char *visited;
TQueue<long> Q(n);
visited = new char[n];
for (i=0; i<n; i++) visited[i] = 0; //初始化访问标志数组
针对邻接表 的
广度优先遍历
算法
73
if (v0>0 && v0<n) Q.QPush(v0);
while (!Q.Empty())
{
v = Q.QPop();
VisitGrphNode (g,v); //访问结点 v
visited[v]=1;
nNodes++;
p = g[v],firstOutEdge;
while (p!=NULL)
{
if (!visited[p->edgeEndIdx]) Q.QPush(p->edgeEndIdx);
p = p->next
}//while
}//while
delete [] visited;
return nNodes;
}
74
§ 6.5 最小生成树
? 无向图的无回路的连通的生成图称为该无向图的生成
树。这种树是无向树（上章主要介绍的为有向树）
? 给图的各边分别赋予一个权, 称边权之和最小的生成
树称为 最小生成树
? 是图的一种最优化问题的抽象
? 在诸如网络构造（如何构造连同 n个站点的网络，有通
迅线路网、交通运输网 … ）之类的应用中占重要地位。
? 两个著名的算法 ── Kruskal算法与 Prim算法
75
§ 6.5.1 Prim算法
(一）基本思想
?贪心法, 它的基本原则是使每步满足：
(a)当前生成的图是连通的
(b)当前生成的图不含回路
(c)当前生成的图是最小生成树的一部分
76
§ 6.5.1 Prim算法
(二） Prim算法
?设 N=(V,E)是无向图, 求它的最小生成树 T=(V',E')的
Prim算法为：
[1] 从 V中任取一结点放入 V'；
[2] 在所有的端点分别在 (V-V')和 V'中的边中, 选一条权
最小的加入 E'；
[3] 将边 E'在 (V-V')中的顶点放入 V'；
[4] 重复步骤 [2]~[3],直到 V'中包含了所有结点为止 。
77
2
C
4
5
1 6A
B
D
E
8
9 2
C
4
5
1 A
B
D
E
(a) 无向图 (b) 无向图 (a)的一棵最小生成树
步骤 V-V' V' 连接 (V-V')与 V’的边 T'
0 BCDE A AB,AE 空
1 CDE AB AE,BE,BD,BC AB
2 DE ABC AE,BE,BD,CD AB,BC
3 E ABCD AE,BE,DE AB,BC,BD
4 空 ABCDE 空 AB,BC,BD,BE
(c) 无向图 (a)的最小生成树生成过程
图 - Prime最小生成树算法示例 (结点 a为初始选择结点 )
78
§ 6.5.1 Prim算法
(三） Prim算法的正确性讨论
? 说明 Prim算法满足本节中提出的三项原则
(a) 因为每次都是从连接 (V-V')与 V'中的边中选一条
边, 故每次构成的部分树是连通的 。
(b) 每次构成的部分树也是肯定无回路的
(c) Prim算法每步生成的图, 均属最小生成树
79
§ 6.5.2 Prim算法的实现
(一）基本思想
? Prim最小生成树的生成过程, 是个逐步扩大 V'的过程：
每次从连接 V'与 (V-V')的边中选择一条最小者, 将其
在 (V-V')中的结点加入到 V'中 。
? 因此, 在算法实现中, 必须记下当前的 V'与 (V-V')之
间的边的信息, 以备选择, 我们称这种信息为候选集 。
80
§ 6.5.2 Prim算法的实现
(一）基本思想
? 称
– V'中结点 ──红点, 即部分生成树的结点；
– (V-V')中的结点 ──白点, 即尚未被加入到部分生成树中的结
点；
– V'中结点构成的边 （ E'中的边 ） ──红边, 即部分生成树的边；
– (V-V')中结点构成的边 （ E的边 ） ──白边, 即原图中的边
– 连接 V'与 (V-V')的边 ── 蓝边, 即当前候选边 （ 候选集 ） 。
81
§ 6.5.2 Prim算法的实现
(一）基本思想
? 生成最小树的过程, 就是不断地从当前蓝边中选出最小者, 涂成
红色 （ 将它的白结点也涂成红色 ）, 然后收集新出现的蓝边 。
? 该过程描述如下：
从 V中任选一结点加到 V'中；
设置初始候选集 （ 蓝边集 ） ；
while（ V'中尚未包含全部结点 ）
{
从当前蓝边集中选一条最小者；
将所选最小边加入到 E'中；
将所选最小边的白结点加入到 V'；
调整候选集 （ 蓝边集合 ） ；
}
82
§ 6.5.2 Prim算法的实现
(一）基本思想
? 将从蓝边中选出的边涂成红色后, 它的白结点也要涂
成红色, 故与该白点关联的那些白边也要变为蓝边,
这就是说, 蓝边集合要改变 （ 减与增 ）, 这种改变过
程, 我们称为调整候选集 。
83
24
8
160 4020
80 30
70
6
95
7
3 15
25
95
45 35
75
图 - 最小生成树候选集调整
V-V' V'
只需记录蓝边集中最小者
84
§ 6.5.2 Prim算法的实现
(二）数据结构设计
1,图
这里, 用邻接矩阵表示图 （ 作为输入数据 ） 。 设 g为邻接矩阵, 它的元
素定义为
∞,若 i与 j之间无边
g[i][j] =
权值,若 i与 j之间有边
85
§ 6.5.2 Prim算法的实现
(二）数据结构设计
2,最小生成树
最小生成树为生成的结果 （ 输出数据 ）, 用边集表示 。 边
集用一个一维数组表示 。 令树的每条边对应于一个数
组元素, 数据元素为如下形式的三元组：
（ 边始点, 边终点, 边权 ）
86
§ 6.5.2 Prim算法的实现
(二）数据结构设计
3,候选集 Close
即蓝边集合, 用一维数组表示 。 数组的每个元素代表一条蓝
边, 它的白点编号为它在树组中的下标, 而它的红点编
号及权值则记录在数组元素中, 若与白点关联的蓝边不
止一条, 则 Close中记录其中权值最小的那条 。
Close数组元素的结构为：
(vex,lowCost)
87
§ 6.5.2 Prim算法的实现
(二）数据结构设计
其中的 vex与 lowCost分别表示蓝边的红端点编号与兰边的权值 。
Close的具体定义为：
· 对每个 v∈ V-V'（ 白点 ）
Close[v].lowCost = MIN{(v,u)上的权值 | u∈ V' }
Close[v].vex = u //u为满足上式的红点, 若 Close[v].lowCostwe=∞，
则 u无关
· 对每个 u∈ V'（ 红点 ）
close[u].lowCost=0
close[u].vex=无关
88
表 6-1 Close示例（ *--无关）
（ a）图 6-1对应的候选集
结点 v 1 2 3 4 5 6 7 8 9
Close[v].vex * * * * * 4 1 * 8
Close[v].lowCost 0 0 ∞ 0 ∞ 20 40 0 30
（ b）在选择一条蓝边，调整候选集后
Close[v].vex * * 6 * 6 * 6 * 8
Close[v].lowCost 0 0 15 0 45 0 35 0 30
24
8
160 4020
80 30
70
6
95
7
3 15
25
95
45 35
75
图 - 最小生成树候选集调整
V-V' V'
89
§ 6.5.2 Prim算法的实现
(三）算法实现
? 该算法的时间复杂度为 O(n2)（ n为结点数）
struct TTreeEdge //最小生成树的边类型
{
long v1,v2; //边起点与终点编号
float weight; //边权
};
90
longMinSpanningTree(TGrphEdge *g,long n,TTreeEdge *minTree)
{//求具有 n个结点的图 g的最小生成树, 结果存于边数组 minTree
//返回最小生成树的边数 。 返回值不等于 n-1时, 表示出错
struct TCloseRec //候选集类型
{
longvex;
float lowCost;
} ;
91
longi,j,k;
float minW;
TCloseRec *close;
i=0;
close = new TClose[n];
for (i=1; i<n; i++)
{
close[i].vex = 0; close[i].lowCost = g[i][0];
} //初始化候选集, 将结点 0作为始点加入 V'
92
close[0].lowCost = 0; //为结点 0做红点标志
for (i=0; i<n-1; i++) //不断挑选蓝边并调整候选集, 每次为 minTree生成一个元素
{
for (k=1; k<n; k++) //找第一个白点
if (close[k].lowCost!=0) break;
for (j=k+1; j<n; j++) //找最小蓝边
if (close[j].lowCost!=0)
if (close[j].lowCost < clost[k].lowCost )
k=j;
//下面将所找出的最小蓝边 （ k,close[k].vex） 涂红
minTree[i].v1 = k;
minTree[i].v2 = close[k].vex;
minTree[i].weight = close[k].lowCost;
close[k].lowCost=0;
93
//下面调整候选集
for (j=1; j<n; j++) //检查每个邻接于 k的 (白 )边
if (close[j].lowCost > g[j][k] )
{
close[j].lowCost = g[j][k];
close[j].vex = k;
}
} //for（ i=0; …
delete [] close;
return i;
};
94
§ 6.5,3 Kruskal算法
(一）基本方法
? Prim算法不是按边权不减的次序生成最小生成树的
? Kruskal算法是一种与 Prim算法不同的算法，它按边不减
的次序生成最小生成树
? Kruskal算法并不保证每步生成的结果是连通的（从而部
分结果可能不是树）
95
§ 6.5,3 Kruskal算法
(一）基本方法
? 设 G=(V,E)是一个有向图, T是它的最小生成树的边集, 则由 G生成 T
的 Kruskal算法描述如下 （ n为 G中结点个数 ）,
置 T为空集；
while (T中边数 <n)
{
从 E中挑选一条最小边 (v,u);
从 E中删去 (v,u);
if ( (v,u)在 T中不产生回路 ) )
将 (v,u)加入 T中 ;
else舍弃 (v,u);
}
96
图 - Kruskal最小生成树算法示例
52
C
7
3
1 4A
B
D
E
82
2
1 A
B选出 AB 选出 ED 选出 BE
1 A
B
D
E
2
1 A
B
D
E
2
3 选出 AE,
作废
1 A
B
D
E
2
3
选出 BC
1 A
B
D
E
2
3
52
C
97
§ 6.5,3 Kruskal算法
(一）实现方法
? Kruskal算法的实现涉及到生成森林, 是按边权递增的次
序连通森林的过程
? 该过程具体描述如下：
long MinSoanningKruskal(G,T)
{//G─无向图, T─最小生成树边集
// TS─生成森林
long cnt=0;
98
置 T为空 ;
将图 G的每个结点分别作为一棵树放入 TS中 ;
while (TS中树的个数大于 1)
{
从 G的边集选一条尚未被选择的代价最小的边 (u,v);
对 (u,v)做已选择标志；
if (u与 v分别属于 TS中两棵不同的树 Tu与 Tv)
{
cnt++;
合并 Tu与 Tv;
将 (u,v)加入到 T中 ;
}
}//while
return cnt;
}
第 6 章 图结构
? 若干个结点与若干条边构成的结构
– 结点是一些具体对象的抽象
– 边是对象间的关系
? 图是一种复杂的非线性结构，它有极强的表达
能力
? 图中结点可有多个前趋和多个后继
? 这里着重讨论图的存贮结构与基本操作的实现
2
§ 6.1 图的基本概念
§ 6.1.1 图的概念
1,图
? 图是由若干个结点和若干条边构成的结构，每个结点
具有任意多个前驱和后继。
– 结点集合：结点代表对象
– 边集合：两结点之间的边表示它们代表的对象之间的关系
? 在具体应用中，结点与边要被赋予具体的含意,如
– 结点代表城市
– 边代表城市之间的行程。
1
2 5
4 3
a
b
c
d
3
§ 6.1.1 图的概念
1,图
图是形为
G=(V,R)
的数据结构, 其中,
V={x|x属于数据对象 }
R={VR}
VR={<x,y> | p(x,y)∧ x∈ V∧ y∈ V}
这里,p(x,y)是 V上的一个谓词,p(x,y)为真当且仅当 x与 y
存在问题世界中的关系。
图的形式化
定义
4
§ 6.1.1 图的概念
2,有向 /无向图
若二元关系 VR是对称的 （ 即对任意 x与 y,若有
<x,y>∈ VR,则必有 <y,x>∈ VR）, 则称图 G是
无向图, 否则称 有向图 。 对无向图, 我们用
(x,y)表示 <x,y>。
1
2 5
4 3
a
b
c
d
5
§ 6.1.1 图的概念
? 3,结点、边、弧
? 图中的数据元素称为 结点 （或顶点）
? 有时为了强调，对有向图，称 <x,y>为 弧, x与 y分别为 弧尾 与 弧
头,
? 称 x与 y分别为 <x,y>的 始点 与 终点,
? 称 y为 x的 出点 /可达邻接点,
? 称 x为 y的 入点,称 <x,y>为 x的 出边 /出弧, <x,y>为 y的 入边 /入
弧 。
? 对无向图，称 <x,y>为 边 。
? 在讨论图中，一般用自然数串给结点编号。
1
2 5
4 3
a
b
c
d
6
【 例 6-1】 设有两个二元组 G1=(V1,R1)与 G2=(V2,R2),其中,
V1={1,2,3,4,5}
R1={VR1}
VR1={<1,2>,<1,5>,<2,1>,<2,4>,<3,5>,<4,1>}
V2={a,b,c,d}
R2={VR2}
VR2={(a,b),(a,d),(b,d),(d,c)}
1
2 5
4 3
a
b
c
d
(a) 有向图 (a) 无向图
【 图 -】 图示例
7
§ 6.1.1 图的概念
4,邻接, 关联
? 对图中任意结点 x与 y，若它们之间存在边的关
系（即有 <x,y>，或 <y,x>），则称 x与 y邻接,
它们互为 邻接点 。同时称 x或 y与边 <x,y>（或
<y,x>或 (x,y)） 关联 。
1
2 5
4 3
a
b
c
d
8
§ 6.1.1 图的概念
5,度
? 对任一结点 x,称以它为头的弧的个数为它的 入度
? 称以它为尾的弧的个数为它的 出度
? 称它的入度与出度之和为它的 度 。
? 对无向图, 无出度入度之分, 直接称与它关联的边的
个数为它的 度 。
1
2 5
4 3
a
b
c
d
9
§ 6.1.1 图的概念
6,权
? 权是一个数值量, 是某些信息的数字化抽象 。
? 权分边权与结点权, 分别是边与结点的问题世界所关
心的信息的数值化表示 。
? 例如, 若结点代表城市, 则边权可代表城市之间的交
通费用 。
1
2 5
4 3
60
70200
170 70
90
10
§ 6.1.1 图的概念
7,路径 （ 通路 ）
? 对有向图, 若存在弧序列
<x0,x1>,<x1,x2>,…, <xn-1,xn>
且 n≥1,则称从 x0到 xn有通路 （ 路径 ） 。 上列序列称为
x0到 xn的 路径 。 该路径也可表示为
(x0,x1,…,xn)
1
2 5
4 3
11
§ 6.1.1 图的概念
7,路径 （ 通路 ） （ 续 ）
? 对无向图, 若有边序列
(x0,x1),(x1,x2),…, (xn-1,xn)
且 n≥1,则称 x0与 xn之间 有路径 （ 通路 ）, 该路径可用
上列边序列表示, 亦可用下列结点序列表示
(x0,x1,…,xn)
a
b
c
d
12
§ 6.1.1 图的概念
7,路径 （ 通路 ） （ 续 ）
? 路径中边的数目称为 路径长 。
? 若 x0=xn,则称相应的路径为 回路 /环路 。
? 若在路径 (x0,x1,…,xn)中, 除 x0与 xn外, 任意其它结
点均不相同, 则称该路径为 简单路径 。 起点与终点重合
的简单路径称为 简单回路 。
a
b
c
d
1
2 5
4 3
13
§ 6.1.1 图的概念
8,子图 /生成图
? 若某图 G'的结点集合与边集合分别是另一图的 G的结
点集合和边集合的子集, 则称 G'为 G的 子图 。
? 设有两个图 G与 G',若它们的结点集合相同, 但 G'的
边集合是 G的边集合的子集, 则称 G'是 G的 生成图 。
? 显然, 生成图一定是子图, 但反之未必 。
a
b
c
d
1
2 5
4 3
14
§ 6.1.1 图的概念
9,连通
? 若图中任意两结点间均有通路 （ x到 y与 y到 x）, 则称
该图是 （ 强 ） 连通的 。
? 若图中某子图是连通的, 则称该子图为一个 连通分量 。
? 若 G的某子图 G'是连通的, 并且, 若有 G的另一子图
G''包含图 G',则 G''必不连通,则称 G'是 极大连通分量 。
a
b
c
d
1
2 5
4 3
15
§ 6.1.1 图的概念
9,连通 （ 续 ）
? 对于有向图, 若任意两结点间至少有单向通路, 但有
些结点无双向通路, 则称该图为 弱连图 。
? 类似地, 也有 弱连通分量 的概念 。
1
2 5
4 3
16
§ 6.1.1 图的概念
10,生成树
无回路的连通的无向图的生成图, 称为该无
向图的 生成树 。
【 定理 6-1】 生成树中边的个数为结点个数
减 1.
a
b
c
d
a
b
c
d
a
b
c
d
17
§ 6.1.2 图的基本操作
① 检索：
·按结点 （ 编号或内容 ） 检索结点 （ 位置 ）
·按边的两顶点检索边
② 插入：
·插入结点
·插入边
③ 删除：
·删除结点及与其关联的边
·删除边
18
§ 6.1.2 图的基本操作
④ 求邻接点, 关联边
⑤ 求度 （ 入度与出度 ）
⑥ 求路径
⑦ 求子图
⑧ 求生成图
⑨ 求生成树
⑩ 求连通分量
19
§ 6.1.2 图的基本操作
⑾ 求拓扑序列 （ 有向图 ）
⑿ 图的遍历
⒀ 求关键路径
⒁ 求最短路径
⒂ 求最小生成树
…………
20
§ 6.2 图的抽象对象模型
? 考虑仅从逻辑关系出发时，图结点和整个图对
象应具有的性质
? 由于图结点的关系不象其他结构中结点那样有
限制，所以它的抽象结构比较复杂。
21
§ 6.2.1 图结点抽象模型
template <class TElem>
struct TGraphNode0
{
long no;
TElem info;
virtual long GetNo ( ) {return no;}; //返回本结点的编号
virtual void SetNo(long mNo) {no = mNo;}; //为本结点设置编号值
virtual TElem& GetElem ( ) {return info;}; //返回本结点的值
virtual TElem& SetElem (TELem &e)
{ info = e; return info;}; //为本结点设置元素值
22
§ 6.2.1 图结点抽象模型
virtual TGrphNode0 *GetSucc (long sucNo)=0;
//返回本结点的第 sucNo个后继结点的地址
virtual TGrphNode0 *GetPrior (long preNo)=0;
//返回本结点的第 pre个前驱结点的地址
virtual TGrphNode0 *SetSucc (long sucNo,TGrphNode* pNode)=0;
//为本结点设置第 sucNo个后继
virtual TGrphNode0 *SetPrior (long preNo,TGrphNode* pNode)=0;
//为本结点设置第 preNo个前驱
virtual long GetInDegree ( )=0;
//返回本结点的入度值
virtual long GetOutDegree ( )=0;
//返回本结点的出度值
};
23
§ 6.2.2 图的边对象抽象模型
template <class TElem>
struct TGrphEdge
{
long startNo,endNo;
TELem info;
virtual TElem &GetElem ( ) { return info;};
virtual TElem &SetElem (TElem &e) { info = e; return info;};
virtual long GetStartNo ( ) { return startNo;};
virtual long GetEndNo ( ) { return endNo;};
virtual void SetStartNo (long mNo) { startNo = mNo; };
virtual void SetEndNo (long mNo) { endNo = mNo; };
};
24
§ 6.2.3 图抽象对象模型
template <class TELem,class TEdgeElem>
class TGrph0
{
public:
virtual TGrphEdge<TEdgeElem> *AddEdge(long startNo,long endNo,
TEdgeElem &ee)=0;
virtual TGrphNode0<TElem> *AddNode(long mNo,TElem &nodeInfo) =0;
virtual TGrphNode0<TElem> *DeleteNode(long mNo) =0;
virtual TGrphEdge<TElem> *DeleteEdge(long startNo,long endNo) =0;
25
virtual long Cluster(TGrphNode0<TElem>* pStartNode,TElem**e,
TTraverseMode tm)=0;
virtual long Cluster(TGrphNode0<TElem>* pStartNode,long**nos,
TTraverseMode tm)=0;
virtual long Cluster(TGrphNode0<TElem>* pStartNode,
TGrphNode0<TElem>* pNodes,TTraverseMode tm)=0;
virtual TGrphNode<TElem> *Locate(longnNo)=0;
virtual TGrphEdge<TEdgeElem> *Locate(longstartNo,long endNo)=0;
virtual TGrphNode<TElem> *Locate(TElem *e,long sn=1)=0;
26
virtual long GetPath(long startNo,long endNo,long sn,long
*pathNodeNo)=0;
virtual long GetPath(longstartNo,long endNo,long sn,
TGrphNode0<TElem>* pathNode) =0;
virtual long GetPathShortest(longstartNo,TDijkPath *path) =0;
virtual long GetPathShortest(long**path) =0;
};
struct TDijkPath
{
float len;
long pre;
};
27
§ 6.3 图的存贮结构
? 必须显式地存贮结点之间的关系 （ 即边 ） 的信
息 。 一般有两大类方法：
① 用边的集合表示图；
②用链接关系表示图。
邻接矩阵法
邻接表
十字链表
邻接多重表
28
§ 6.3.1 邻接矩阵法
（一）存贮方法
? 用边的集合表示图的方法
? 边集合用一个二维数组表示
? 数组每个元素表示一条边，它的两个下标分别表示边
的两个端点的编号
? 结点编号要用连续的自然数，使得能与数组下标对应
29
§ 6.3.1 邻接矩阵法
（一）存贮方法
边 <i,j>的权：若 <i,j>是边
A[i][j]=
特殊标志,若 <i,j>不是边
若不考虑边的权, 则 A[i][j]只表示边 <i,j>是否存在, 即
1,若 <i,j>是边
A[i][j]=
0或 ∞,若 <i,j>不是边
?同样适合于无向图
?用 (i,j)代替 <i,j>
?对无向图，邻接矩阵是个
对称矩阵，可按对称矩阵
的压缩存贮方法存贮
30
1 2 3 4 5 a b c d
1 0 1 0 0 1
2 1 0 0 1 0 a 1 0 1 0 1
3 0 0 0 0 5 b 2 1 0 0 1
4 1 0 0 0 0 c 3 0 0 0 0
5 0 0 0 0 0 d 4 1 1 0 0
下图的邻接矩阵
a
b
c
d
1
2 5
4 3
空间复杂度正
比于图的结点
个数的平方
31
§ 6.3.1 邻接矩阵法
（二） 算法实现的考虑
1,结点, 边的增删
? 对邻接矩阵, 结点或边的增删的算法校简单, 但一般要移动元素 。
? 删除边：删除一条边比较简单, 只需将对应元素置无边标志；
? 删除点：删除一个结点, 要将与它关联的边一同删除, 即删除结
点在矩阵中对应的行与列 。
? 增加边：为现有两结点间增加一条边, 只需将对应矩阵元素置边
信息 。
? 增加点：增加一个新结点, 要在矩阵中相应位置插入一行一列 。
? 增加新结点边：插入带新结点的边，先插入新结点，然后置边信
息。
32
§ 6.3.1 邻接矩阵法
（二） 算法实现的考虑
2,度的计算
出度：结点 i的出度, 等于 i所对应的行上的非特殊元素的个数 。
入度：结点 i的入度等于 i所对应的列上的非特殊元素的个数 。
3,找邻接点 /判别是否有边
对邻接矩阵, 判别是否有边是直接的, 即要知结点 i到 j是否有边,
只要测试元素 A[i][j]即可 。 至于找邻接点, 则是个依次判别是否有边
的问题 。
33
§ 6.3.1 邻接矩阵法
（二） 算法实现的考虑
4,找路径
要找出结点 x到结点 y之间的路径, 即 path(x,y),按下列方法进行：
Path(x,y)
{
if (x==y) return x; //所找的路径为 (x)，
if (若 x到 y有边 ) return (x,y); //所找的路径为 (x,y)
for (x的每个直接可达点 u)
{
if (u尚未试探过 )
if (Path(u,y)存在 ) return (x)+Path(u,y);
}
return (); //空路径
}
可适合于
任意存贮
结构
34
§ 6.3.2 邻接表
（一） 存贮方法
? 图的邻接表存贮法与树及树的邻接表存贮法类
似, 其具体方法为：
·为图中每个结点 x建立一个线性链表
·对无向图, x的线性链表的每个元素, 分别存放存放
与 x的各邻接点构成的边的信息 。
·对有向图, x的线性链表的每个元素, 分别存放以 x
为始点的各个弧的信息 。
35
§ 6.3.2 邻接表
（一） 存贮方法
? 线性链表的结点结构为：
?
·为每个图结点, 设立一个如下形式的结点：
? 各结点可以存储在一个一维数组 （ 称为头数组 ） 中
（ 每个数组元素分别对应一个图结点 ）, 也可以增设一
个链指针, 使各结点链在一起, 形成另一个单链表 。
边终点编号 边内容 链指针
结点编号 结点内容 链头指针
36
2 5 ^
1 4 ^
5 ^
1 ^
1
2
3
4
^5
下图对应的邻接矩阵
当边数较少时，
该存贮方式的存
贮利用率更高
a
b
c
d
1
2 5
4 3
37
§ 6.3.2 邻接表
（二） 存储结构的高级语言描述
图的边 （ 邻接表中的链结点 ） 的 C++描述为：
template <class TEdgeInfo>
struct TGrphEdge
{
long edgeEndIdx; //边终点编号
TEdgeInfo edgeInfo; //边信息
TGrphEdge *next; //链指针
};
38
§ 6.3.2 邻接表
（二） 存储结构的高级语言描述
图结点的 C++描述为：
template <class TElem>
struct TGrphNode
{
long nodeIdx; //结点编号
TElem nodeInfo; //结点信息
TGrphEdge * firstOutEdge; //第一条出边的指针
};
39
§ 6.3.2 邻接表
（三） 算法实现的考虑
1,求邻接点, 关联边
? 求以 x为始点 （ 尾 ） 的边时, 只需搜索 x的线性链表；
? 求以 x为终点 （ 头 ） 的结点时, 则要搜索各结点的线性
链表, 检查其中是否有以 x为终点的链表结点, 若 i的线性
链表中有终点为 x的结点, 则 <i,x>就是一条边, 其中 i为
始点 。
40
§ 6.3.2 邻接表
（三） 算法实现的考虑
2,结点, 边的增删
·删除一条边：对有向图, 删除边 <x,y>时, 从 x的线性链表中找到
终点为 y的结点, 并删除之；对无向图, 删除边 (x,y)时, 先在 x的线
性链表中找到终点为 y的结点, 并删除之, 然后在 y的线性链表中找
到终点为 x的结点并删除之 。
·增加新结点：在头数组中增加一个元素即可 。
·增加边：设要增加边 <x,y>,若 x与 y是已存在结点, 则在 x的线性
链表中增加一个结点, 置其终点为 y；对无向图, 还要按同样方法增
加 <y,x>。 若 x或 y是新结点, 则先在头数组中增加对应的元素, 然后
按上法将边 <x,y>加到链表中 。
·删除一个结点：是上述几项操作的复合 。 先删除与待删结点关联
的各个边, 然后再在头数组中删除该结点 。
41
§ 6.3.2 邻接表
（三） 算法实现的考虑
3,求度
·出度：结点 x的出度等于 x的单链表中结点个数 。
·入度：结点 x的入度等于各结点的线性链表中所含的以 x为终点的
链表结点的个数 。 故求入度时要扫描整个邻接表 。
4,路径
基本思想同邻接矩阵 。
? 有时为了操作方便, 对图采用逆邻接表存贮法 。 所谓逆邻接表,
是指将有向图中的各弧的方向掉转后所对应的邻接表 。 对逆邻接表
求入度与出度的方法, 正好与邻接表情况相反 。
42
§ 6.3.3 十字链表（有向图）
（一） 存贮方法
? 基本思想
– 将图中某结点的各前趋视为与它同, 行, 的元素, 而将它的
各后继视为与它同, 列, 的元素, 则可沿用矩阵的十字链表
存贮法存贮图
? 通常, 图的十字链表的, 行, 链表与, 列, 链表不使
用循环结构 。
? 在图的十字链表中, i―行, 对应的线性链表中的元素是
以 i为始点 （ 尾 ） 的边, 而 i―列, 对应的线性链表中的结
点是以 i为终点 （ 头 ） 的边
43
§ 6.3.3 十字链表（有向图）
（一） 存贮方法
? 对于图中的每条边，用如下结构的一个结点描述（称为边结点）：
其中,
边信息：描述对应边的有关信息, 如权 。
起点：边的起点的编号 。
终点：边的终点的编号 。
射入链：指向终点相同的下条边
射出链：指向起点相同的下条边
边信息 起点 终点 射入链 射出链
44
§ 6.3.3 十字链表（有向图）
（一） 存贮方法
? 对于每个图结点，设一个顶点结点，其结构为：
其中：
结点编号：存放结点的编号；
结点信息：存放结点的有关信息；
射入链头：指向该结点的射入链 （ 即以该结点为终点的弧构成的
链 ） 中的第一个结点；
射出链头：指向该结点的射出链（即以该结点为始头的弧构成的
链）中的第一个结点；
? 为了快速访问，可设一个一维数组（称为头数组），存放上述的各顶
点结点。也可在顶点结点中增设一个链域，使各顶点结点链为一条链。
结点编号 射入链头 射出链头结点信息
45
1
2 5
4 3
(a) 一个有向图
1
2
3
4
5
^
3 5 ^ ^
1 3 ^ 1 5 ^1 2 ^
2 1 2 4 ^ ^
4 1 ^
(b) 图（ a）的十字链表
图 -有向图十字链表示例
46
§ 6.3.3 十字链表（有向图）
（二） 高级语言描述
? 有向图的十字链表存贮结构可用 C++描述如下 。
? 边结点定义为：
template <class TEdgeInfo>
struct TGrphEdge
{
TEdgeInfo edgeInfo; //边信息
long startNodeIdx; //边起点编号
long endNodeIdx; //边终点编号
TGrphEdge *nextOut; //指向下一条射出边
TGrphEdge *nextIn; //指向下一条射入边
} ;
47
§ 6.3.3 十字链表（有向图）
（二） 高级语言描述
? 边顶点结点定义为：
template <class TElem>
struct TGrphNode
{
TElem nodeInfo; //边信息
long nodeIdx; //结点编号
TGrphEdge *firstOut; //指向第一条射出边
TGrphEdge *firstIn; //指向第一条射入边
}
48
§ 6.3.3 十字链表（有向图）
（二） 算法实现的考虑
? 图的十字链表是对图的邻接表的一种扩展
– 与邻接表相同的是，它也是对每条边设立一个链表结点。
– 不同的是，它的链表结点增设了一个用于将终点相同的弧链接在一
起的链指针。
? 十字链表实质上是邻接表与逆邻接表的结合
? 由于十字链表中每个链表结点（图中的边对应的结点）有两个链
域，所以它的存贮效率要比邻接表低
? 图的十字链表是图的邻接矩阵的十字链表的变形,二者的主要差别
是
– ①前者的链表结点不需按起点与终点（相当于行号与列号）的大小
排列；
– ②前者的, 行, 与, 列, 链表一般不需构成循环结构。
49
§ 6.3.4 邻接多重表（无向图）
? 邻接多重表是面向无向图的一种链式存贮结构，可视
为由有向图的十字链表演变而来
? 对于无向图，若要按邻接表或十字链表的方法存贮，
则图中每条边对应两个链表结点（边 (x,y)相当于 <x,y>
与 <y,x>），这不仅造成存贮浪费，而且给图的操作维护
带来 麻烦 。
? 限制每个图边对应一个链表结点，将此限制应用于图
的十字链表存贮法上，就导出了图的邻接多重表存贮法。
50
§ 6.3.4 邻接多重表（无向图）
? 邻接多重表的规则
? 图中每条边 (x,y)设一个边结点, 格式为
这里：
边信息：存贮有关边 (x,y)的信息；
起点, 终点：边 （ x,y） 的两个端点的编号；
link1,link2：分别为关联于 x和 y的下条边的指针 。 即 link1
指向关联于结点 x的下条边, 而 link2指向关联于结点 y的下条边 。
边信息 起点 x 终点 y link1 link2
51
§ 6.3.4 邻接多重表（无向图）
? 每个图结点设立一个如下形式的结点（顶点结点）：
这里：
结点编号：图结点的编号；
结点信息：存储有关图结点的信息；
首边指针：指向关联于该结点的第一条边的边结点。
? 为了快速查找顶点结点，可设一个一维数组，存放各顶点结点。
也可在顶点结点中增设链域，将各顶点结点链接在一起。
结点编号 首边指针结点信息
52
1
2
4
3
1
2
3
4
3 1 ^ ^2 1 ^
4 2 ^3 2 ^
4 3
图 - 无向图邻接多重表示例
对无向图，每条边的起点与终点没有指定，所以邻接多重表
在形式上是不唯一的
53
§ 6.4 图的遍历
? 图的遍历的含意是，从图中某结点出发，按某既定方
式访问图中各个可访问到的结点，使每个可访问到的
结点恰被访问一次。
? 图的遍历方式有两种：
– 深度优先
– 广度优先
? 在遍历中，应为每个结点设立一个访问标志
§ 6.4,1 概述
54
? 访问标志的设置有两种方法：
– ①在描述图结的记录中增设一个访问标志位。
– ②另设一个, 访问数组,,令它的每个元素对应于一个图结点访
问标志。这种方法的访问标志很容易多次初始化。
? 从图中某一结点出发，一趟只能遍历到它所在的极大连通分量中
的结点，要想遍历到图中各结点，需进行多趟遍历（每趟遍历一
个极大连通分量）。
? 该过程可描述为：
for (图中每个结点发 v)
if (v尚未被访问过 )
从 v出发遍历该图 ;
§ 6.4,1 概述
55
§ 6.4,2 深度优先遍历
(一 )遍历规则
– 从图中某结点 v0出发,深度优先遍历 （ Depth First Search）图
的规则为：
– 访问 v0；
– 对 v0的各个出点 v01,v02,…, v0m，每次从它们中按一定方式
（也可任选）选取一个未被访问过的结点，从该结点出发按
深度优先遍历方式遍历。
? 显然，因为我们没有规定对出点的遍历次序，所以，
图的深度优先遍历结果一般不唯一。
56
§ 6.4,2 深度优先遍历
?一些遍历结果 （ 结点访问次序 ） 为：
?左图：从 1出发,1,2,4,5；或 1,5,2,4
? 从 2出发,2,1,5,4；或 2,4,1,5
? 右图：从 a出发,a,b,c,d；或 a,b,d,c; … …
1
2 5
4 3
a
b
c
d
图 - 一个有向图（左）和无向图
57
§ 6.4,2 深度优先遍历
(一 )遍历规则
?从图中某结点 v0出发, 深度优先遍历 （ Depth
First Search） 图的规则为：
– 访问 v0；
– 对 v0的各个出点 v01,v02,…, v0m，每次从它们中按
一定方式（也可任选）选取一个未被访问过的结点，
从该结点出发按深度优先遍历方式遍历。
58
1
2 5
4 3
a
b
c
d
图 - 一个有向图（左）和无向图
例如, 对 图 6-0给出的有向图与无向图, 一些遍历结果 （ 结点
访问次序 ） 为：
左图：从 1出发,1,2,4,5；或 1,5,2,4
从 2出发,2,1,5,4；或 2,4,1,5
右图：从 a出发,a,b,c,d；或 a,b,d,c; … …
59
§ 6.4,2 深度优先遍历
(二 )实现方法
?图的深度优先遍历与二叉树的前序遍历相似 。
不同之处有：
① 二叉树每个结点至多有两个可达邻接点 （ 左右儿
子 ）, 而图的可达邻接点数且不定；
② 对二叉树, 沿可达邻接点搜索时不会发生回绕, 但
对图, 若不加特别控制, 就有可能回绕 。
60
?图的深度优先遍历递归算法
longDFS(图 g,结点 v0)
{ //从结点 v0出发, 深度优先遍历图 g,返回访问到的结点总数
int nNodes; //寄存访问到的结点数且
nNodes=1;
访问 v0;
为 v0置已访问标志 ;
求出 v0的第 1个可达邻接点 v;
while (v存在 )
{
if (v未被访问过 ) nNodes=nNodes+DFS(g,v);
求出 v0的下个可达邻接点 v;
}
return nNodes;
}
61
long DFS1(TGrphEdge **g,long n,long v0)
{
long nNodes,i;
nNodex=1;
VisitGrphNode(g,v0); //设该函数用于访问图 g的结点 v0
GgphNodeSetVisited(g,v0,1);
//设该函数用于设置图 g中的结点 v0的访问标志 （ 第三个参数 0/1—未 /已访问 ）
for (i=0; i<n; i++)
{
if (g[v0][i]!=无边标志 )
if (!GrphGetVisited(g,i))
//设 GrphGetVisited(g,i)返回 g中结点 i的访问标志 (0—未访问 )
nNodes = nNodes+DFS1(g,i);
} //for
return nNodes;
}
针对邻接矩阵
的 深度优先遍
历递归算法
62
long DFS2(TGrphNode *g,long v0)
{
long nNodes,i;
TGrphEdge *p;
nNodex=1;
VisitGrphNode(g,v0); //设该函数用于访问图 g的结点 v0
GgphNodeSetVisited(g,v0,1);
//设该函数用于设置图 g中的结点 v0的访问标志 （ 第三个参数 0/1—未 /已访问 ）
p = g[v0].firstOutEdge;
while (p!=NULL)
{
if (!GrphGetVisited(g,p->edgeEndIdx))
//设 GrphGetVisited(g,k)返回 g中结点 k的访问标志 (0—未访问 )
nNodes = nNodes+FDS2(g,p->edgeEndIdx);
p = p->next;
}
return nNodes;
}
针对邻接表 的
深度优先遍历
递归算法
63
§ 6.4,3 广度优先遍历
(一 )图的分层
?图的分层就是要识别出图中每个结点属于的层次, 即给
每个结点编一个层次号
?分层时, 应先确定一个或几个参考点
?以结点 v0为参考点的图的分层的定义 （ 非过程化 ）, 这
里用 Level(v)表示结点 v的层号：
– 令 Level(v0) = 1
– 对任意的 v≠v0,若存在 v0到 v的通路, 则令
Level(v)=1+MIN{ Level(u) | <u,v>是图的边 }
– 否则令 Level(v)=∞
64
1
2 5
4 3
a
b
c
d
图 - 一个有向图（左）和无向图
左图：从 1出发分层：层号
为 1的结点,1
层号为 2的结点,2,5
层号为 3的结点,4
层号为 ∞的结点,3
左图：从 2出发分层：层号
为 1的结点,2
层号为 2的结点,1,4
层号为 3的结点,5
层号为 ∞ 的结点,3
右图：
从 a出发分层：层号为 1
的结点,a
层号为 2的结点,b,d
层号为 3的结点,c
65
§ 6.4,3 广度优先遍历
(二 )图的广度优先遍历方法
? 从结点 v0 出发, 广 度 优 先 遍 历
（ Breadth/Width First Search） 图的方法是
按从 v0出发对图的分层的层次号的大小次序访问结
点, 即先访问第一层上结点, 然后访问第二层上结
点, … 等等, 同层上次序可按邻接点次序或任意 。
66
1
2 5
4 3
a
b
c
d
图 - 一个有向图（左）和无向图
左图：从 1出发广度优先遍历结果,1,2,5,4
左图：从 2出发广度优先遍历,2,1,4,5
右图：从 a出发广度优先遍历,a,b,d,c
67
§ 6.4,3 广度优先遍历
(三 )算法实现
? 广度优先遍历是一种分层处理, 对这种分层处理,
使用队列是自然的 。 我们设立一个队列, 任何时刻, 均
保证它满足下列条件：
– 队中元素是已访问过的结点的可达邻接点；
– 队中元素是尚未被访问过的；
– 队中元素按它们所处的层次的先后排列 。
? 这样, 我们就可不断地每次从队中取出一个元素并
访问之, 然后再将该元素的尚未被访问过的邻接点进队,
直至队空 。
68
§ 6.4,3 广度优先遍历
(三 )算法实现
longBFS(图 g,结点 v0）
{ //在图 g中从 v0出发按广度优先遍历方式遍历 g,返回遍历到的结点
数目
longnNodes=0;
初始化队 Q;
if （ v0存在 ）
{ v0入 Q;
置 v为已访问标志 ;
}
未涉及到具体
的存贮结构 的
广度优先遍历
算法
69
while (Q不空 )
{
队 Q头元素出队并送 v;
访问 v;
nNodes++; //对已访问元素计数
求出 v的第一个可达邻接点 w;
while (w存在 )
{
if (w尚未被访问过 )
{
w入 Q;
置 w为已访问标志 ;
}
求 v的下个可达邻接点 w;
}
return nNodes;
}
70
long BFS1(TGrphEdge **g,long n,long v0)
{
long nNodes=0;
long v,w;
char *visited;
TQueue<long> Q(n);
visited = new char[n];
for (i=0; i<n; i++) visited[i] = 0; //初始化访问标志数组
针对邻接矩阵
的
广度优先遍历
算法
71
if (v0>0 && v0<n) Q.QPush(v0);
while (!Q.Empty())
{
v = Q.QPop();
VisitGrphNode (g,v); //访问结点 v
nNodes++;
for (w=0; w<n; w++)
if (g[v][w]!=无边标志 )
if (!visited[w]) Q.QPush(w);
} //while
} //while
delete [] visited;
return nNodes;
}
72
long BFS2(TGrphNode *g,long n,long v0)
{
long nNodes=0;
TGrphEdge *p;
char *visited;
TQueue<long> Q(n);
visited = new char[n];
for (i=0; i<n; i++) visited[i] = 0; //初始化访问标志数组
针对邻接表 的
广度优先遍历
算法
73
if (v0>0 && v0<n) Q.QPush(v0);
while (!Q.Empty())
{
v = Q.QPop();
VisitGrphNode (g,v); //访问结点 v
visited[v]=1;
nNodes++;
p = g[v],firstOutEdge;
while (p!=NULL)
{
if (!visited[p->edgeEndIdx]) Q.QPush(p->edgeEndIdx);
p = p->next
}//while
}//while
delete [] visited;
return nNodes;
}
74
§ 6.5 最小生成树
? 无向图的无回路的连通的生成图称为该无向图的生成
树。这种树是无向树（上章主要介绍的为有向树）
? 给图的各边分别赋予一个权, 称边权之和最小的生成
树称为 最小生成树
? 是图的一种最优化问题的抽象
? 在诸如网络构造（如何构造连同 n个站点的网络，有通
迅线路网、交通运输网 … ）之类的应用中占重要地位。
? 两个著名的算法 ── Kruskal算法与 Prim算法
75
§ 6.5.1 Prim算法
(一）基本思想
?贪心法, 它的基本原则是使每步满足：
(a)当前生成的图是连通的
(b)当前生成的图不含回路
(c)当前生成的图是最小生成树的一部分
76
§ 6.5.1 Prim算法
(二） Prim算法
?设 N=(V,E)是无向图, 求它的最小生成树 T=(V',E')的
Prim算法为：
[1] 从 V中任取一结点放入 V'；
[2] 在所有的端点分别在 (V-V')和 V'中的边中, 选一条权
最小的加入 E'；
[3] 将边 E'在 (V-V')中的顶点放入 V'；
[4] 重复步骤 [2]~[3],直到 V'中包含了所有结点为止 。
77
2
C
4
5
1 6A
B
D
E
8
9 2
C
4
5
1 A
B
D
E
(a) 无向图 (b) 无向图 (a)的一棵最小生成树
步骤 V-V' V' 连接 (V-V')与 V’的边 T'
0 BCDE A AB,AE 空
1 CDE AB AE,BE,BD,BC AB
2 DE ABC AE,BE,BD,CD AB,BC
3 E ABCD AE,BE,DE AB,BC,BD
4 空 ABCDE 空 AB,BC,BD,BE
(c) 无向图 (a)的最小生成树生成过程
图 - Prime最小生成树算法示例 (结点 a为初始选择结点 )
78
§ 6.5.1 Prim算法
(三） Prim算法的正确性讨论
? 说明 Prim算法满足本节中提出的三项原则
(a) 因为每次都是从连接 (V-V')与 V'中的边中选一条
边, 故每次构成的部分树是连通的 。
(b) 每次构成的部分树也是肯定无回路的
(c) Prim算法每步生成的图, 均属最小生成树
79
§ 6.5.2 Prim算法的实现
(一）基本思想
? Prim最小生成树的生成过程, 是个逐步扩大 V'的过程：
每次从连接 V'与 (V-V')的边中选择一条最小者, 将其
在 (V-V')中的结点加入到 V'中 。
? 因此, 在算法实现中, 必须记下当前的 V'与 (V-V')之
间的边的信息, 以备选择, 我们称这种信息为候选集 。
80
§ 6.5.2 Prim算法的实现
(一）基本思想
? 称
– V'中结点 ──红点, 即部分生成树的结点；
– (V-V')中的结点 ──白点, 即尚未被加入到部分生成树中的结
点；
– V'中结点构成的边 （ E'中的边 ） ──红边, 即部分生成树的边；
– (V-V')中结点构成的边 （ E的边 ） ──白边, 即原图中的边
– 连接 V'与 (V-V')的边 ── 蓝边, 即当前候选边 （ 候选集 ） 。
81
§ 6.5.2 Prim算法的实现
(一）基本思想
? 生成最小树的过程, 就是不断地从当前蓝边中选出最小者, 涂成
红色 （ 将它的白结点也涂成红色 ）, 然后收集新出现的蓝边 。
? 该过程描述如下：
从 V中任选一结点加到 V'中；
设置初始候选集 （ 蓝边集 ） ；
while（ V'中尚未包含全部结点 ）
{
从当前蓝边集中选一条最小者；
将所选最小边加入到 E'中；
将所选最小边的白结点加入到 V'；
调整候选集 （ 蓝边集合 ） ；
}
82
§ 6.5.2 Prim算法的实现
(一）基本思想
? 将从蓝边中选出的边涂成红色后, 它的白结点也要涂
成红色, 故与该白点关联的那些白边也要变为蓝边,
这就是说, 蓝边集合要改变 （ 减与增 ）, 这种改变过
程, 我们称为调整候选集 。
83
24
8
160 4020
80 30
70
6
95
7
3 15
25
95
45 35
75
图 - 最小生成树候选集调整
V-V' V'
只需记录蓝边集中最小者
84
§ 6.5.2 Prim算法的实现
(二）数据结构设计
1,图
这里, 用邻接矩阵表示图 （ 作为输入数据 ） 。 设 g为邻接矩阵, 它的元
素定义为
∞,若 i与 j之间无边
g[i][j] =
权值,若 i与 j之间有边
85
§ 6.5.2 Prim算法的实现
(二）数据结构设计
2,最小生成树
最小生成树为生成的结果 （ 输出数据 ）, 用边集表示 。 边
集用一个一维数组表示 。 令树的每条边对应于一个数
组元素, 数据元素为如下形式的三元组：
（ 边始点, 边终点, 边权 ）
86
§ 6.5.2 Prim算法的实现
(二）数据结构设计
3,候选集 Close
即蓝边集合, 用一维数组表示 。 数组的每个元素代表一条蓝
边, 它的白点编号为它在树组中的下标, 而它的红点编
号及权值则记录在数组元素中, 若与白点关联的蓝边不
止一条, 则 Close中记录其中权值最小的那条 。
Close数组元素的结构为：
(vex,lowCost)
87
§ 6.5.2 Prim算法的实现
(二）数据结构设计
其中的 vex与 lowCost分别表示蓝边的红端点编号与兰边的权值 。
Close的具体定义为：
· 对每个 v∈ V-V'（ 白点 ）
Close[v].lowCost = MIN{(v,u)上的权值 | u∈ V' }
Close[v].vex = u //u为满足上式的红点, 若 Close[v].lowCostwe=∞，
则 u无关
· 对每个 u∈ V'（ 红点 ）
close[u].lowCost=0
close[u].vex=无关
88
表 6-1 Close示例（ *--无关）
（ a）图 6-1对应的候选集
结点 v 1 2 3 4 5 6 7 8 9
Close[v].vex * * * * * 4 1 * 8
Close[v].lowCost 0 0 ∞ 0 ∞ 20 40 0 30
（ b）在选择一条蓝边，调整候选集后
Close[v].vex * * 6 * 6 * 6 * 8
Close[v].lowCost 0 0 15 0 45 0 35 0 30
24
8
160 4020
80 30
70
6
95
7
3 15
25
95
45 35
75
图 - 最小生成树候选集调整
V-V' V'
89
§ 6.5.2 Prim算法的实现
(三）算法实现
? 该算法的时间复杂度为 O(n2)（ n为结点数）
struct TTreeEdge //最小生成树的边类型
{
long v1,v2; //边起点与终点编号
float weight; //边权
};
90
longMinSpanningTree(TGrphEdge *g,long n,TTreeEdge *minTree)
{//求具有 n个结点的图 g的最小生成树, 结果存于边数组 minTree
//返回最小生成树的边数 。 返回值不等于 n-1时, 表示出错
struct TCloseRec //候选集类型
{
longvex;
float lowCost;
} ;
91
longi,j,k;
float minW;
TCloseRec *close;
i=0;
close = new TClose[n];
for (i=1; i<n; i++)
{
close[i].vex = 0; close[i].lowCost = g[i][0];
} //初始化候选集, 将结点 0作为始点加入 V'
92
close[0].lowCost = 0; //为结点 0做红点标志
for (i=0; i<n-1; i++) //不断挑选蓝边并调整候选集, 每次为 minTree生成一个元素
{
for (k=1; k<n; k++) //找第一个白点
if (close[k].lowCost!=0) break;
for (j=k+1; j<n; j++) //找最小蓝边
if (close[j].lowCost!=0)
if (close[j].lowCost < clost[k].lowCost )
k=j;
//下面将所找出的最小蓝边 （ k,close[k].vex） 涂红
minTree[i].v1 = k;
minTree[i].v2 = close[k].vex;
minTree[i].weight = close[k].lowCost;
close[k].lowCost=0;
93
//下面调整候选集
for (j=1; j<n; j++) //检查每个邻接于 k的 (白 )边
if (close[j].lowCost > g[j][k] )
{
close[j].lowCost = g[j][k];
close[j].vex = k;
}
} //for（ i=0; …
delete [] close;
return i;
};
94
§ 6.5,3 Kruskal算法
(一）基本方法
? Prim算法不是按边权不减的次序生成最小生成树的
? Kruskal算法是一种与 Prim算法不同的算法，它按边不减
的次序生成最小生成树
? Kruskal算法并不保证每步生成的结果是连通的（从而部
分结果可能不是树）
95
§ 6.5,3 Kruskal算法
(一）基本方法
? 设 G=(V,E)是一个有向图, T是它的最小生成树的边集, 则由 G生成 T
的 Kruskal算法描述如下 （ n为 G中结点个数 ）,
置 T为空集；
while (T中边数 <n)
{
从 E中挑选一条最小边 (v,u);
从 E中删去 (v,u);
if ( (v,u)在 T中不产生回路 ) )
将 (v,u)加入 T中 ;
else舍弃 (v,u);
}
96
图 - Kruskal最小生成树算法示例
52
C
7
3
1 4A
B
D
E
82
2
1 A
B选出 AB 选出 ED 选出 BE
1 A
B
D
E
2
1 A
B
D
E
2
3 选出 AE,
作废
1 A
B
D
E
2
3
选出 BC
1 A
B
D
E
2
3
52
C
97
§ 6.5,3 Kruskal算法
(一）实现方法
? Kruskal算法的实现涉及到生成森林, 是按边权递增的次
序连通森林的过程
? 该过程具体描述如下：
long MinSoanningKruskal(G,T)
{//G─无向图, T─最小生成树边集
// TS─生成森林
long cnt=0;
98
置 T为空 ;
将图 G的每个结点分别作为一棵树放入 TS中 ;
while (TS中树的个数大于 1)
{
从 G的边集选一条尚未被选择的代价最小的边 (u,v);
对 (u,v)做已选择标志；
if (u与 v分别属于 TS中两棵不同的树 Tu与 Tv)
{
cnt++;
合并 Tu与 Tv;
将 (u,v)加入到 T中 ;
}
}//while
return cnt;
}
