第7章 图
图的定义与基本术语
图的存储结构
图的遍历
图的连通性问题
有向无环图的应用
最短路径 返回主目录
../../ppt/%E6%95%99%E6%A1%
图结构与表结构和树结构的不同表现在结点之
间的关系上，线性表中结点之间的关系是一对一的；
树是按分层关系组织的结构，树结构之间是一对多；
对于图结构，图中顶点之间的关系可以是多对多，
即一顶点和其它顶点间的关系是任意的，可以有关
也可以无关。因此，图 G 树T L，图是一种比较
复杂的非线性数据结构。
图作为一种非线性结构，被广泛应用于多个技术
领域。在本章中，主要是应用图论的理论知识来讨论
如何在计算机上表示和处理图，以及如何利用图来解
决一些实际问题。
返回主目录
../../ppt/%E6%95%99%E6%A1%
图的定义与基本术语
图的定义
图（Graph）是一种网状数据结构，其形式化定
义如下：
Graph=（V，R）
V={x∣x∈DataObject}
R={VR}
VR={<x，y>∣P（x，y）∧（x，y∈V）}
返回主目录
../../ppt/%E6%95%99%E6%A1%
DataObject为一个集合，该集合中的所有元素
具有相同的特性。V中的数据元素通常称为顶点
（vertex），VR是两个顶点之间的关系的集合。 P
（x，y）表示x和y之间有特定的关联属性P。
弧：若<x，y>∈VR，则<x，y>表示从顶点x到顶点
y的一条弧（arc），并称x为弧尾（tail）或起始点，
称y为弧头（head）或终端点。
有向图：若图中的边是有方向的，称这样的图为有
向图。
返回主目录
../../ppt/%E6%95%99%E6%A1%
无向图：若<x，y>∈VR，必有<y，x>∈VR，即
VR是对称关系，这时以无序对（x，y）来代替两
个有序对，表示x和y之间的一条边（edge），此时
的图称为无向图。
例如：下图G1是有向图，G2是无向图
21
3 4
G1
21
4 5
G2
3
返回主目录
../../ppt/%E6%95%99%E6%A1%
在图中，我们可以将任一顶点看成是图的第一
个顶点，同理，对于任一顶点而言，它的邻接点之
间也不存在顺序关系。为了操作的方便，我们需要
将图中的顶点按任意序列排列起来。顶点在这个人
为的随意排列中的位置序号称为顶点在图中的位置。
图的基本操作和其它数据结构一样，也有创
建、插入、删除、查找等。
返回主目录
../../ppt/%E6%95%99%E6%A1%
图的抽象类型定义：
ADT Graph
数据对象V：一个集合，该集合中的所有元素具有相
同的特性。
数据关系R：R={VR}
VR={<x，y>∣P（x，y）∧（x，y∈V）}
返回主目录
../../ppt/%E6%95%99%E6%A1%
基本操作：
（1）GreateGraph(G)：创建图G。
（2）DestoryGraph(G)：销毁图G。
（3）LocateVertex(G,v)：确定顶点v在图G中的位置。
若图G中没有顶点v，则函数值为“空”。
（4）GetVertex(G,I)：取出图G中的第i个顶点的值。
若i>图G中顶点数，则函数值为“空”。
返回主目录
../../ppt/%E6%95%99%E6%A1%
（5）FirstAdjVertex(G,v)：求图G中顶点v的第一
个邻接点。若v无邻接点或图G中无顶点v，则函数值
为“空”。
（6）NextAdjVertex(G,v,w)：已知w是图G中顶点v
的某个邻接点，求顶点v的下一个邻接点（紧跟在w
后面）。若w是v的最后一个邻接点，则函数值为“
空”。
（7）InsertVertex(G,u)：在图G中增加一个顶点u。
返回主目录
../../ppt/%E6%95%99%E6%A1%
（8）DeleteVertex（G，v）：删除图G的顶点v及与
顶点v相关联的弧。
（9）InsertArc（G，v，w）：在图G中增加一条从顶
点v到顶点w的弧。
（10）DeleteArc（G，v，w）：删除图G中从顶点v到
顶点w的弧。
（11）TraverseGraph（G）：按照某种次序，对图
G的每个结点访问一次且最多一次。
返回主目录
../../ppt/%E6%95%99%E6%A1%
基本术语
设用n表示图中顶点的个数，用 e表示图中边或
弧的数目，并且不考虑图中每个顶点到其自身的边
或弧。
无向完全图：有n（n-1）/2条边（图中每个顶点和
其余n-1个顶点都有边相连）的无向图为无向完全图。
有向完全图：有n（n-1）条边（图中每个顶点和其
余n-1个顶点都有弧相连）的有向图为有向完全图。
返回主目录
../../ppt/%E6%95%99%E6%A1%
稀疏图：对于有很少条边的图（e < n log n）称为
稀疏图，反之称为稠密图。
子图：设有两个图G=（V，{E}）和图G/=（V/，
{E/}）,若V/V且E/ E，则称图G/为G的子图。
图G1和图G2的子图见p155的图所示。
返回主目录
../../ppt/%E6%95%99%E6%A1%
对于无向图 G=（V，{E}），如果边（v，v/
）∈E，则称顶点v，v/互为邻接点，即v，v/ 相邻接。
边（v，v/）依附于顶点v和v/，或者说边（v，v/）与
顶点v和v/ 相关联。
对于有向图G=（V，{A}）而言，若弧<v，
v/>∈A，则称顶点v邻接到顶点v/，顶点v/ 邻接自顶
点v，或者说弧<v，v/>与顶点v，v/相关联。
邻接点：
返回主目录
../../ppt/%E6%95%99%E6%A1%
度、入度和出度
对于无向图而言，顶点v 的度是指和v相关联的边的
数目，记作TD（v）。
对于有向图而言，顶点v的度有出度和入度两部分：
以顶点v为弧头的弧的数目称为该顶点的入度，记
作ID（v），以顶点v为弧尾的弧的数目称为该顶点
的出度，记作OD（v）则顶点v的度为：
TD（v）= ID（v）+ OD（v）。
返回主目录
../../ppt/%E6%95%99%E6%A1%
一般地，若图G中有n个顶点，e条边或弧，则图
中顶点的度与边的关系如下：
e=
TD(Vi)
2
n
i=1
返回主目录
../../ppt/%E6%95%99%E6%A1%
权与网 :
在实际应用中，有时图的边或弧上往往与具有
一定意义的数有关，即每一条边都有与它相关的数，
称为权，这些权可以表示从一个顶点到另一个顶点
的距离或耗费等信息。我们将这种带权的图叫做赋
权图或网。
图例见p156的图所示。
返回主目录
../../ppt/%E6%95%99%E6%A1%
路径与回路
无向图G=（V，{E}）中从顶点v到v/的路径是一个顶
点序列v
i 0
，v
i1
，v
i2
，…，v
in
，其中（v
ij-1
，v
ij
）
∈E，1≤j≤n。
如果图G是有向图，则路径也是有向的，顶点序列应
满足<v
ij-1
，v
ij
>∈A，1≤j≤n。
路径长度：指路径上经过的弧或边的数目。
返回主目录
../../ppt/%E6%95%99%E6%A1%
回路或环：在一个路径中，若其第一个顶点和最后
一个顶点是相同的，即v =v/，则称该路径为一个回
路或环。
简单路径：若表示路径的顶点序列中的顶点各不相
同，则称这样的路径为简单路径。
简单回路：除了第一个和最后一个顶点外，其余各
顶点均不重复出现的回路为简单回路。
返回主目录
../../ppt/%E6%95%99%E6%A1%
连通图
连通图：在无向图G=（V，{E}）中，若从v
i
到v
j
有路
径相通，则称顶点v
i
与v
j
是连通的。如果对于图中的
任意两个顶点v
i
、v
j
∈V，v
i
，v
j
都是连通的，则称该
无向图G为连通图。
连通分量：无向图中的极大连通子图称为该无向图的
连通分量。
返回主目录
../../ppt/%E6%95%99%E6%A1%
强连通图：在有向图G=（V，{A}）中，若对于每对
顶点v
i
、v
j
∈V且v
i
≠v
j
，从vi到v
j
和v
j
到v
i
都有路径，
则称该有向图为强连通图。
强连通分量：有向图的极大强连通子图称作有向图
的强连通分量。
图G1和图G3的连通分量见p157的图所示
返回主目录
../../ppt/%E6%95%99%E6%A1%
生成树
一个连通图的生成树是指一个极小连通子图，它含
有图中的全部顶点，但只有足已构成一棵树的n-1
条边。
如图p157的图所示。
返回主目录
../../ppt/%E6%95%99%E6%A1%
图的存储结构
图的存储结构方法有：
①邻接矩阵表示法；
②邻接表；
③邻接多重表；
④十字链表
返回主目录
../../ppt/%E6%95%99%E6%A1%
邻接矩阵表示法
图的邻接矩阵表示法（Adjacency Matrix）也称作
数组表示法。
它采用两个数组来表示图：一个是用于存储顶点信
息的一维数组，另一个是用于存储图中顶点之间关
联关系的二维数组，这个关联关系数组被称为邻接
矩阵。
返回主目录
../../ppt/%E6%95%99%E6%A1%
若G是一具有n个顶点的无权图，G的邻接矩阵是具
有如下性质的n×n矩阵A：
A[i,j]=
1 若<vi,vj>或
（vi,vj)VR
0 反之
G1和G2的邻接矩阵见p158的图所示
返回主目录
../../ppt/%E6%95%99%E6%A1%
若图G是一个有n个顶点的网，则它的邻接矩阵是具
有如下性质的n×n矩阵A ：
A[i,j]=
Wij 若<vi,vj>或（vi,vj)VR
∞ 反之
有向网及其邻接矩阵见p158的图所示。
返回主目录
../../ppt/%E6%95%99%E6%A1%
邻接矩阵表示法的C语言类型描述为：
#define MAX_VERTEX_NUM 10 /*最多顶点个数*/
#define INFINITY 32768 /*最多顶点个数*/
typedef enum{DG, DN, UDG, UDN} GraphKind;
/*图的种类：DG表示有向图, DN表示有向网, UDG表示无向图, UDN表示无向网*/
typedef char VertexData; /*假设顶点数据为字符型*/
typedef struct ArcNode{
AdjType adj;
/*对于无权图，用1或0表示是否相邻；对带权图，则为权值类型*/
OtherInfo info;
} ArcNode;
返回主目录
../../ppt/%E6%95%99%E6%A1%
typedef struct{
VertexData vexs[MAX_VERTEX_NUM]; /*顶点向量*/
ArcNode arcs [MAX_VERTEX_NUM][MAX_VERTEX_NUM]; /*邻接矩阵*/
int vexnum, arcnum; /*图的顶点数和弧数*/
GraphKind kind; /*图的种类标志*/
} AdjMatrix; /*（Adjacency Matrix Graph）*/
返回主目录
../../ppt/%E6%95%99%E6%A1%
邻接矩阵法的特点：
1. 存储空间：对于无向图而言，它的邻接矩阵是对
称矩阵，所以可采用压缩存储法（下三角），其存
储空间只需n(n-1)/2。但对于有向图而言，因为它的
弧是有方向的，它的邻接矩阵不一定是对称矩阵，
所以需要n2个存储空间。
2. 便于运算：采用邻接矩阵表示法，便于判定图
中任意两个顶点之间是否有边相连，即根据A[i，
j]=0或1来判断。另外还便于求得各个顶点的度。
返回主目录
../../ppt/%E6%95%99%E6%A1%
对于无向图而言，其邻接矩阵第 i 行元素之和就
是图中第 i 个顶点的度：
TD(vi)= A[i,j]
j=1
n
对于有向图而言，其邻接矩阵第i行元素之和就是
图中第i个顶点的出度，第i列元素之和就是图中第i
个顶点的入度。
OD(vi)= A[i,j]
j=1
n
ID(vi)= A[j,i]
j=1
n
顶点i的出度：
顶点i的入度： 返回主目录
../../ppt/%E6%95%99%E6%A1%
采用邻接矩阵存储法表示图，很便于实现图的一些
基本操作，如 FirstAdjVertex（G，v）：
（1）首先，由LocateVertex（G，v）找到v在图中
的位置，即v在一维数组vexs中的序号i。
（2）二维数组arcs中第i行上第一个adj域非零的分
量所在的列号j，便是v的第一个邻接点在图G中的位
置。
（3）取出一维数组vexs[j]中的数据信息，即与顶
点v邻接的第一个邻接点的信息。
注意：稀疏图不适于用邻接矩阵来存储，因为这样
会造成存储空间的浪费。 返回主目录
../../ppt/%E6%95%99%E6%A1%
用邻接矩阵法创建有向网的算法如下：
int LocateVertex(AdjMatrix * G, VertexData v)/*求顶点位置函数*/
{ int j=Error,k;
for(k=0;k<G->vexnum;k++)
if(G->vexs[k]==v)
{ j=k; break; }
return(j);
}
返回主目录
../../ppt/%E6%95%99%E6%A1%
int CreateDN(AdjMatrix *G) /*创建一个有向网*/
{ int i,j,k,weight; VertexData v1,v2;
scanf("%d,%d",&G->arcnum,&G->vexnum);
/*输入图的顶点数和弧数*/
for(i=0;i<G->vexnum;i++)
for(j=0;j<G->vexnum;j++)
G->arcs[i][j].adj=INFINITY;
for(i=0;i<G->vexnum;i++)
scanf("%c",&G->vexs[i]); /* 输入图的顶点*/
for(k=0;k<G->arcnum;k++)
返回主目录
../../ppt/%E6%95%99%E6%A1%
{ scanf("%c,%c,%d",&v1,&v2,&weight);
/*输入一条弧的两个顶点及权值*/
i=LocateVex_M(G,v1);
j=LocateVex_M(G,v2);
G->arcs[i][j].adj=weight; /*建立弧*/
}
return(Ok);
}
分析：该算法的时间复杂度为O（n2+e×n），其中 O
（n2）时间耗费在对二维数组arcs的每个分量的arj
域初始化赋值上。O（e×n）的时间耗费在有向网中
边权的赋值上。
返回主目录
../../ppt/%E6%95%99%E6%A1%
邻接表表示法
邻接表（Adjacency List）表示法实际上是图的一种
链式存储结构。 它的基本思想是只存有关联的信息，
对于图中存在的边信息则存储，而对于不相邻接的
顶点则不保留信息。在邻接表中，对图中的每个顶
点建立一个带头结点的边链表，每个边链表的头结
点又构成一个表头结点表。
这样，一个n个顶点的图的邻接表表示由表头结点表
与边表两部分构成。
返回主目录
../../ppt/%E6%95%99%E6%A1%
（1）表头结点表：由所有表头结点以顺序结构（向
量）的形式存储，以便可以随机访问任一顶点的单链
表。 表头结点有两部分构成，其中数据域
（vexdata）用于存储顶点的名或其它有关信息；链
域（firstarc）用于指向链表中第一个顶点（即与顶
点vi邻接的第一个邻接点）。
表头结点结构为：
vexdata firstarc
返回主目录
../../ppt/%E6%95%99%E6%A1%
（2）边表：由表示图中顶点间邻接关系的n个边链
表组成。它由三部分组成，其中邻接点域
（adjvex）用于存放与顶点vi相邻接的顶点在图中
的位置；链域（nextarc）用于指向与顶点vi相关联
的下一条边或弧的结点；数据域（info）用于存放
与边或弧相关的信息（如赋权图中每条边或弧的权
值等）。
adjvex info nextarc
弧结点结构为：
返回主目录
../../ppt/%E6%95%99%E6%A1%
图例
p161的图所示是图G1、G2的邻接表表示法
返回主目录
../../ppt/%E6%95%99%E6%A1%
邻接表存储结构的形式化说明如下：
#define MAX_VERTEX_NUM 10 /*最多顶点个数*/
typedef enum{DG, DN, UDG, UDN} GraphKind; /*图的种类*/
typedef struct ArcNode{
int adjvex; /*该弧指向顶点的位置*/
struct ArcNode *nextarc; /*指向下一条弧的指针*/
OtherInfo info; /*与该弧相关的信息*/
} ArcNode;
返回主目录
../../ppt/%E6%95%99%E6%A1%
typedef struct VertexNode{
VertexData data; /*顶点数据*/
ArcNode *firstarc; /*指向该顶点第一条弧的指针*/
} VertexNode;
typedef struct{
VertexNode vertex[MAX_VERTEX_NUM];
int vexnum,arcnum; /*图的顶点数和弧数*/
GraphKind kind; /*图的种类标志*/
}AdjList; /*基于邻接表的图(Adjacency List Graph)*/
返回主目录
../../ppt/%E6%95%99%E6%A1%
●存储空间：对于有n个顶点，e条边的无向图而言，
若采取邻接表作为存储结构，则需要n个表头结点和
2e个表结点。
●无向图的度：在无向图的邻接表中，顶点vi的度恰
好就是第i个边链表上结点的个数。
●有向图的度：在有向图中，第i个边链表上顶点的
个数是顶点vi的出度。要想求得该顶点的入度，则
必须遍历整个邻接表。在所有单链表中查找邻接点
域的值为i的结点并计数求和。
返回主目录
../../ppt/%E6%95%99%E6%A1%
由此可见，对于用邻接表方式存储的有向图，求顶
点的入度并不方便，因此需要有一种解决的方法－
逆邻接表法。
对图中的每一顶点vi建立一个递邻接表，即对每个顶
点vi建立一个所有以顶点vi为弧头的弧的表，这样求
顶点vi的入度即是计算逆邻接表中第i个顶点的边链表
中结点个数。
图G1的逆邻接表表示法见p162的图
返回主目录
../../ppt/%E6%95%99%E6%A1%
十字链表
十字链表(Orthogonal List)是有向图的另一种链
式存储结构。我们也可以把它看成是将有向图的邻
接表和逆邻接表结合起来形成的一种链表。
有向图中的每一条弧对应十字链表中的一个弧
结点，同时有向图中的每个顶点在十字链表中对应
有一个结点，叫做顶点结点。
这两类结点的结构见p162的图所示。
返回主目录
../../ppt/%E6%95%99%E6%A1%
图G1的十字链表表示见p163的图所示。
1 2 ∧ 1 3 ∧ ∧
4 1 ∧ ∧
1
3
2
∧
4
3 4 ∧∧
1
2
3
4
返回主目录
../../ppt/%E6%95%99%E6%A1%
建立一个有向图的十字链表的算法如下：
void CrtOrthList（OrthList g）
/*从终端输入n个顶点的信息和e条弧的信息，以建立一个有向图的十字链
表*/
{
scanf(“%d,%d”,&n,&e);/*键盘输入图的顶点个数和弧的个数*/
for (i=0;i<n;i++)
{scanf(“%c”,[i].data）；
[i] .firstin=NULL；[i] .firsout=NULL；
}
返回主目录
../../ppt/%E6%95%99%E6%A1%
for (k=0;k<e;k++)
{scanf(“%c,%c”,&vt,&vh);
i=LocateVertex（g，vt）；j = LocateVertex（g，vh）；
p=alloc(sizeof(ArcNode));
p->tailvex=i；p->headvex=j；
p->tlink = [i].firstout；[i].firstout =p；
p->hlink = [j].firstin；[j].firstin =p；
}
}/* CrtOrthList */
返回主目录
../../ppt/%E6%95%99%E6%A1%
十字链表的优点：
在十字链表中既能够很容易地找到以vi为尾的
弧，也能够容易地找到以vi为头的弧，因此对于有
向图，若采用十字链表作为存储结构，则很容易求
出顶点vi的度。
返回主目录
../../ppt/%E6%95%99%E6%A1%
邻接多重表
邻接多重表(Adjacency Multi_list)是无向图的
另外一种存储结构。使用邻接多重表这种存储结构
是因为它能够提供更为方便的边处理信息。
邻接多重表是指将图中关于一条边的信息用一
个结点来表示。
邻接多重表中的边结点结构和顶点结点结构见
p164的图所示。
返回主目录
../../ppt/%E6%95%99%E6%A1%
邻接多重表的结构类型说明如下：
typedef struct EdgeNode {
int mark,ivex,jvex;
struct EdgeNode *ilink, *jlink;
}EdgeNode;
typedef struct {
VertexData data;
EdgeNode *firstedge;
}VertexNode;
返回主目录
../../ppt/%E6%95%99%E6%A1%
typedef struct{
VertexNode vertex[MAX_VERTEX_NUM];
int vexnum, arcnum; /*图的顶点数和弧数*/
GraphKind kind; /*图的种类*/
} AdjMultiList;
/*基于图的邻接多重表表示法(Adjacency Multi_list)*/
图G2的邻接多重表见p165的图所示。
返回主目录
../../ppt/%E6%95%99%E6%A1%
图的遍历
图的遍历：从图中的某个顶点出发，按某种方法对
图中的所有顶点访问且仅访问一次。
为了保证图中的各顶点在遍历过程中访问且仅
访问一次，需要为每个顶点设一个访问标志，用以
标示图中每个顶点是否被访问过，访问标志用数组
visited[n]来表示。
图的遍历方法有两种：
深度优先搜索和广度优先搜索
返回主目录
../../ppt/%E6%95%99%E6%A1%
深度优先搜索：
深度优先搜索（Depth_First Search）是指按照深度
方向搜索 ，它类似于树的先根遍历。
深度优先算法的基本思想是：
（1）从图中某个顶点v0出发，首先访问v0。
（2）找出刚访问过的顶点vi的第一个未被访问的邻
接点，然后访问该顶点。重复此步骤，直到当前的
顶点没有未被访问的邻接点为止。
（3）返回前一个访问过的顶点，找出该顶点的下一
个未被访问的邻接点，访问该顶点。转2。
返回主目录
../../ppt/%E6%95%99%E6%A1%
采用递归的形式说明，则深度优先搜索连通子图的
的基本思想可表示为：
（1）访问出发点v0。
（2）依次以v0的未被访问的邻接点为出发点，深度
优先搜索图，直至图中所有与v0有路径相通的顶点
都被访问。
若此时图中还有顶点未被访问，则另选图中一
个未被访问的顶点作为起始点，重复上述深度优先
搜索过程，直至图中所有顶点均被访问过为止。
返回主目录
../../ppt/%E6%95%99%E6%A1%
深度优先搜索的过程示例见p167的图所示。
其中实箭头代表访问方向，虚箭头代表回溯方向，
箭头旁边的数字代表搜索顺序，A为起始顶点。
8
A D G
B E H
C F I
1
2
3
6
7 10
11
4
15
5
14
9
13
12
16
访问序列为：A、B、C、F、E、G、D、H、I。
返回主目录
../../ppt/%E6%95%99%E6%A1%
图的深度优先搜索的算法描述如下：
#define True 1
#define False 0
#define Error –1 /*出错*/
#define Ok 1
int visited[MAX_VERTEX_NUM]; /*访问标志数组*/
返回主目录
../../ppt/%E6%95%99%E6%A1%
void TraverseGraph (Graph g)
/*对图g进行深度优先搜索，Graph 表示图的一种存储结构，如数组表示
法或邻接表等*/
{
for (vi=0;vi<;vi++) visited[vi]=False ;/*访问标志数组初始*/
for( vi=0;vi<;vi++) /*调用深度遍历连通子图的操作*/
/*若图g是连通图，则此循环只执行一次*/
if (！visited[vi] ) DepthFirstSearch(g，vi)；
}/* TraverseGraph */
返回主目录
../../ppt/%E6%95%99%E6%A1%
深度遍历v0所在地连通子图算法如下：
void DepthFirstSearch（Graph g, int v0） /*深度遍历v0所在的连通子图*/
{
visit（v0）；visited[v0] =True；/*访问顶点v0，并置访问标志数组相应分量值*/
w=FirstAdjVertex(g,v0);
while ( w!=-1) /*邻接点存在*/
{ if(! visited [w] ) DepthFirstSearch(g,w); /*递归调用DepthFirstSearch*/
w=NextAdjVertex(g,v0,w); /*找下一个邻接点*/
}
} /*DepthFirstSearch*/
返回主目录
../../ppt/%E6%95%99%E6%A1%
上述算法中对于FirstAdjVertex（g，v0）以及NextAdjVertex
（g，v0，w）并没有具体实现。因为对于图的不同
存储方法，两个操作的实现方法不同，时间耗费也
不同。
下面的算法是在邻接矩阵与邻接表方式下实现上面
算法的功能。
返回主目录
../../ppt/%E6%95%99%E6%A1%
1）用邻接矩阵方式实现深度优先搜索
void DepthFirstSearch(AdjMatrix g, int v0)
/* 图g 为邻接矩阵类型AdjMatrix */
{visit(v0);visited[v0]=True;
for ( vj=0;vj<n;vj++)
if (!visited[vj] && [v0][vj].adj==1)
DepthFirstSearch(g,vj);
} /* DepthFirstSearch */
返回主目录
../../ppt/%E6%95%99%E6%A1%
2）用邻接表方式实现深度优先搜索
void DepthFirstSearch(AdjList g, int v0)
/*图g为邻接表类型AdjList */
{visit(v0) ；visited[v0]=True；
p=[v0].firstarc；
while( p!=NULL )
{if (! visited[p->adjvex])
DepthFirstSearch（g， p->adjvex）；
p=p->nextarc；
}
}/*DepthFirstSearch*/
返回主目录
../../ppt/%E6%95%99%E6%A1%
分析算法：以邻接表作为存储结构，查找每个顶点
的邻接点的时间复杂度为O(e)， 其中e是无向图中
的边数或有向图中弧数, 则深度优先搜索图的时间
复杂度为O(n+e)。
返回主目录
../../ppt/%E6%95%99%E6%A1%
3）用非递归过程实现深度优先搜索
void DepthFirstSearch(Graph g, int v0) /*从v0出发深度优先搜索图g*/
{ InitStack(S); /*初始化空栈*/
Push(S, v0)；
while ( ! Empty(S))
{ v=Pop(S);
if (!visited(v)) /*栈中可能有重复结点*/
{ visit(v); visited[v]=True; }
w=FirstAdj(g, v); /*求v的第一个邻接点*/
while (w!=-1 )
{ if (!visited(w)) Push(S, w);
w=NextAdj(g, v, w); /*求v相对于w的下一个邻接点*/
}
}
}
返回主目录
../../ppt/%E6%95%99%E6%A1%
广度优先搜索
广度优先搜索（Breadth_First Search）是指按照广
度方向搜索，它类似于树的按层次遍历。
广度优先搜索的基本思想是：
（1）从图中某个顶点v0出发，首先访问v0。
（2）依次访问v0的各个未被访问的邻接点。
（3）分别从这些邻接点（端结点）出发，依次访问
它们的各个未被访问的邻接点（新的端结点）。
返回主目录
../../ppt/%E6%95%99%E6%A1%
访问时应保证：如果Vi和Vk为当前端结点，且
Vi在Vk之前被访问，则Vi的所有未被访问的邻接点
应在Vk的所有未被访问的邻接点之前访问。重复
（3），直到所有端结点均没有未被访问的邻接点
为止。
若此时还有顶点未被访问，则选一个未被访问
的顶点作为起始点，重复上述过程，直至所有顶点
均被访问过为止。
返回主目录
../../ppt/%E6%95%99%E6%A1%
广度优先搜索过程示例见p169的图所示。其中
箭头代表搜索方向，箭头旁边的数字代表搜索顺序，
A为起始顶点。
A D G
B E H
C F I
1
4
6
5 7
8
2
3
访问序列为：A、B、E、D、C、G、F、H、I。
返回主目录
../../ppt/%E6%95%99%E6%A1%
广度优先搜索连通子图的算法如下：
void BreadthFirstSearch(Graph g, int v0)
/*广度优先搜索图g中v0所在的连通子图*/
{
visit(v0); visited[v0]=True;
InitQueue(&Q); /*初始化空队*/
EnterQueue(&Q,v0)；/* v0进队*/
while ( ! Empty(Q))
{ DeleteQueue(&Q, &v); /*队头元素出队*/
w=FirstAdj(g,v); /*求v的第一个邻接点*/
返回主目录
../../ppt/%E6%95%99%E6%A1%
while (w!=-1 )
{ if (!visited(w))
{ visit(w); visited[w]=True;
EnterQueue(&Q, w);
}
w=NextAdj(g, v, w); /*求v相对于w的下一个邻接点*/
}
}
}
返回主目录
../../ppt/%E6%95%99%E6%A1%
图的连通性问题
无向图的连通分量
在对图遍历时，对于连通图，无论是广度优先
搜索还是深度优先搜索，仅需要调用一次搜索过程，
即从任一个顶点出发，便可以遍历图中的各个顶点。
对于非连通图，则需要多次调用搜索过程，而每次
调用得到的顶点访问序列恰为各连通分量中的顶点
集。调用搜索过程的次数就是该图连通分量的个数。
返回主目录
../../ppt/%E6%95%99%E6%A1%
例如：p171的图(a)是一个非连通图，按照它的
邻接表进行深度优先搜索遍历，三次调用深度优先
搜索（DepthFirstSearch）过程得到的访问顶点序
列为：
1，2，4，3，9
5，6，7
8，10
因此有三个连通分量。如p171的图(c).
返回主目录
../../ppt/%E6%95%99%E6%A1%
最小生成树
在一个连通网的所有生成树中，各边的代价之和最
小的那棵生成树称为该连通网的最小代价生成树
（Minimum Cost Spanning Tree），简称为最小生
成树。
最小生成树的重要性质如下：
设N=(V,{E}) 是一连通网，U 是顶点集V的一个非空
子集。若（u , v）是一条具有最小权值的边，其中
u∈U，v∈V-U，则存在一棵包含边（u , v）的最
小生成树。
返回主目录
../../ppt/%E6%95%99%E6%A1%
用反证法来证明这个最小生成树（MST）的性质：
假设不存在这样一棵包含边（u , v）的最小生成
树。任取一棵最小生成树T，将（u , v）加入T中。
根据树的性质，此时T中必形成一个包含（u , v）的
回路，且回路中必有一条边（u’ , v’）的权值大于或
等于（u , v）的权值。删除（u , v），则得到一棵
代价小于等于T的生成树T’，且T’为一棵包含边（u ,
v）的最小生成树。这与假设矛盾。
返回主目录
../../ppt/%E6%95%99%E6%A1%
一个连通网的最小生成树算法：
1. 普里姆算法
假设N=(V,{E})是连通网，TE为最小生成树中边的集合。
（1）初始U={u0}(u0∈V),TE=φ；
（2）在所有u∈U, v∈V-U的边中选一条代价最小的边
（u0，v0）并入集合TE，同时将v0并入U；
（3）重复（2），直到U=V为止。
此时，TE中必含有n-1条边，则T=（V，{TE}）为N的最
小生成树。
返回主目录
../../ppt/%E6%95%99%E6%A1%
普里姆算法是逐步增加U中的顶点，可称为“加点法”
注意：选择最小边时，可能有多条同样权值的边可
供选择，此时任选其一。
为了实现这个算法需设一个辅助数组closedge[ ]，以
记录从U道V-U具有最小代价的边。对每个顶点v∈V
-U，在辅助数组中存在一个分量closedge[v]，它包括
两个域vex和lowcost，其中lowcost存储该边上的权，
显然有
closedge[v].lowcoast=Min({cost(u,v) | u∈U})
返回主目录
../../ppt/%E6%95%99%E6%A1%
普里姆算法可描述为：
struct
{ VertexData adjvex;
int lowcost;
} closedge[MAX_VERTEX_NUM];
/* 求最小生成树时的辅助数组*/
返回主目录
../../ppt/%E6%95%99%E6%A1%
MiniSpanTree_Prim(AdjMatrix gn, VertexData u)
/*从顶点u出发，按普里姆算法构造连通网gn 的最小生成树，并
输出生成树的每条边*/
{k=LocateVertex(gn, u);
closedge[k].lowcost=0; /*初始化，U={u} */
for (i=0;i<;i++)
if ( i!=k) /*对V-U中的顶点i，初始化closedge[i]*/
{closedge[i].adjvex=u; closedge[i].lowcost=[k][i].adj;}
for (e=1;e<=-1;e++) /*找n-1条边(n= ) */
{
k0=Minium(closedge); /* closedge[k0]中存有当前最小边
（u0,v0）的信息*/ 返回主目录
../../ppt/%E6%95%99%E6%A1%
u0= closedge[k0].adjvex; /* u0∈U*/
v0= [k0] /* v0∈V-U*/
printf(u0, v0); /*输出生成树的当前最小边（u0,v0）*/
closedge[k0].lowcost=0; /*将顶点v0纳入U集合*/
for ( i=0 ;i<vexnum;i++) /*在顶点v0并入U之后，更新
closedge[i]*/
if ( [k0][i].adj <closedge[i].lowcost)
{ closedge[i].lowcost= [k0][i].adj;
closedge[i].adjvex=v0;
}
}
}
返回主目录
../../ppt/%E6%95%99%E6%A1%
P173的图(a)是一个连通网，由普里姆算法构
造最小生成树的过程见图(b)~(f)所示。
算法中各参量的变化见p173的表7－1。
返回主目录
../../ppt/%E6%95%99%E6%A1%
2. 克鲁斯卡尔算法
假设N=(V,{E})是连通网，将N中的边按权值从小到
大的顺序排列；
（1）将n个顶点看成n个集合；
（2）按权值由小到大的顺序选择边，所选边应满足
两个顶点不在同一个顶点集合内，将该边放到生成
树边的集合中。同时将该边的两个顶点所在的顶点
集合合并；
（3）重复（2），直到所有的顶点都在同一个顶点
集合内。
返回主目录
../../ppt/%E6%95%99%E6%A1%
克鲁斯卡尔算法是逐步增加生成树的边，故称为“加
边法”
以p174的连通图(a)为例，说明克鲁斯卡尔算法
的执行过程。
返回主目录
../../ppt/%E6%95%99%E6%A1%
有向无环图的应用
拓扑排序（Topological Sort）
AOV-网：用顶点表示活动，用弧表示活动间的优先
关系的有向无环图，称为顶点表示活动的网
（Activity On Vertex Network），简称为AOV-网。
如p175的表7-2 课程关系，用顶点表示课程，弧表
示先决条件，则表7－2可用一个有向无环图表示。
见图p175的图。
返回主目录
../../ppt/%E6%95%99%E6%A1%
拓扑序列：在有向图G=（V，{E}）中， V中顶点
的线性序列（vi1,,vi1,,vi3,…，vin）称为拓扑序列。
此序列必须满足：对序列中任意两个顶点vi、vj，在
G中有一条从vi到vj的路径，则在序列中vi必排在vj
之前。
如p175的图的一个拓扑序列为：
C1,C2,C3,C4,C5,C8,C9,C7,C6。
返回主目录
../../ppt/%E6%95%99%E6%A1%
AOV-网的特性如下：
若v
i
为v
j
的先行活动，v
j
为v
k
的先行活动，则v
i
必
为v
k
的先行活动，即先行关系具有可传递性。
AOV-网的拓扑序列不是唯一的。
如p175的图的另一个拓扑序列为：
C1,C2,C3, C8 , C4,C5, C9,C7,C6。
返回主目录
../../ppt/%E6%95%99%E6%A1%
求拓扑排序的基本思想：
（1）从有向图中选一个无前驱的顶点输出；
（2）将此顶点和以它为起点的弧删除；
（3）重复（1）、（2），直到不存在无前驱的顶点；
（4）若此时输出的顶点数小于有向图中的顶点数，
则说明有向图中存在回路，否则输出的顶点的顺序
即为一个拓扑序列。
例如p176的图所示的AOV－网，其拓扑序列为：
v1,v6,v4,v3,v2,v5或v1, v3, v2, v6,v4, v5 返回主目录
../../ppt/%E6%95%99%E6%A1%
对于有向图的不同存储形式，有不同实现的拓扑排
序算法。
1）基于邻接矩阵表示的存储结构
A为有向图G的邻接矩阵，则有
（1）找G中无前驱的顶点 —在A中找到值全为0的列；
（2）删除以i为起点的所有弧 —将矩阵中i对应的行
全部置为0。
返回主目录
../../ppt/%E6%95%99%E6%A1%
算法步骤为：
（1）取1作为第一新序号；
（2）找一个未新编号的、值全为0的列j，若找到则转（3）；
否则，若所有的列全部都编过号，拓扑排序结束； 若有列未
曾被编号，则该图中有回路；
（3）输出列号对应的顶点j，把新序号赋给所找到的列；
（4）将矩阵中j对应的行全部置为0;
（5）新序号加1，转（2）；
返回主目录
../../ppt/%E6%95%99%E6%A1%
2）基于邻接表的存储结构
入度为零的顶点即没有前趋的顶点，因此我们
可以附设一个存放各顶点入度的数组indegree [ ]，
于是有
（1）找G中无前驱的顶点 ——查找indegree [ i]为零的顶点vi
；
（2）删除以i为起点的所有弧——对链在顶点i后面的所有邻
接顶点k，将对应的indegree[k]减1。
为了避免重复检测入度为零的顶点，可以再设置一个辅
助栈，若某一顶点的入度减为0，则将它入栈。每当输出某一
顶点时，便将它从栈中删除。 返回主目录
../../ppt/%E6%95%99%E6%A1%
拓扑排序的实现算法
int TopoSort (AdjList G)
{ Stack S;
int indegree[MAX_VERTEX_NUM];
int i, count, k;
ArcNode *p;
FindID(G,indegree); /*求各顶点入度*/
InitStack(&S); /*初始化辅助栈*/
for(i=0;i<;i++)
if(indegree[i]==0) Push(&S,i); /*将入度为0的顶点入栈*/
count=0;
返回主目录
../../ppt/%E6%95%99%E6%A1%
while(!StackEmpty(S))
{ Pop(&S,&i);
printf("%c",[i].data);
count++; /*输出i号顶点并计数*/
p=[i].firstarc;
while(p!=NULL)
{ k=p->adjvex;
indegree[k]--; /*i号顶点的每个邻接点的入度减1*/
if(indegree[k]==0) Push(&S, k); /*若入度减为0，则入栈*/
p=p->nextarc;
}
} /*while*/
if (count<) return(Error); /*该有向图含有回路*/
else return(Ok);
}
返回主目录
../../ppt/%E6%95%99%E6%A1%
求各顶点入度的函数
void FindID( AdjList G, int indegree[MAX_VERTEX_NUM])
/*求各顶点的入度*/
{ int i; ArcNode *p;
for(i=0;i<;i++)
indegree[i]=0;
for(i=0;i<;i++)
{p=[i].firstarc;
while(p!=NULL)
{indegree[p->adjvex]++;
p=p->nextarc;
}
} /* for */
}
返回主目录
../../ppt/%E6%95%99%E6%A1%
P176的图所示的AOV-网的邻接表如图p178的图
所示，用拓扑排序算法求出的拓扑序列为：
v6，v1，v3，v2，v4，v5。
算法的时间复杂度分析：
若有向无环图有n个顶点和e条弧，则在拓扑排
序的算法中，for循环需要执行n次，时间复杂度为
O(n)；对于while循环，由于每一顶点必定进一次
栈，出一次栈，其时间复杂度为O(e)；故该算法的
时间复杂度为O(n+e)。
返回主目录
../../ppt/%E6%95%99%E6%A1%
关键路径
AOE-网：在有向图中，用顶点表示事件，用弧表
示活动，弧的权值表示活动所需要的时间。 我们
把用这种方法构造的有向无环图叫做边表示活动的
网（Activity On Edge Network）,简称AOE-网。
AOE-网用在工程计划和管理中，人们最关心的是：
哪些活动是影响工程进度的关键活动？
至少需要多长时间能完成整个工程？
返回主目录
../../ppt/%E6%95%99%E6%A1%
源点：存在唯一的、入度为零的顶点，叫源点。
汇点：存在唯一的、出度为零的顶点，叫汇点。
关键路径：从源点到汇点的最长路径的长度即为完
成整个工程任务所需的时间，该路径叫做关键路径。
关键活动：关键路径上的活动叫做关键活动。
在AOE-网中的基本概念：
例如p179的图所示的AOE-网。V0为源点，表
示整个工程可以开始，v8为汇点，表示整个工程结
束。
返回主目录
../../ppt/%E6%95%99%E6%A1%
几个重要的定义：
事件vi的最早发生时间ve(i)：从源点到顶点vi的最
长路径的长度，叫做事件vi的最早发生时间。
求ve(i) 时可从源点开始，按拓扑顺序向汇点递推：
ve(0)=0；
ve(i)=Max{ve(k)＋dut(<k,i>)}
<k,i>∈T,1≤i≤n-1;
其中，T为所有以i为头的弧<k,i>的集合，
dut（<k,i>）表示与弧<k,i>对应的活动的持续时间。
返回主目录
../../ppt/%E6%95%99%E6%A1%
事件vi的最晚发生时间vl(i)：在保证汇点按其最早
发生时间发生这一前提下，事件vi的最晚发生时间。
在求出ve(i)的基础上， 可从汇点开始，按逆拓扑顺
序向源点递推，求出vl(i)：
vl(n-1)=ve(n-1)；
vl(i)=Min{vl(k)＋dut(<i,k>)}
<i,k>∈S,0≤i≤n-2;
其中，S为所有以i为尾的弧<i,k>的集合，
dut（<i,k>）表示与弧<i,k>对应的活动的持续时间。
返回主目录
../../ppt/%E6%95%99%E6%A1%
活动ai的最早开始时间e(i)：如果活动ai对应的弧为
<j,k>，则e(i)等于从源点到顶点j的最长路径的长度，
即：e(i)=ve(j)
活动ai的最晚开始时间l(i)：如果活动ai对应的弧为
<j,k>，其持续时间为dut（<j,k>）则有：l(i)=vl(k)
- dut（<j,k>）
活动ai的松弛时间（时间余量）：ai的最晚开始时
间与ai的最早开始时间之差：l(i)- e(i)。
显然，松弛时间（时间余量）为0的活动为关键活动。
返回主目录
../../ppt/%E6%95%99%E6%A1%
求关键路径的基本步骤：
（1）对图中顶点进行拓扑排序，在排序过程中按拓
扑序列求出每个事件的最早发生时间ve(i)；
（2）按逆拓扑序列求每个事件的最晚发生时间vl(i)
；
（3）求出每个活动ai的最早开始时间e(i)和最晚发生
时间l(i)；
4) 找出e(i)=l(i) 的活动ai，即为关键活动。
返回主目录
../../ppt/%E6%95%99%E6%A1%
修改后的拓扑排序算法
int ve[MAX_VERTEX_NUM]; /*每个顶点的最早发生时间*/
int TopoOrder(AdjList G,Stack * T)
/* G为有向网，T为返回拓扑序列的栈，S为存放入度为0的顶点的栈*/
{ int count,i,j,k; ArcNode *p;
int indegree[MAX_VERTEX_NUM]; /*各顶点入度数组*/
Stack S;
InitStack(T); InitStack(&S); /*初始化栈T, S*/
FindID(G, indegree); /*求各个顶点的入度*/
for(i=0;i<;i++)
if(indegree[i]==0) Push(&S,i); 返回主目录
../../ppt/%E6%95%99%E6%A1%
count=0;
for(i=0;i<;i++)
ve[i]=0; /*初始化最早发生时间*/
while(!StackEmpty(S))
{Pop(&S,&j);
Push(T,j);
count++;
p=[j].firstarc;
while(p!=NULL)
{ k=p->adjvex;
if(--indegree[k]==0) Push(&S,k); /*若顶点的入度减为0，则入栈*/
返回主目录
../../ppt/%E6%95%99%E6%A1%
if(ve[j]+p->weight>ve[k]) ve[k]=ve[j]+p->weight;
p=p->nextarc;
} /*while*/
} /*while*/
if(count<) return(Error);
else return(Ok);
}
返回主目录
../../ppt/%E6%95%99%E6%A1%
求关键路径的实现算法
int CriticalPath(AdjList G)
{ ArcNode *p;
int i,j,k,dut,ei,li; char tag;
int vl[MAX_VERTEX_NUM]; /*每个顶点的最迟发生时间*/
Stack T;
if(!TopoOrder(G,&T)) return(Error);
for(i=0;i<;i++)
vl[i]=ve[i]; /*初始化顶点事件的最迟发生时间*/
while(!StackEmpty(T)) /*按逆拓扑顺序求各顶点的vl值*/
{ Pop(&T,&j);
p=[j].firstarc; 返回主目录
../../ppt/%E6%95%99%E6%A1%
while(p!=NULL)
{ k=p->adjvex; dut=p->weight;
if(vl[k]-dut<vl[j]) vl[j]= vl[k]-dut;
p=p->nextarc;
} /* while */
} /* while*/
for(j=0;j<;j++) /*求ei,li和关键活动*/
{ p=[j].firstarc;
while(p!=NULL)
{ k=p->Adjvex; dut=p->weight;
ei=ve[j];li=vl[k]-dut;
返回主目录
../../ppt/%E6%95%99%E6%A1%
tag=(ei==li)?'*':' ';
printf("%c,%c,%d,%d,%d,%c\n",
[j].data,[k].data,dut,ei,li,tag); /*输出关键活动*/
p=p->nextarc;
} /*while*/
} /* for */
return(Ok);
} /*CriticalPath*/
该算法的时间复杂度为O(n+e) 。用该算法求p179的
图中AOE-网的关键路径，结果如p181的图。
返回主目录
../../ppt/%E6%95%99%E6%A1%
最短路径
求某一顶点到其它各顶点的最短路径
设有带权的有向图D=(V,{E})，D中的边权为 W(e)。
已知源点为v0，求v0到其它各顶点的最短路径。
如p184的图所示的带权有向图，其源点v0到其它
各顶点的最短路径如p184的表7－3所示。
返回主目录
../../ppt/%E6%95%99%E6%A1%
用迪杰斯特拉（Dijkstra） 求最短路径算法
基本思想是：按路径长度递增的顺序，逐个产生各
最短路径。
首先引进辅助向量dist[ ]，它的每一个分量dist[i]表
示已经找到的且从开始点v0到每一个终点vi的当前最
短路径的长度。它的初态为：如果从v0到vi有弧，则
dist[i]为弧的权值；否则dist[i]为∞。其中，长度为
dist[j]=Min{dist[i] | vi∈V}
的路径是从v0出发的长度最短的一条最短路径，此
路径为（v0，vj）。
返回主目录
../../ppt/%E6%95%99%E6%A1%
当我们按长度递增的顺序来产生各个最短路径时，设
S为已经求得的最短路径的终点集合。我们可以证明：
下一条最短路径或者是弧（v0，vx），或者是中间经
过S中的某些顶点，而后到达vx的路径。
一般情况下，下一条长度最短的最短路径的长度必
是
dist[j]=Min{dist[i] | vi∈V－S}
其中，dist[i]或者是弧（v0，vi）上的权值，或者是dist[k]
（vk∈S）和弧（vk，vi）上的权值之和。
返回主目录
../../ppt/%E6%95%99%E6%A1%
我们将图中的顶点分为两组：
S —已求出的最短路径的终点集合(开始为{v0})。
V-S —尚未求出最短路径的顶点集合(开始为V－
{v0}的全部结点)。
按最短路径长度的递增顺序逐个将第二组的顶点加
入到第一组中。
返回主目录
../../ppt/%E6%95%99%E6%A1%
迪杰斯特拉算法的主要步骤：
（1）g为用邻接矩阵表示的带权图。
S←—{v0} ，dist[i]= [v0][vi]；
将v0到其余顶点的路径长度初始化为权值；
（2）选择vk，使得 dist[vk]=min(dist[i] | vi∈V－S)
vk为目前求得的下一条从v0出发的最短路径的终点。
（3）修改从v
0
出发到集合V－S上任一顶点v
i
的最短路径的长
度。如果 dist[k]+ [k][i]<dist[i]
则将dist[i]修改为： dist[k]+ [k][i]
（4)重复(2)、(3) n-1次，即可按最短路径长度的递增顺序，
逐个求出v
0
到图中其它每个顶点的最短路径。
返回主目录
../../ppt/%E6%95%99%E6%A1%
求图的最短路径的迪杰斯特拉算法
typedef SeqList VertexSet;
ShortestPath_DJS(AdjMatrix g, int v0,
WeightType dist[MAX_VERTEX_NUM],
VertexSet path[MAX_VERTEX_NUM] )
/* path[i]中存放顶点i的当前最短路径。dist[i]中存放顶点i的当前最短路径长度*/
{ VertexSet s; /* s为已找到最短路径的终点集合*/
for ( i =0;i< ;i++) /*初始化dist[i]和path [i] */
{ InitList(&path[i]);
dist[i]=[v0][i];
if ( dist[i]<MAX)
{ AddTail(&path[i], [v0]); /* AddTail为表尾添加操作*/
AddTail(&path[i], [i]);
}
}
返回主目录
../../ppt/%E6%95%99%E6%A1%
InitList(&s);
AddTail(&s, [v0]); /* 将v0看成第一个已找到最短路径的终点*/
for ( t = 1 ;t<=-1; t++) /*求v0到其余n-1个顶点的最短路径(n=
)*/
{ min=MAX;
for ( i =0; i<;i++)
if (! Member([i], s) && dist[i]<min ) {k =i; min=dist[i];}
AddTail(&s, [k]);
for ( i =0; i<;i++) /*修正dist[i], i∈V-S*/
if (!Member([i], s) && (dist[k]+ [k][i]<dist[i]))
{dist[i]=dist[k]+ [k][i]; path[i]=path[k];
AddTail(&path[i], [i]); /* path[i]=path[k]∪{Vi} */
}
}
}
返回主目录
../../ppt/%E6%95%99%E6%A1%
求任意一对顶点间的最短路径
佛罗依德算法的基本思想
设图g用邻接矩阵法表示，求图g中任意一对顶点v
i、
、v
j
间的的最短路径。
（-1）将vi到vj 的最短的路径长度初始化为
[i][j]，然后进行如下n次比较和修正：
（0）在vi、vj间加入顶点v0，比较（vi,v0,vj）和
(vi,vj)的路径的长度，取其中较短的路径作为vi到vj
的且中间顶点号不大于0的最短路径。
返回主目录
../../ppt/%E6%95%99%E6%A1%
（1）在vi、vj间加入顶点v1，得（vi,…， v1）和(v1,…， vj)
，其中（vi,…,v1）是vi到v1 的且中间顶点号不大于0的最短路
径，(v1,…,vj) 是v1到vj 的且中间顶点号不大于0的最……短路
径，这两条路径在上一步中已求出。将（vi,…,v1,…,vj）与上
一步已求出的且vi到vj 中间顶点号不大于0的最短路径比较，
取其中较短的路径作为vi到vj 的且中间顶点号不大于1的最短
路径。
（2）在vi、vj间加入顶点v2，得（vi,…,v2）和(v2,…,vj)，其中
（vi,…,v2）是vi到v2 的且中间顶点号不大于1的最短路径，
(v2,…,vj) 是v2到vj 的且中间顶点号不大于1的最短路径，这两
条路径在上一步中已求出。将（vi,…,v2,…,vj）与上一步已求
出的且vi到vj 中间顶点号不大于1的最短路径比较，取其中较
短的路径作为vi到vj 的且中间顶点号不大于2的最短路径。
………
返回主目录
../../ppt/%E6%95%99%E6%A1%
依次类推，经过n次比较和修正，在第（n-1）步，
将求得vi到vj 的且中间顶点号不大于n-1的最短路径，
这必是从vi到vj的最短路径。
图g中所有顶点偶对v
i
、v
j
间的最短路径长度对应一
个n阶方阵D。在上述n+1步中，D的值不断变化，对
应一个n阶方阵序列。
返回主目录
../../ppt/%E6%95%99%E6%A1%
定义：
n阶方阵序列：D-1, D0, D1, D2, …Dn-1
其中 :
D-1[i][j]= [i][j]
Dk[i][j]=Min{Dk-1[i][j],
Dk-1[i][k]+Dk-1[k][j]} 0≤k≤n-1
显然，Dn-1中为所有顶点偶对vi、vj间的最终最短路
径长度。
返回主目录
../../ppt/%E6%95%99%E6%A1%
佛罗依德算法的描述
typedef SeqList VertexSet;
ShortestPath_Floyd(AdjMatrix g,
WeightType dist [MAX_VERTEX_NUM] [MAX_VERTEX_NUM],
VertexSet path[MAX_VERTEX_NUM] [MAX_VERTEX_NUM] )
/* g为带权有向图的邻接矩阵表示法， path [i][j]为v
i
到v
j
的当前最短
路径，dist[i][j]为v
i
到v
j
的当前最短路径长度*/
{
for (i=0; i<; i++)
for (j =0;j<; j++)
{ /*初始化dist[i][j]和path[i][j] */
InitList(&path[i][j]);
返回主目录
../../ppt/%E6%95%99%E6%A1%
dist[i][j]=[i][j];
if (dist[i][j]<MAX)
{AddTail(&path[i][j], [i]);
AddTail(&path[i][j], [j]);
}
}
for (k =0;k<;k++)
for (i =0;i<;i++)
for (j=0;j<;j++)
if (dist[i][k]+dist[k][j]<dist[i][j])
{dist[i][j]=dist[i][k]+dist[k][j];
paht[i][j]=JoinList(paht[i][k], paht[k][j]);
} /*JoinList为合并线性表操作*/
}
返回主目录
../../ppt/%E6%95%99%E6%A1%
利用佛罗依德算法，可求出p187的图(a)所示的
带权有向图G6中的每一对顶点之间的最短路径P及
其路径长度D，其结果如p187的图(c) 所示。
返回主目录
../../ppt/%E6%95%99%E6%A1%
