? 图的基本概念
? 图的存储表示
? 图的遍历与连通性
? 最小生成树
? 最短路径
? 活动网络
图的基本概念
? 图定义 图是由顶点集合 (vertex)及顶点间
的关系集合组成的一种数据结构,
Graph＝ ( V,E )
其中 V = { x | x ? 某个数据对象 }
是顶点的有穷非空集合；
E = {(x,y) | x,y ? V }
或 E = {<x,y> | x,y ? V && Path (x,y)}
是顶点之间关系的有穷集合，也叫做边
(edge)集合。 Path (x,y)表示从 x 到 y 的一
条单向通路,它是有方向的。
? 有向图与无向图 在有向图中，顶点对 <x,
y> 是有序的。在无向图中，顶点对 (x,y)是
无序的。
? 完全图 若有 n 个顶点的无向图有 n(n-1)/2
条边,则此图为完全无向图。有 n 个顶点
的有向图有 n(n-1) 条边,则此图为完全有向
图。
0 0 0 0
1
1
1 12 2
2 265433
? 邻接顶点 如果 (u,v) 是 E(G) 中的一条边，
则称 u 与 v 互为邻接顶点 。
? 子图 设有两个图 G＝ (V,E) 和 G‘＝ (V’,
E‘)。若 V’? V 且 E‘?E,则称 图 G’ 是 图 G
的子图。
? 权 某些图的边具有与它相关的数,称之为
权。这种带权图叫做网络。
0
1 2
3
子图 0
1
3
0
1 2
3
0
2
3
? 顶点的度 一个顶点 v的度是与它相关联的
边的条数。记作 TD(v)。 在有向图中,顶点
的度等于该顶点的入度与出度之和。
? 顶点 v 的入度 是以 v 为终点的有向边的条
数,记作 ID(v); 顶点 v 的出度 是以 v 为始点
的有向边的条数,记作 OD(v)。
? 路径 在图 G＝ (V,E) 中,若从顶点 vi 出发,
沿一些边经过一些顶点 vp1,vp2,…,vpm，到
达顶点 vj。则称顶点序列 (vi vp1 vp2,.,vpm vj)
为从顶点 vi 到顶点 vj 的路径 。它经过的边
(vi,vp1),(vp1,vp2),...,(vpm,vj) 应是属于 E
的边。
? 路径长度 非带权图的路径长度是指此路径
上边的条数。带权图的路径长度是指路径
上各边的权之和。
? 简单路径 若路径上各顶点 v1,v2,...,vm 均不
互相重复,则称这样的路径为简单路径。
? 回路 若路径上第一个顶点 v1 与最后一个
顶点 vm 重合,则称这样的路径为回路或环。
0
1 2
3
0
1 2
3
0
1 2
3
? 连通图与连通分量 在无向图中,若从顶点
v1到顶点 v2有路径,则称顶点 v1与 v2是连通
的。如果图中任意一对顶点都是连通的,则
称此图是连通图。非连通图的极大连通子
图叫做连通分量。
? 强连通图与强连通分量 在有向图中,若对
于每一对顶点 vi和 vj,都存在一条从 vi到 vj和
从 vj到 vi的路径,则称此图是强连通图。非
强连通图的极大强连通子图叫做强连通分
量。
? 生成树 一个连通图的生成树是其极小连
通子图，在 n个顶点的情形下，有 n-1条边。
图的抽象数据类型
class Graph {
public:
Graph ( );
void InsertVertex ( Type & vertex );
void InsertEdge ( int v1,int v2,int weight );
void RemoveVertex ( int v );
void RemoveEdge ( int v1,int v2 );
int IsEmpty ( );
Type GetWeight ( int v1,int v2 );
int GetFirstNeighbor ( int v );
int GetNextNeighbor ( int v1,int v2 );
}
图的存储表示
? 在图的邻接矩阵表示中，有一个 记录各个
顶点信息 的 顶点表, 还有一个 表示各个顶
点之间关系 的 邻接矩阵 。
? 设图 A = (V,E)是一个有 n 个顶点的图,图
的邻接矩阵是一个二维数组 A.edge[n][n]，
定义：
邻接矩阵 (Adjacency Matrix)
?
?
? ??
?
,
),(,,
]][[,
否则
或者如果
0
><1
A
EjiEji
jiE d g e
? 无向图的邻接矩阵是对称的 ;
? 有向图的邻接矩阵可能是不对称的。
0
1 2
3 ??
?
?
?
?
?
?
?
?
?
0101
1010
0101
1010
A, e d g e
0
1
2
?
?
?
?
?
?
?
?
?
000
101
010
A, ed g e
? 在有向图中,统计第 i 行 1 的个数可得顶点
i 的 出度,统计第 j 行 1 的个数可得顶点 j
的 入度 。
? 在无向图中,统计第 i 行 (列 ) 1 的个数可得
顶点 i的 度 。
网络的邻接矩阵
??
?
?
?
??
??????
?????
?
ji
ji,ji,ji
ji,ji,jiji
ji
若
或且若
或且若
,
)(,
)(),,(
]][[
0
EE
EEW
A,e d ge
8
6
3
1
29 5
4
2
0
3
1
?
?
?
?
?
?
?
?
?
?
??
?
?
?
06
8053
290
410
A,e d g e
用邻接矩阵表示的图的类的定义
const int MaxEdges = 50;
const int MaxVertices = 10;
template <class Type>
class Graph {
private:
SeqList<Type> VerticesList (MaxVertices);
float Edge[MaxVertices][MaxVertices];
int CurrentEdges;
int FindVertex (SeqList <Type> & L;
const Type vertex){ return L.Find (vertex); }
int GetVertexPos ( int vertex )
{ return FindVertex (VerticesList,vertex); }
public:
Graph ( int sz = MaxEdges );
int GraphEmpty ( )
const { return VerticesList.IsEmpty ( ); }
int GraphFull( )
const { return VerticesList.IsFull( ) ||
CurrentEdges == MaxEdges; }
int NumberOfVertices ( )
{ return VerticesList.last +1; }
int NumberOfEdges ( )
{ return CurrentEdges; }
Type GetValue ( int i )
{ return i >= 0 && i <= VerticesList.last
VerticesList.data[i], NULL; }
DistType GetWeight ( int v1,int v2 );
int GetFirstNeighbor ( int v );
int GetNextNeighbor ( int v1,int v2 );
void InsertVertex ( const Type vertex );
void InsertEdge
( int v1,int v2,float weight );
void RemoveVertex ( int v );
void RemoveEdge ( int v1,int v2 );
}
邻接矩阵实现的部分图操作
template <class Type> Graph <Type>,:
Graph ( int sz ) { //构造函数
for ( int i = 0; i < sz; i++ )
for ( int j = 0; j < sz; j++ ) Edge[i][j] = 0;
CurrentEdges = 0;
}
template <class Type> folat Graph<Type>,:
GetWeight( int v1,int v2 ) {
//给出以顶点 v1 和 v2 为两端点的边上的权值
if (v1 != -1 && v2 != -1) return Edge[v1][v2];
else return 0;
}
template <class Type> int Graph <Type>::
GetFirstNeighbor ( const int v ) {
//给出顶点位置为 v 的第一个邻接顶点的位置
if ( v != -1 ) {
for ( int col = 0; col <= VerticesList.last;
col++ )
if ( Edge[v][col] > 0 &&
Edge[v][col] < MaxValue ) return col;
}
else return -1;
}
template <class Type> int Graph<Type>,:
GetNextNeighbor ( int v,int w ) {
//给出顶点 v的某邻接顶点 w的下一个邻接顶点
int col;
if ( v != -1 && w != -1 ) {
for ( col = w+1; col <= VerticesList.last;
col++ )
if ( Edge[v][col] > 0 &&
Edge[v][col] < MaxValue ) return col;
}
return -1;
}
邻接表 (Adjacency List)
? 无向图的邻接表
同一个顶点发出的边链接在同一个边链表
中，每一个链结点代表一条边 (边结点 ),结
点中有另一顶点的下标 dest 和指针 link。
A
B C
D
data adj
A
B
C
D
0
1
2
3
dest link dest link
?
?
?
?
1 3
0 2
1
0
? 有向图的邻接表和逆邻接表
A
B
C
data adj
A
B
C
0
1
2
dest link
dest link
?
邻接表 (出边表 )
data adj
A
B
C
0
1
2
dest link
逆邻接表 (入边表 )
1
0 2
?
?
?
?
?
0
1
1
? 网络 (带权图 ) 的邻接表
B
A
C
D6
95 2
8
data adj
A
B
C
D
0
1
2
3
dest cost link
?
?
?
?1 5 3 6
2 8
3 2
1 9
(出边表 )(顶点表 )
? 带权图的边结点中保存该边上的权值 cost。
? 顶点 i 的边链表的表头指针 adj 在顶点表的
下标为 i 的顶点记录中，该记录还保存了该
顶点的其它信息。
? 在邻接表的边链表中,各个边结点的链入
顺序任意，视边结点输入次序而定。
? 设图中有 n 个顶点,e 条边，则 用邻接表表
示无向图时,需要 n 个顶点结点,2e 个边
结点；用 邻接表表示有向图时,若不考虑
逆邻接表，只需 n 个顶点结点,e 个边结点。
邻接表表示的图的类定义
#define DefaultSize 10
template <class Type> class Graph;
template <class Type> struct Edge { //边结点
friend class Graph<Type>;
int dest; //目标顶点下标
float cost; //边上的权值
Edge<Type> * link; //下一边链接指针
Edge ( ) { } //构造函数
Edge ( int D,Type C ),
dest (D),cost (C),link (NULL) { }
int operator != ( Edge<Type>& E )
const { return dest != E.dest; }
}
template <class Type> struct Vertex { //顶点
friend class Graph <Type>;
NemeType data; //顶点数据
Edge<DistType> *adj; //边链表头指针
}
template <class Type> class Graph { //图类
private:
Vertex<Type> * NodeTable; //顶点表
int NumVertices; //当前顶点个数
int MaxVertices; //最大顶点个数
int NumEdges; //当前边数
int GetVertexPos ( const Type vertex );
public:
Graph ( int sz );
~Graph ( );
int GraphEmpty ( )
const { return NumVertices == 0; }
int GraphFull ( ) const
{ return NumVertices == MaxVertices; }
NameType GetValue ( int i )
{ return i >= 0 && i < NumVertices?
NodeTable[i].data, NULL; }
int NumberOfVertices ( )
{ return NumVertices; }
int NumberOfEdges ( ) { return NumEdges; }
void InsertVertex ( Type vertex );
void RemoveVertex ( int v );
void InsertEdge ( int v1,int v2,float weight );
void RemoveEdge ( int v1,int v2 );
float GetWeight ( int v1,int v2 );
int GetFirstNeighbor ( int v );
int GetNextNeighbor ( int v,int w );
}
邻接表的构造函数和析构函数
template <class Type> Graph <Type>,:
Graph ( int sz = DefaultSize ), NumVertices (0),
MaxVertices (sz),NumEdges (0){
int n,e,k,j; Type name,tail,head;
float weight;
NodeTable = //创建顶点表
new Vertex<Type>[MaxVertices];
cin >> n; //输入顶点个数
for ( int i = 0; i < n; i++) //输入各顶点信息
{ cin >> name; InsertVertex ( name ); }
cin >> e; //输入边条数
for ( i = 0; i < e; i++) { //逐条边输入
cin >> tail >> head >> weight;
k = GetVertexPos ( tail );
j = GetVertexPos ( head );
InsertEdge ( k,j,weight ); //插入边
}
}
template <class Type> Graph <Type>,,
~Graph ( ) {
for ( int i = 0; i < NumVertices; i++ ) {
Edge<Type> *p = NodeTable[i].adj;
while ( p != NULL ) { //逐条边释放
NodeTable[i].adj = p->link;
delete p;
p = NodeTable[i].adj;
}
}
delete [ ] NodeTable; //释放顶点表
}
邻接表部分成员函数的实现
template <class Type> int Graph <Type>,:
GetVertexPos ( const Type vertex ) {
//根据顶点名 vertex查找它在邻接表中位置
for ( int i = 0; i < NumVertices; i++ )
if ( NodeTable[i].data == vertex ) return i;
return -1;
}
template <Class Type> int Graph <Type>,:
GetFirstNeighbor ( int v ) {
//查找顶点 v 第一个邻接顶点在邻接表中位置
if ( v != -1 ) { //若顶点存在
Edge<Type> * p = NodeTable[v].adj;
if ( p != NULL ) return p->dest;
}
return -1; //若顶点不存在
}
template <Class Type> int Graph <Type>,,
GetNextNeighbor ( int v,int w ) {
//查找顶点 v 在邻接顶点 w 后下一个邻接顶点
if ( v != -1 ) {
Edge<Type> * p = NodeTable[v1].adj;
while ( p != NULL ) {
if ( p->dest == w && p->link != NULL )
return p->link->dest;
//返回下一个邻接顶点在邻接表中位置
else p = p->link;
}
}
return -1; //没有查到下一个邻接顶点
}
template <Class Type> float Graph <Type>,:
GetWeight ( int v1,int v2) {
//取两端点为 v1 和 v2 的边上的权值
if ( v1 != -1 && v2 != -1 ) {
Edge<Type> * p = NodeTable[v1].adj;
while ( p != NULL ) {
if ( p->dest == v2 ) return p->cost;
else p = p->link;
}
}
return 0;
}
邻接多重表 (Adjacency Multilist)
? 在邻接多重表中,每一条边只有一个边结点。
为有关边的处理提供了方便。
? 无向图的情形
? 边结点的结构
mark vertex1 vertex2 path1 path2
其中,mark 是记录是否处理过的标记 ; vertex1
和 vertex2是该边两顶点位置。 path1域是链接
指针,指向下一条依附顶点 vertex1的边； path2
是指向下一条依附顶点 vertex2的边链接指针。
?顶点结点的结构
存储顶点信息的结点表 以顺序表方式组织,
每一个顶点结点有两个数据成员：其中，
data 存放与该顶点相关的信息,Firstout
是指示第一条依附该顶点的边的指针。在
邻接多重表中,所有依附同一个顶点的边
都链接在同一个单链表中。
data Firstout
需要时还可设置一个存放与该边相关的权
值的域 cost。
? 从 顶点 i 出发,可以循链找到所有依附于该
顶点的边，也可以找到它的所有邻接顶点。
? 有向图的情形
? 在用邻接表表示有向图时,有时需要同时使
用邻接表和逆邻接表。用有向图的邻接多
重表 (十字链表 )可把两个表结合起来表示。
? 边结点的结构
mark vertex1 vertex2 path1 path2
其中,mark是处理标记； vertex1和 vertex2
指明该有向边始顶点和终顶点的位置。
?顶点结点的结构
每个顶点有一个结点，它相当于出边表和
入边表的表头结点：其中，数据成员 data
存放与该顶点相关的信息，指针 Firstin指
示以该顶点为始顶点的出边表的第一条边，
Firstout指示以该顶点为终顶点的入边表
的第一条边。
data Firstin Firstout
path1是指向始顶点与该边相同的下一条边
的指针； path2是指向终顶点与该边相同的下
一条边的指针。需要时还可有权值域 cost。
–邻接多重表的结构
mark vtx1 vtx2 path1 path2
?
?
? ?
? ?
? ?
? ?
0 1
0 3
1 2
2 3
3 4
4 0
e1
e2
e3
e4
e5
e6
data Fin Fout
A
B
C
D
E
0
1
2
3
4
e1
e2
e3 e4
e5
e6
A
B C
D
E
图的遍历与连通性
? 从已给的连通图中某一顶点出发，沿着一
些边访遍图中所有的顶点，且使每个顶点
仅被访问一次，就叫做图的遍历 ( Graph
Traversal )。
? 图中可能存在回路，且图的任一顶点都可
能与其它顶点相通，在访问完某个顶点之
后可能会沿着某些边又回到了曾经访问过
的顶点。
? 为了避免重复访问，可设置一个标志顶点
是否被访问过的辅助数组 visited [ ]。
? 辅助数组 visited [ ] 的初始状态为 0,在图
的遍历过程中,一旦某一个顶点 i 被访问,
就立即让 visited [i] 为 1,防止它被多次访
问。
? 图的遍历的分类,
? 深度优先搜索
DFS (Depth First Search)
? 广度优先搜索
BFS (Breadth First Search)
深度优先搜索 DFS ( Depth First Search )
? 深度优先搜索的示例
A
CD
E
G
B
F IH
A
CD
E
G
B
F IH
1 2 3
45
6
7
8 9
1 2 3
45
6
7
8 9前进 回退
深度优先搜索过程 深度优先生成树
? DFS 在访问图中某一 起始顶点 v 后,由 v 出
发,访问它的任一 邻接顶点 w1; 再从 w1 出发,
访问 与 w1邻 接 但还 没有访问过的顶点 w2;
然后再从 w2 出发,进行类似的访问,… 如此
进行下去,直至到达所有的邻接顶点都被访
问过的顶点 u 为止 。接着,退回一步,退到
前一次刚访问过的顶点,看是否还有其它没
有被访问的邻接顶点。 如果有,则访问此顶
点,之后再从此顶点出发,进行与前述类似
的访问 ; 如果没有,就再退回一步进行搜索。
重复上述过程,直到连通图中所有顶点都被
访问过为止。
图的深度优先搜索算法
template<class Type> void Graph <Type>,:
DFS ( ) {
int * visited = new int [NumVertices];
for ( int i = 0; i < NumVertices; i++ )
visited [i] = 0; //访问数组 visited 初始化
DFS (0,visited ); //从顶点 0出发开始搜索
delete [ ] visited; //释放 visited
}
template<class Type> void Graph <Type>,:
DFS ( const int v,int visited [ ] ) {
cout << GetValue (v) << ? ?; //访问顶点 v
visited[v] = 1; //顶点 v 作访问标记
int w = GetFirstNeighbor (v);
//取 v 的第一个邻接顶点 w
while ( w != -1 ) { //若邻接顶点 w 存在
if ( !visited[w] ) DFS ( w,visited );
//若 顶点 w 未访问过,递归访问顶点 w
w = GetNextNeighbor ( v,w );
//取顶点 v 排在 w 后的下一个邻接顶点
}
}
广度优先搜索 BFS ( Breadth First Search )
? 广度优先搜索的示例
A
CD
E
G
B
F IH
A
CD
E
G
B
F H
1 2
34
5
6
7
8 9
1 2
34
5
6
7
8 9
广度优先搜索过程 广度优先生成树
I
? BFS在访问了 起始顶点 v 之后,由 v 出发,依
次访问 v 的各个 未被访问过的邻接顶点 w1,
w2,…,wt,然后再顺序访问 w1,w2,…,wt 的
所有还未被访问过的邻接顶点。再从这些访
问过的顶点出发，再访问它们的所有还未被
访问过的邻接顶点,… 如此做下去，直到
图中所有顶点都被访问到为止。
? 广度优先搜索是一种分层的搜索过程,每向
前走一步可能访问一批顶点,不像深度优先
搜索那样有往回退的情况。因此,广度优先
搜索不是一个递归的过程。
? 为了实现逐层访问,算法中使用了一个 队列,
以记忆正在访问的这一层和上一层的顶点,
以便于向下一层访问。
? 为避免重复访问,需要一个辅助数组 visited
[ ]，给被访问过的顶点加标记。
图的广度优先搜索算法
template<class Type> void Graph <Type>,:
BFS ( int v ) {
int * visited = new int[NumVertices];
for ( int i = 0; i < NumVertices; i++ )
visited[i] = 0; //visited初始化
cout << GetValue (v) << ' '; visited[v] = 1;
Queue<int> q; q.EnQueue (v); //进队列
while ( !q.IsEmpty ( ) ) { //队空搜索结束
v = q.GetFront( ); q.DeQueue ( );
int w = GetFirstNeighbor (v);
while ( w != -1 ) { //若邻接顶点 w 存在
if ( !visited[w] ) { //未访问过
cout << GetValue (w) << ? ?;
visited[w] = 1; q.EnQueue (w);
}
w = GetNextNeighbor (v,w);
} //重复检测 v 的所有邻接顶点
} //外层循环，判队列空否
delete [ ] visited;
}
连通分量 (Connected component)
? 当无向图为非连通图时,从图中某一顶点出
发,利用深度优先搜索算法或广度优先搜索
算法 不可能遍历到图中的所有顶点,只能访
问到该顶点所在的最大连通子图 (连通分量 )
的所有顶点 。
? 若从无向图的每一个连通分量中的一个顶
点出发进行遍历,可求得无向图的所有连
通分量。
? 在算法中,需要对图的每一个顶点进行检
测：若已被访问过，则该顶点一定是落在
图中已求得的连通分量上；若还未被访问，
则从该顶点出发遍历图，可求得图的另一
个连通分量。
? 对于非连通的无向图，所有连通分量的生
成树组成了非连通图的生成森林 。
A
C D E IB
F OG
H
J
NML
K
非连通无向图
A H K
C D E IB
F OG J
NML
非连通图的连通分量
确定连通分量的算法
template <class Type> void Graph <Type>,:
Components ( ) {
int *visited = new int[NumVertices];
for ( int i = 0; i < NumVertices; i++ )
visited[i] = 0; //visited 初始化
for ( i = 0; i < NumVertices; i++ )
if ( !visited[i] ) { //检测顶点是否访问过
DFS ( i,visited ); //未访问,出发访问
OutputNewComponent ( ); //连通分量
}
【 例 】 以深度优先搜索方法从顶点 出发遍
历图,建立深度优先生成森林。
A B C
D E F
G
A
A
B
DE
C
F
G有向图 深度优先生成森林
delete [ ] visited;
}
template<class Type> void Graph <Type>,:
DFS_Forest ( Tree <Type> &T ) {
TreeNode <Type> * rt,* subT;
int *visited = new int[n]; //创建访问数组
for ( int i = 0; i < n; i++ )
visited [i] = 0; //初始化
for ( i = 0; i < n; i++ ) //遍历所有顶点
if ( !visited[i] ) { //顶点 i 未访问过
if ( T.IsEmpty ( ) ) //原为空森林,建根
subT = rt = T.BuildRoot ( GetValue(i) );
//顶点 i 的值成为根 rt 的值
else
subT = T.InsertRightSibling
( subT,GetValue(i) );
//顶点 i 的值成为 subT 右兄弟的值
DFS_Tree ( T,subT,i,visited );
//从顶点 i 出发深度优先遍历,建立以
// subT为根的 T 的子树
}
}
template<class Type> void Graph <Type>,,
DFS_Tree ( Tree<Type> &T,TreeNode
<Type>*RT,int v,int visited [ ] ) {
TreeNode<Type> * p;
visited [v] = 1; //顶点 v 作访问过标志
int w = GetFirstNeighbor (v);
//取顶点 v 的第一个邻接顶点 w
int FirstChild = 1;
//第一个未访问子女应是 v 的左子女
while ( w ) { //邻接顶点 w 存在
if ( ! visited [w] ) {
// w未访问过,将成为 v 的子女
if ( FirstChild ) {
p = T.InsertLeftChild ( RT,GetValue(w) );
// p 插入为 RT 的左子女
FirstChild = 0; //建右兄弟
}
else p = T.InsertRightSibling
( p,GetValue(w) );
// p 插入为 p 的左子女
DFS_Tree ( T,p,w,visited );
//递归建立 w 的以 p 为根的 子树
} //邻接顶点 w 处理完
w = GetNextNeighbor ( v,w );
//取 v 的下一个邻接顶点 w
} //回到 while 判邻接顶点 w 存在
}
重连通分量 (Biconnected Component)
? 在无向连通图 G中,当且仅当删去 G中的顶
点 v及 所有依附于 v的所有边 后,可将图分割
成两个或两个以上的连通分量，则称顶点 v
为 关节点 。
? 没有 关节点 的连通图叫做重连通图。
? 在重连通图上,任何一对顶点之间至少存在
有两条路径,在删去某个顶点及与该顶点相
关联的边时,也不破坏图的连通性。
? 一个连通图 G如果不是重连通图，那么它可
以包括几个重连通分量。
? 在一个无向连通图 G中,重连通分量可以利
用深度优先生成树找到 。
? 在图中各 顶点旁标明的深度优先数,给出进
行深度优先搜索时各顶点访问的次序。
? 深度优先生成树的根是 关节点 的充要条件
是 它至少有两个子女 。
? 其它顶点 u 是 关节点 的充要条件是 它至少
有一个子女 w,从 w 出发,不能通过 w,w
的子孙及一条回边所组成的路径到达 u 的
祖先 。
A
B
C D
E
F
G
H
I J A
B
C D
E
F
G
H
J
A
B
C D
E
F
G
H
JI
I
12
3
4
5
6
7
8
9 10
根有两
个子女
关
节
点
关
节
点
关节点
最小生成树
( minimum cost spanning tree )
? 使用不同的遍历图的方法，可以得到不同
的生成树；从不同的顶点出发，也可能得
到不同的生成树。
? 按照生成树的定义,n 个顶点的连通网络
的生成树有 n 个顶点,n-1 条边。
? 构造最小生成树的准则
? 必须使用且仅使用该网络中的 n-1 条边
来联结网络中的 n 个顶点；
? 不能使用产生回路的边；
? 各边上的权值的总和达到最小。
克鲁斯卡尔 (Kruskal) 算法
? 克鲁斯卡尔算法的基本思想：
设有一个有 n 个顶点的连通网络 N = { V,
E },最初先构造一个只有 n 个顶点,没有边
的非连通图 T = { V,? },图中每个顶点自
成一个连通分量。当在 E 中选到一条具有
最小权值的边时,若该边的两个顶点落在不
同的连通分量上，则将此边加入到 T 中 ; 否
则将此边舍去，重新选择一条权值最小的
边。 如此重复下去,直到所有顶点在同一个
连通分量上为止。
? 算法的框架 利用 最小堆 (MinHeap)和 并查
集 (DisjointSets)来实现 克鲁斯卡尔算法 。
? 首先,利用 最小堆 来存放 E中的所有的边,堆
中每个结点的格式为
? 在构造最小生成树过程中,利用 并查集 的运
算检查依附一条边的两顶点 tail,head是否
在同一连通分量 (即 并查集的同一个子集合 )
上,是则舍去这条边；否则将此边加入 T,
同时将这两个顶点放在同一个连通分量上。
tail head cost
边的两个顶点位置 边的权值
10
? 随着各边逐步加入到最小生成树的边集合中,
各连通分量也在逐步合并,直到形成一个连
通分量为止。
应用克鲁斯卡尔算法构造最小生成树的过程
5
0
4
6
1
3
2
28
10
25
14
24
22
16
18 12
5
0
4
6
1
3
2 5
0
4
6
1
3
2
原图 (a) (b)
10
12
5
0
4
6
1
3
2
28
10
25
14
24
22
16
18 12
5
0
4
6
1
3
2 5
0
4
6
1
3
2
10 14
12
原图 (c) (d)
5
0
4
6
1
3
2
10 14 16
12
(e) (f) (g)
5
0
4
6
1
3
2
10 14
22
16
12
5
0
4
6
1
2
10
25
14
22
16
123
最小生成树类定义
const int MAXNUM = 机器可表示的,问题中
不可能出现的大数
class MinSpanTree;
class MSTEdgeNode { //生成树边结点类
friend class MinSpanTree;
private:
int tail,head; //生成树各边的两顶点
float cost; //生成树各边的权值
public:
MSTEdgeNode ( ) //构造函数
,tail ( -1 ),head ( -1 ),cost ( 0 ) { }
};
class MinSpanTree {
protected:
MSTEdgeNode * edgevalue;
int MaxSize,n;
public:
MinSpanTree ( int sz = NumVertices-1 )
,MaxSize(sz),n (0) {
edgevalue = new MSTEdgeNode[MaxSize];
}
int Insert ( MSTEdgeNode& item );
}
利用克鲁斯卡尔算法建立最小生成树
void Graph<string>,:
Kruskal ( MinSpanTree& T ) {
MSTEdgeNode e; //边结点辅助单元
MinHeap <MSTEdgeNode> H( NumEdges );
int NumVertices = VerticesList.last; //顶点数
UFSets F ( NumVertices ); //并查集
for ( int u = 0; u < NumVertices; u++ )
for ( int v = u +1; v < NumVertices; v++ )
if ( Edge[u][v] != MAXNUM ) {
e.tail = u; e.head = v; //插入堆
e.cost = Edge[u][v]; H.Insert (e);
}
int count = 1; //最小生成树加入边数计数
while ( count < NumVertices ) {
H.RemoveMin ( e ); //从堆中退出一条边
u = F.Find ( e.tail ); //检测两端点的根
v = F.Find ( e.head );
if ( u != v ) { //根不在同一连通分量
F.Union ( u,v ); //合并
T.Insert ( e ); //该边存入最小生成树
count++;
}
}
}
出堆顺序 (0,5,10) 选中 (2,3,12) 选中
(1,6,14)选中 (1,2,16) 选中 (3,6,18) 舍弃
(3,4,22)选中 (4,6,24) 舍弃 (4,5,25) 选中
并查集 邻接矩阵表示
-2
-2
-2
-2
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -10
2-1 -1 -10
-2 2 0
0
0
0
0 1 2 3 4 5 6
-2 1-1
1-2 -1-4 21
-2 -5 1 2 11
-71 1 2 1 1
F 0 1 2 3 4 5 6
0 28 ? ? ? 10 ? 0
28 0 16 ? ? ? 14 1
? 16 0 12 ? ? ? 2
? ? 12 0 22 ? 18 3
? ? ? 22 0 25 24 4
10 ? ? ? 25 0 ? 5
? 14 ? 18 24 ? 0 6
普里姆 (Prim)算法
? 普里姆算法的基本思想：
从连通网络 N = { V,E }中的某一顶点 u0 出
发,选择与它关联的具有最小权值的边 ( u0,
v ),将其顶点加入到 生成树顶点集合 U中。
以后每一步从 一个顶点在 U 中,而 另一个
顶点不在 U 中 的各条边中选择 权值最小的
边 (u,v),把它的顶点加入到 集合 U 中。如
此继续下去,直到网络中的所有顶点都加入
到生成树顶点集合 U 中为止。
? 采用邻接矩阵作为图的存储表示。
2525
10
5
0
4
6
1
3
2
28
10
25
14
24
22
16
18
5
0
4
6
1
3
2 5
0
4
6
1
3
2
10
原图 (a) (b)
5
0
4
6
1
3
2
10
(c) (d) (e) (f)
5
0
4
6
1
3
2
10
22
12
5
0
4
6
1
2
10
25
14
22
16
123
25
22
12
? 在构造过程中, 还设置了两个辅助数组：
? lowcost[ ] 存放 生成树顶点集合内顶点 到
生成树外各顶点 的各边上的当前最小权值；
? nearvex[ ] 记录 生成树顶点集合外各顶点
距离 集合内哪个顶点 最近 (即权值最小 )。
? 例子
5
0
4
6
1
3
2
28
10
25
14
24
22
16
18 12
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
????
???
???
????
???
????
0241814
02510
2425022
1822012
12016
1416028
10280
? 若选择从顶点 0出发，即 u0 = 0，则两个辅
助数组的初始状态为：
? 然后反复做以下工作：
? 在 lowcost [ ]中选择 nearvex[i] ? -1 &&
lowcost[i]最小 的边,用 v 标记它。则选中
的权值最小的边为 (nearvex[v],v),相应的
权值为 lowcost[v]。
0 28 ? ? ? 10 ?
-1 0 0 0 0 0 0
lowcost
nearvex
0 1 2 3 4 5 6
? 将 nearvex[v] 改为 -1,表示它已加入生
成树顶点集合。
? 将边 (nearvex[v],v,lowcost[v] ) 加入生
成树的边集合。
? 取 lowcost[i] = min{ lowcost[i],
Edge[v][i] },即用 生成树顶点集合外各
顶点 i 到刚加入该集合的新顶点 v 的距
离 Edge[v][i] 与 原来它们到生成树顶点
集合中顶点的最短距离 lowcost[i] 做比较,
取距离近的作为这些集合外顶点到生成
树顶点集合内顶点的最短距离。
? 如果 生成树顶点集合外顶点 i 到 刚加入
该集合的新顶点 v 的距离比原来它到生
成树顶点集合中顶点的最短距离还要近，
则修改 nearvex[i], nearvex[i] = v。表示
生成树外顶点 i到生成树内顶点 v当前距
离最近。
0 28 ? ? ? 10 ?
-1 0 0 0 0 0 0
lowcost
nearvex
0 1 2 3 4 5 6
选 v=5 选边 (0,5)
顶点 v=5加入生成树顶点集合：
0 28 ? ? 25 10 ?
-1 0 0 0 5 -1 0
lowcost
nearvex
0 1 2 3 4 5 6
选 v=4 选边 (5,4)
5
0
4
6
1
3
2
28
10
25
14
24
22
16
18
原图 边 (0,5,10) 加入生成树
12
0
4
6
1
3
2
10
25
5
0 1 2 3 4 5 6
顶点 v=4加入生成树顶点集合：
0 28 ? 22 25 10 24
-1 0 0 4 -1 -1 4
lowcost
nearvex
选 v=3 选边 (4,3)
5
0
4
6
1
3
2
28
10
25
14
24
22
16
18
原图 边 (5,4,25) 加入生成树
12
5
0
4
6
1
3
2
10
25
22
顶点 v=3加入生成树顶点集合：
0 28 12 22 25 10 18
-1 0 3 -1 -1 -1 3
lowcost
nearvex
0 1 2 3 4 5 6
选 v=2 选边 (3,2)
5
0
4
6
1
3
2
28
10
25
14
24
22
16
18
原图 边 (4,3,22) 加入生成树
12
5
0
4
6
1
3
2
10
25
22
12
lowcost
nearvex
0 1 2 3 4 5 6
顶点 v=2加入生成树顶点集合：
0 16 12 22 25 10 18
-1 2 -1 -1 -1 -1 3
选 v=1 选边 (2,1)
5
0
4
6
1
3
2
28
10
25
14
24
22
16
18
原图 边 (3,2,12) 加入生成树
12
5
0
4
1
3
2
10
25
22
16
12
顶点 v=1加入生成树顶点集合：
0 16 12 22 25 10 14
-1 -1 -1 -1 -1 -1 1
lowcost
nearvex
0 1 2 3 4 5 6
选 v=6 选边 (1,6)
5
0
4
6
1
3
2
28
10
25
14
24
22
16
18
原图 边 (2,1,16) 加入生成树
12
5
0
4
6
1
3
2
10
25
14
22
16
12
lowcost
nearvex
0 1 2 3 4 5 6
顶点 v=6加入生成树顶点集合：
0 16 12 22 25 10 14
-1 -1 -1 -1 -1 -1 -1
5
0
4
6
1
3
2
28
10
25
14
24
22
16
18
原图 边 (1,6,14) 加入生成树
12
5
0
4
6
1
3
2
10
25
14
22
16
12
最后生成树中边集合里存入得各条边为,
(0,5,10),(5,4,25),(4,3,22),
(3,2,12),(2,1,16),(1,6,14)
利用普里姆算法建立最小生成树
void Graph<string>,:
Prim ( MinSpanTree &T ) {
int NumVertices = VerticesList.last; //顶点数
float * lowcost = new float[NumVertices];
int * nearvex = new int[NumVertices];
for ( int i = 1; i < NumVertices; i++ ) {
lowcost[i] = Edge[0][i]; //顶点 0到各边代价
nearvex[i] = 0; //及最短带权路径
}
nearvex[0] = -1; //加到生成树顶点集合
MSTEdgeNode e; //最小生成树结点单元
for ( i = 1; i < NumVertices; i++ ) {
//循环 n-1次,加入 n-1条边
float min = MAXNUM; int v = 0;
for ( int j = 0; j < NumVertices; j++ )
if ( nearvex[j] != -1 && lowcost[j] < min )
{ v = j; min = lowcost[j]; }
//求生成树外顶点到生成树内顶点具有最
//小权值的边,v是 当前具最小权值的边
if ( v ) { //v=0表示再也找不到要求顶点
e.tail = nearvex[v]; e.head = v;
e.cost = lowcost[v];
T.Insert (e); //选出的边加入生成树
nearvex[v] = -1; //该边加入生成树标记
for ( j = 1; j < NumVertices; j++ )
if ( nearvex[j] != -1 &&
Edge[v][j] < lowcost[j] ) {
lowcost[j] = Edge[v][j]; //需要修改
nearvex[j] = v;
}
}
} //循环 n-1次,加入 n-1条边
}
? 分析以上算法,设连通网络有 n 个顶点,则
该算法的时间复杂度为 O(n2),它适用于边
稠密的网络。
最短路径 (Shortest Path)
? 最短路径问题,如果从图中某一顶点 (称为
源点 )到达另一顶点 (称为终点 )的路径可能
不止一条，如何找到一条路径使得沿此路
径上各边上的权值总和达到最小。
? 问题解法
? 边上权值非负情形的单源最短路径问题
— Dijkstra算法 ? (仅讲此算法 )
? 边上权值为任意值的单源最短路径问题
— Bellman和 Ford算法 ? (不讲 )
? 所有顶点之间的最短路径
— Floyd算法 ? (不讲 )
边上权值非负情形的单源最短路径问题
? 问题的提法,给定一个带权有向图 D与源
点 v，求从 v 到 D中其它顶点的最短路径。
限定各边上的权值大于或等于 0。
? 为求得这些最短路径,Dijkstra提出按路径
长度的递增次序,逐步产生最短路径的算
法。首先求出长度最短的一条最短路径，
再参照它求出长度次短的一条最短路径，
依次类推，直到从顶点 v到其它各顶点的最
短路径全部求出为止。
? 举例说明
Dijkstra逐步求解的过程
1
0
4
32
10 100
30
50
20
60
10
源点 终点 最短路径 路径长度
v0 v1 (v0,v1) 10
v2 (v0,v1,v2) (v0,v3,v2) ?,60,50
v3 (v0,v3) 30
v4 (v0,v4) (v0,v3,v4) (v0,v3,v2,v4) 100,90,60
? 引入辅助数组 dist。它的每一个分量 dist[i]表
示当前找到的从 源点 v0到 终点 vi 的最短路径
的长度。初始状态：
? 若从源点 v0到顶点 vi 有边,则 dist[i]为该边
上的权值；
? 若从源点 v0到顶点 vi 无边,则 dist[i]为 ?。
? 假设 S 是已求得的最短路径的终点的集合，
则可证明,下一条最短路径必然是从 v0 出发，
中间只经过 S 中的顶点便可到达的那些顶点
vx (vx?V-S )的路径中的一条。
? 每次求得一条最短路径后,其终点 vk加入集合
S，然后 对所有的 vi?V-S，修改其 dist[i]值 。
Dijkstra算法可描述如下：
① 初始化,S ← { v0 };
dist[j] ← Edge[0][j],j = 1,2,…,n-1;
// n为图中顶点个数
② 求出最短路径的长度：
dist[k] ← min { dist[ i] },i ? V- S ;
S ← S U { k };
③ 修改：
dist[i] ← min{ dist[ i],dist[k] + Edge[k][i] },
对于每一个 i ? V- S ;
④ 判断：若 S = V,则算法结束，否则转 ② 。
用于计算最短路径的图邻接矩阵类
const int NumVertices = 6; //图最大顶点个数
class Graph { //图的类定义
private:
float Edge[NumVertices][NumVertices];
float dist[NumVertices]; //最短路径长度数组
int path[NumVertices]; //最短路径数组
int S[NumVertices]; //最短路径顶点集
public:
void ShortestPath ( int,int );
int choose ( int );
};
计算从单个顶点到其它各顶点最短路径
void Graph,,ShortestPath ( int n,int v ){
//Graph是一个具有 n 个顶点的带权有向图,各
//边上的权值由 Edge[i][j]给出。本算法建立起
//一个数组, dist[j],0? j<n,是当前求到的从顶
//点 v 到顶点 j 的最短路径长度,同时用数组
//path[j],0? j<n,存放求到的最短路径 。
for ( int i = 0; i < n; i++) {
dist[i] = Edge[v][i]; //dist数组初始化
S[i] = 0;
if ( i != v && dist[i] < MAXNUM)
path[i] = v;
else path[i] = -1; //path数组初始化
}
S[v] = 1; dist[v] = 0; //顶点 v加入顶点集合
//选当前不在集合 S中具有最短路径的顶点 u
for ( i = 0; i < n-1; i++ ) {
float min = MAXNUM; int u = v;
for ( int j = 0; j < n; j++ )
if ( !S[j] && dist[j] < min )
{ u = j; min = dist[j]; }
S[u] = 1; //将顶点 u加入集合 S
for ( int w = 0; w < n; w++ ) //修改
if ( !S[w] && Edge[u][w] < MAXNUM
&& dist[u] + Edge[u][w] < dist[w] ) {
//顶点 w未加入 S,且绕过 u可以缩短路径
dist[w] = dist[u] + Edge[u][w];
path[w] = u; //修改到 w的最短路径
}
}
}
Dijkstra算法中各辅助数组的最终结果
从表中读取源点 0到终点 v的最
短路径的方法, 举顶点 4为例
path[4] = 2 path[2] = 3
path[3] = 0,反过来排列，得
到路径 0,3,2,4,这就是源点 0
到终点 4的最短路径。
0
41
2 3
10
50 10
20
60
30
100
序号 顶点 1 顶点 2 顶点 3 顶点 4
Dist 10 50 30 60
path 0 3 0 2
活动网络 (Activity Network)
? 计划、施工过程、生产流程、程序流程等都
是, 工程,。除了很小的工程外，一般都把
工程分为若干个叫做,活动,的子工程。完
成了这些活动，这个工程就可以完成了。
? 例如，计算机专业学生的学习就是一个工程，
每一门课程的学习就是整个工程的一些活动。
其中有些课程要求先修课程，有些则不要求。
这样在有的课程之间有领先关系，有的课程
可以并行地学习。
用顶点表示活动的网络 (AOV网络 )
C1 高等数学
C2 程序设计基础
C3 离散数学 C1,C2
C4 数据结构 C3,C2
C5 高级语言程序设计 C2
C6 编译方法 C5,C4
C7 操作系统 C4,C9
C8 普通物理 C1
C9 计算机原理 C8
学生课程学习工程图
C8
C3
C5
C4
C9
C6
C7C1
C2
? 可以用 有向图 表示一个工程。在这种有向
图中,用顶点表示活动, 用有向边 <Vi,Vj>
表示 活动 Vi 必须先于活动 Vj进行 。这种有
向图叫做顶点表示活动的 AOV网络
(Activity On Vertices)。
? 在 AOV网络中不能出现有向回路,即有向
环。如果出现了有向环，则意味着某项活
动应以自己作为先决条件。
? 因此，对给定的 AOV网络，必须先判断它
是否存在有向环。
? 检测有向环的一种方法是对 AOV网络构造
它的拓扑有序序列。即将各个顶点 (代表各
个活动 )排列成一个线性有序的序列，使得
AOV网络中所有应存在的前驱和后继关系
都能得到满足。
? 这种 构造 AOV网络全部顶点的拓扑有序序
列的运算就叫做拓扑排序。
? 如果通过拓扑排序能将 AOV网络的所有顶
点都排入一个拓扑有序的序列中,则该网络
中必定不会出现有向环。
? 如果 AOV网络中存在有向环，此 AOV网络
所代表的工程是不可行的。
? 例如,对学生选课工程图进行拓扑排序,得
到的拓扑有序序列为
C1,C2,C3,C4,C5,C6,C8,C9,C7
或 C1,C8,C9,C2,C5,C3,C4,C7,C6
C8
C3
C5
C4
C9
C6
C7C1
C2
进行拓扑排序的方法
① 输入 AOV网络。令 n 为顶点个数。
② 在 AOV网络中选一个 没有直接前驱 的顶点,
并输出之 ;
③ 从图中删去该顶点,同时删去所有它发出
的有向边 ;
④ 重复以上 ②, ③ 步,直到
?全部顶点均已输出,拓扑有序序列形成，
拓扑排序完成；或
?图中还有未输出的顶点,但已跳出处理
循环 。说明图中还剩下一些顶点,它们都
有直接前驱。这时网络中必存在有向环。
C0 C1 C2
C3 C4 C5
拓扑排序的过程
(a) 有向无环图
C2
C5
C1C0
C3
(b) 输出顶点 C4
C1 C2
C5C3
(c) 输出顶点 C0
C4
C0 C2
C5
C1
C3
(d) 输出顶点 C3
C1 C2
C5
(e) 输出顶点 C2
C5
C1
(f) 输出顶点 C1
C5
(g) 输出顶点 C5
最后得到的拓扑有序序列为 C4,C0,C3,C2,
C1,C5 。它满足图中给出的所有前驱和后继关系，
对于本来没有这种关系的顶点，如 C4和 C2，也
排出了先后次序关系。
(h) 拓扑排序完成
AOV网络及其邻接表表示
C0 C1 C2
C3 C4 C5
C0
C1
C2
C3 0
C4
C5 0
0
1
2
3
4
5
count data adj
1
3
0
1
0
3
1
dest link
3 0
5
1 5 0
0 1 5 0
? 在邻接表中增设一个数组 count[ ],记录各
顶点入度 。 入度为零的顶点即无前驱顶点 。
? 在输入数据前,顶点表 NodeTable[ ]和入度数
组 count[ ]全部初始化 。 在输入数据时,每输
入一条边 <j,k>,就需要建立一个边结点,并
将它链入相应边链表中,统计入度信息：
Edge<int> * p = new Edge<int> (k);
//建立边结点,dest 域赋为 k
p->link = NodeTable[j].adj;
NodeTable[j].adj = p;
//链入顶点 j 的边链表的前端
count[k]++; //顶点 k 入度加一
? 在算法中,使用一个存放入度为零的顶点的
链式栈,供选择和输出无前驱的顶点。
? 拓扑排序算法可描述如下：
? 建立入度为零的顶点栈 ;
? 当入度为零的顶点栈不空时,重复执行
? 从顶点栈中退出一个顶点,并输出之 ;
? 从 AOV网络中删去这个顶点和它发出
的边,边的终顶点入度减一 ;
? 如果边的终顶点入度减至 0,则该顶点
进入度为零的顶点栈 ;
? 如果输出顶点个数少于 AOV网络的顶点
个数,则报告网络中存在有向环。
? 在算法实现时,为了建立入度为零的顶点栈,
可以不另外分配存储空间,直接利用入度为
零的顶点的 count[ ]数组元素。设立一个栈
顶指针 top,指示当前栈顶位置,即某一个入
度为零的顶点。栈初始化时置 top = -1。
? 将 顶点 i 进栈时执行以下指针的修改：
count[i] = top; top = i ;
// top指向新栈顶 i,原栈顶元素在 count[i]中
? 退栈操作可以写成：
j = top; top = count[top];
//位于栈顶的顶点记于 j,top退到次栈顶
拓扑排序时入度
为零的顶点栈在
count[]中的变化
C0 C1 C2
C3 C4 C5
1
3
0
1
0
3
1
3
-1
1
2
3
2
2
-1
1
2
2
2
1
-1
2
2
2
0
1
2
3
4
5
0
1
2
3
4
5
0
1
2
3
4
5
0
1
2
3
4
5
top top
top
top
建栈
top
top
顶点 4
出栈
top
top
顶点 0
出栈
拓扑排序时入度
为零的顶点栈在
count[]中的变化
C0 C1 C2
C3 C4 C5
2
1
-1
2
2
2
2
-1
-1
2
2
1
2
-1
-1
2
2
-1
2
-1
-1
2
2
-1
0
1
2
3
4
5
0
1
2
3
4
5
0
1
2
3
4
5
0
1
2
3
4
5
top
top
top
top
top顶点 1出栈
top
顶点 5
出栈
顶点 3
出栈
顶点 2
出栈
class Graph { //图的邻接表的类定义
friend class <int> Vertex;
friend class <int> Edge;
private:
Vertex<int> * NodeTable; //顶点表数组
int *count; //入度数组兼栈
int n; //顶点个数
public:
Graph ( const int vertices = 0 ), n ( vertices ) {
NodeTable = new vertex <int> [n];
count = new int[n];
};
void TopologicalOrder ( );
}
拓扑排序的算法
void Graph,,TopologicalSort ( ) {
int top = -1; //入度为零的顶点栈初始化
for ( int i = 0; i < n; i++ ) //入度为零顶点
if ( count[i] == 0 ) //进栈
{ count[i] = top; top = i; }
for ( i = 0; i < n; i++ ) //期望输出 n个顶点
if ( top == -1 ) { //中途栈空,转出
cout <<,网络中有回路 ！ " << endl;
return;
}
else { //继续拓扑排序
int j = top; top = count[top]; //退栈
cout << j << endl; //输出
Edge<float> * p = NodeTable[j].adj;
while ( p != NULL ) { //扫描出边表
int k = p->dest; //另一顶点
if ( --count[k] == 0 ) //顶点入度减一
{ count[k] = top; top = k; }
//顶点的入度 减至零,进栈
p = p->link;
}
}
}
用边表示活动的网络 (AOE网络 )
? 如果在 无有向环的带权有向图 中,用有向边
表示一个工程中的活动 (Activity),用边上权
值表示活动持续时间 (Duration),用顶点表
示事件 (Event),则这样的有向图叫做用边
表示活动的网络,简称 AOE ( Activity On
Edges ) 网络。
? AOE网络在某些工程估算方面非常有用。
例如，可以使人们了解：
? 完成整个工程至少需要多少时间 (假设网
络中没有环 )?
? 为缩短完成工程所需的时间,应当加快哪
些活动?
? 从源点到各个顶点,以至从源点到汇点的有
向路径可能不止一条。 这些路径的长度也
可能不同。 完成不同路径的活动所需的时
间虽然不同,但只有各条路径上所有活动都
完成了,整个工程才算完成。
? 因此,完成整个工程所需的时间取决于从源
点到汇点的最长路径长度,即在这条路径上
所有活动的持续时间之和。 这条路径长度最
长的路径就叫做关键路径 (Critical Path)。
a9=6
1
3
2
4
a1=8
a2=12
5
6
7 8a10=12
a8=18
a5=28
a6=8
a7=6
a3=14
a4=10
? 要找出关键路径，必须找出 关键活动,即不
按期完成就会影响整个工程完成的活动。
? 关键路径上的所有活动都是关键活动 。因
此,只要找到了关键活动,就可以找到关键
路径。例如,下图就是一个 AOE网。
定义几个与计算关键活动有关的量：
① 事件 Vi 的最早可能开始时间 Ve(i)
是从 源点 V0到 顶点 Vi的最长路径长度 。
② 事件 Vi的最迟允许开始时间 Vl[i]
是在保证汇点 Vn-1 在 Ve[n-1] 时刻完成的前
提下, 事件 Vi 的允许的最迟开始时间 。
③ 活动 ak的最早可能开始时间 e[k]
设活动 ak 在边 < Vi,Vj >上,则 e[k]是从源点
V0到顶点 Vi 的最长路径长度 。 因此,
e[k] = Ve[i]。
④ 活动 ak的最迟允许开始时间 l[k]
l[k]是在不会引起时间延误的前提下,该活
动允许的最迟开始时间。
l[k] = Vl[j] - dur(<i,j>)。
其中,dur(<i,j>)是完成 ak 所需的时间。
⑤ 时间余量 l[k] - e[k]
表示活动 ak 的最早可能开始时间和最迟允
许开始时间的时间余量。 l[k] == e[k] 表示活
动 ak 是没有时间余量的关键活动。
? 为找出关键活动,需要求各个活动的 e[k] 与
l[k]，以判别是否 l[k] == e[k]。
? 为求得 e[k]与 l[k],需要先求得从源点 V0 到
各个顶点 Vi 的 Ve[i] 和 Vl[i]。
? 求 Ve[i]的递推公式
? 从 Ve[0] = 0 开始，向前递推
< Vj,Vi > ? S2,i = 1,2,?,n-1
S2 是所有指向 Vi 的有向边 < Vj,Vi >的集合。
? 从 Vl[n-1] = Ve[n-1]开始，反向递推
< Vi,Vj > ? S1,i = n-2,n-3,?,0
S1是所有源自 Vi的有向边 < Vi,Vj >的集合。
},),(][ {][ ???? ij
j
VVdu rjVem axiVe
},),(][ {][ ???? ji
j
VVdu rjVlm i niVl
? 这两个递推公式的计算必须分别在 拓扑有序
及 逆拓扑有序 的前提下进行。
? 设 活动 ak(k=1,2,…,e)在带权有向边 < Vi,Vj >
上,其持续时间用 dur (<Vi,Vj >) 表示,则有
e[k] = Ve[i]；
l[k] = Vl[j] - dur(<Vi,Vj >)； k = 1,2,…,e。
这样就得到计算关键路径的算法。
? 为了简化算法,假定在求关键路径之前已经
对各顶点实现了拓扑排序,并按拓扑有序的
顺序对各顶点重新进行了编号。
1
3
2
4
a1=8
a2=12
5
6
7 8a10=12
a9=6
a8=18
a5=28
a6=8
a7=6
a3=14
a4=10
Ve
Vl
1 2 3 4 5 6 7 8
0 8 12 22 28 40 46 58
0 8 12 22 28 40 46 58
e
l
0 0 8 12 12 22 22 28 40 46
0 0 8 12 12 32 22 28 40 46
1 2 3 4 5 6 7 8 9 10
利用关键路径法求 AOE网的各关键活动
void graph,,CriticalPath ( ) {
//在此算法中需要在邻接表中单链表的结点内
//增加一个 int型 cost域,记录该边上的权值。
int i,j; int p,k; float e,l;
float * Ve = new float[n];
float * Vl = new float[n];
for ( i = 0; i < n; i++ ) Ve[i] = 0;
for ( i = 0; i < n; i++ ) { //顺向计算 Ve[ ]
Edge<float> *p = NodeTable[i].adj;
while ( p != NULL ) {
k = p->dest;
if ( Ve[i] + p->cost > Ve[k] )
Ve[k] = Ve[i] + p->cost;
p = p->link;
}
}
Vl[n-1] = Ve[n-1];
for ( i = n-2; i > 0; i-- ) { //逆向计算 Vl[ ]
p = NodeTable[i].adj;
while ( p != NULL ) {
k = p->dest;
if ( Vl[k] - p->cost < Vl[i])
Vl[i] = Vl[k] - p->cost;
p = p->link;
}
}
for ( i = 0; i < n; i++ ) { //求各活动的 e,l
p = NodeTable[i].adj;
while ( p != NULL ) {
k = p->dest;
e = Ve[i]; l = Vl[k] - p->cost;
if ( l == e ) cout << "<" << i << "," << k
<<,>” <<,是关键活动, << endl;
p = p->link;
}
}
}
注意
?所有顶点按拓扑有序的次序编号
?仅计算 Ve [i] 和 Vl[i] 是不够的，还须计算
e[k] 和 l[k]。
?不是任一关键活动加速一定能使整个工程
提前。
?想使整个工程提前，要考虑各个关键路径
上所有关键活动。
? 图的存储表示
? 图的遍历与连通性
? 最小生成树
? 最短路径
? 活动网络
图的基本概念
? 图定义 图是由顶点集合 (vertex)及顶点间
的关系集合组成的一种数据结构,
Graph＝ ( V,E )
其中 V = { x | x ? 某个数据对象 }
是顶点的有穷非空集合；
E = {(x,y) | x,y ? V }
或 E = {<x,y> | x,y ? V && Path (x,y)}
是顶点之间关系的有穷集合，也叫做边
(edge)集合。 Path (x,y)表示从 x 到 y 的一
条单向通路,它是有方向的。
? 有向图与无向图 在有向图中，顶点对 <x,
y> 是有序的。在无向图中，顶点对 (x,y)是
无序的。
? 完全图 若有 n 个顶点的无向图有 n(n-1)/2
条边,则此图为完全无向图。有 n 个顶点
的有向图有 n(n-1) 条边,则此图为完全有向
图。
0 0 0 0
1
1
1 12 2
2 265433
? 邻接顶点 如果 (u,v) 是 E(G) 中的一条边，
则称 u 与 v 互为邻接顶点 。
? 子图 设有两个图 G＝ (V,E) 和 G‘＝ (V’,
E‘)。若 V’? V 且 E‘?E,则称 图 G’ 是 图 G
的子图。
? 权 某些图的边具有与它相关的数,称之为
权。这种带权图叫做网络。
0
1 2
3
子图 0
1
3
0
1 2
3
0
2
3
? 顶点的度 一个顶点 v的度是与它相关联的
边的条数。记作 TD(v)。 在有向图中,顶点
的度等于该顶点的入度与出度之和。
? 顶点 v 的入度 是以 v 为终点的有向边的条
数,记作 ID(v); 顶点 v 的出度 是以 v 为始点
的有向边的条数,记作 OD(v)。
? 路径 在图 G＝ (V,E) 中,若从顶点 vi 出发,
沿一些边经过一些顶点 vp1,vp2,…,vpm，到
达顶点 vj。则称顶点序列 (vi vp1 vp2,.,vpm vj)
为从顶点 vi 到顶点 vj 的路径 。它经过的边
(vi,vp1),(vp1,vp2),...,(vpm,vj) 应是属于 E
的边。
? 路径长度 非带权图的路径长度是指此路径
上边的条数。带权图的路径长度是指路径
上各边的权之和。
? 简单路径 若路径上各顶点 v1,v2,...,vm 均不
互相重复,则称这样的路径为简单路径。
? 回路 若路径上第一个顶点 v1 与最后一个
顶点 vm 重合,则称这样的路径为回路或环。
0
1 2
3
0
1 2
3
0
1 2
3
? 连通图与连通分量 在无向图中,若从顶点
v1到顶点 v2有路径,则称顶点 v1与 v2是连通
的。如果图中任意一对顶点都是连通的,则
称此图是连通图。非连通图的极大连通子
图叫做连通分量。
? 强连通图与强连通分量 在有向图中,若对
于每一对顶点 vi和 vj,都存在一条从 vi到 vj和
从 vj到 vi的路径,则称此图是强连通图。非
强连通图的极大强连通子图叫做强连通分
量。
? 生成树 一个连通图的生成树是其极小连
通子图，在 n个顶点的情形下，有 n-1条边。
图的抽象数据类型
class Graph {
public:
Graph ( );
void InsertVertex ( Type & vertex );
void InsertEdge ( int v1,int v2,int weight );
void RemoveVertex ( int v );
void RemoveEdge ( int v1,int v2 );
int IsEmpty ( );
Type GetWeight ( int v1,int v2 );
int GetFirstNeighbor ( int v );
int GetNextNeighbor ( int v1,int v2 );
}
图的存储表示
? 在图的邻接矩阵表示中，有一个 记录各个
顶点信息 的 顶点表, 还有一个 表示各个顶
点之间关系 的 邻接矩阵 。
? 设图 A = (V,E)是一个有 n 个顶点的图,图
的邻接矩阵是一个二维数组 A.edge[n][n]，
定义：
邻接矩阵 (Adjacency Matrix)
?
?
? ??
?
,
),(,,
]][[,
否则
或者如果
0
><1
A
EjiEji
jiE d g e
? 无向图的邻接矩阵是对称的 ;
? 有向图的邻接矩阵可能是不对称的。
0
1 2
3 ??
?
?
?
?
?
?
?
?
?
0101
1010
0101
1010
A, e d g e
0
1
2
?
?
?
?
?
?
?
?
?
000
101
010
A, ed g e
? 在有向图中,统计第 i 行 1 的个数可得顶点
i 的 出度,统计第 j 行 1 的个数可得顶点 j
的 入度 。
? 在无向图中,统计第 i 行 (列 ) 1 的个数可得
顶点 i的 度 。
网络的邻接矩阵
??
?
?
?
??
??????
?????
?
ji
ji,ji,ji
ji,ji,jiji
ji
若
或且若
或且若
,
)(,
)(),,(
]][[
0
EE
EEW
A,e d ge
8
6
3
1
29 5
4
2
0
3
1
?
?
?
?
?
?
?
?
?
?
??
?
?
?
06
8053
290
410
A,e d g e
用邻接矩阵表示的图的类的定义
const int MaxEdges = 50;
const int MaxVertices = 10;
template <class Type>
class Graph {
private:
SeqList<Type> VerticesList (MaxVertices);
float Edge[MaxVertices][MaxVertices];
int CurrentEdges;
int FindVertex (SeqList <Type> & L;
const Type vertex){ return L.Find (vertex); }
int GetVertexPos ( int vertex )
{ return FindVertex (VerticesList,vertex); }
public:
Graph ( int sz = MaxEdges );
int GraphEmpty ( )
const { return VerticesList.IsEmpty ( ); }
int GraphFull( )
const { return VerticesList.IsFull( ) ||
CurrentEdges == MaxEdges; }
int NumberOfVertices ( )
{ return VerticesList.last +1; }
int NumberOfEdges ( )
{ return CurrentEdges; }
Type GetValue ( int i )
{ return i >= 0 && i <= VerticesList.last
VerticesList.data[i], NULL; }
DistType GetWeight ( int v1,int v2 );
int GetFirstNeighbor ( int v );
int GetNextNeighbor ( int v1,int v2 );
void InsertVertex ( const Type vertex );
void InsertEdge
( int v1,int v2,float weight );
void RemoveVertex ( int v );
void RemoveEdge ( int v1,int v2 );
}
邻接矩阵实现的部分图操作
template <class Type> Graph <Type>,:
Graph ( int sz ) { //构造函数
for ( int i = 0; i < sz; i++ )
for ( int j = 0; j < sz; j++ ) Edge[i][j] = 0;
CurrentEdges = 0;
}
template <class Type> folat Graph<Type>,:
GetWeight( int v1,int v2 ) {
//给出以顶点 v1 和 v2 为两端点的边上的权值
if (v1 != -1 && v2 != -1) return Edge[v1][v2];
else return 0;
}
template <class Type> int Graph <Type>::
GetFirstNeighbor ( const int v ) {
//给出顶点位置为 v 的第一个邻接顶点的位置
if ( v != -1 ) {
for ( int col = 0; col <= VerticesList.last;
col++ )
if ( Edge[v][col] > 0 &&
Edge[v][col] < MaxValue ) return col;
}
else return -1;
}
template <class Type> int Graph<Type>,:
GetNextNeighbor ( int v,int w ) {
//给出顶点 v的某邻接顶点 w的下一个邻接顶点
int col;
if ( v != -1 && w != -1 ) {
for ( col = w+1; col <= VerticesList.last;
col++ )
if ( Edge[v][col] > 0 &&
Edge[v][col] < MaxValue ) return col;
}
return -1;
}
邻接表 (Adjacency List)
? 无向图的邻接表
同一个顶点发出的边链接在同一个边链表
中，每一个链结点代表一条边 (边结点 ),结
点中有另一顶点的下标 dest 和指针 link。
A
B C
D
data adj
A
B
C
D
0
1
2
3
dest link dest link
?
?
?
?
1 3
0 2
1
0
? 有向图的邻接表和逆邻接表
A
B
C
data adj
A
B
C
0
1
2
dest link
dest link
?
邻接表 (出边表 )
data adj
A
B
C
0
1
2
dest link
逆邻接表 (入边表 )
1
0 2
?
?
?
?
?
0
1
1
? 网络 (带权图 ) 的邻接表
B
A
C
D6
95 2
8
data adj
A
B
C
D
0
1
2
3
dest cost link
?
?
?
?1 5 3 6
2 8
3 2
1 9
(出边表 )(顶点表 )
? 带权图的边结点中保存该边上的权值 cost。
? 顶点 i 的边链表的表头指针 adj 在顶点表的
下标为 i 的顶点记录中，该记录还保存了该
顶点的其它信息。
? 在邻接表的边链表中,各个边结点的链入
顺序任意，视边结点输入次序而定。
? 设图中有 n 个顶点,e 条边，则 用邻接表表
示无向图时,需要 n 个顶点结点,2e 个边
结点；用 邻接表表示有向图时,若不考虑
逆邻接表，只需 n 个顶点结点,e 个边结点。
邻接表表示的图的类定义
#define DefaultSize 10
template <class Type> class Graph;
template <class Type> struct Edge { //边结点
friend class Graph<Type>;
int dest; //目标顶点下标
float cost; //边上的权值
Edge<Type> * link; //下一边链接指针
Edge ( ) { } //构造函数
Edge ( int D,Type C ),
dest (D),cost (C),link (NULL) { }
int operator != ( Edge<Type>& E )
const { return dest != E.dest; }
}
template <class Type> struct Vertex { //顶点
friend class Graph <Type>;
NemeType data; //顶点数据
Edge<DistType> *adj; //边链表头指针
}
template <class Type> class Graph { //图类
private:
Vertex<Type> * NodeTable; //顶点表
int NumVertices; //当前顶点个数
int MaxVertices; //最大顶点个数
int NumEdges; //当前边数
int GetVertexPos ( const Type vertex );
public:
Graph ( int sz );
~Graph ( );
int GraphEmpty ( )
const { return NumVertices == 0; }
int GraphFull ( ) const
{ return NumVertices == MaxVertices; }
NameType GetValue ( int i )
{ return i >= 0 && i < NumVertices?
NodeTable[i].data, NULL; }
int NumberOfVertices ( )
{ return NumVertices; }
int NumberOfEdges ( ) { return NumEdges; }
void InsertVertex ( Type vertex );
void RemoveVertex ( int v );
void InsertEdge ( int v1,int v2,float weight );
void RemoveEdge ( int v1,int v2 );
float GetWeight ( int v1,int v2 );
int GetFirstNeighbor ( int v );
int GetNextNeighbor ( int v,int w );
}
邻接表的构造函数和析构函数
template <class Type> Graph <Type>,:
Graph ( int sz = DefaultSize ), NumVertices (0),
MaxVertices (sz),NumEdges (0){
int n,e,k,j; Type name,tail,head;
float weight;
NodeTable = //创建顶点表
new Vertex<Type>[MaxVertices];
cin >> n; //输入顶点个数
for ( int i = 0; i < n; i++) //输入各顶点信息
{ cin >> name; InsertVertex ( name ); }
cin >> e; //输入边条数
for ( i = 0; i < e; i++) { //逐条边输入
cin >> tail >> head >> weight;
k = GetVertexPos ( tail );
j = GetVertexPos ( head );
InsertEdge ( k,j,weight ); //插入边
}
}
template <class Type> Graph <Type>,,
~Graph ( ) {
for ( int i = 0; i < NumVertices; i++ ) {
Edge<Type> *p = NodeTable[i].adj;
while ( p != NULL ) { //逐条边释放
NodeTable[i].adj = p->link;
delete p;
p = NodeTable[i].adj;
}
}
delete [ ] NodeTable; //释放顶点表
}
邻接表部分成员函数的实现
template <class Type> int Graph <Type>,:
GetVertexPos ( const Type vertex ) {
//根据顶点名 vertex查找它在邻接表中位置
for ( int i = 0; i < NumVertices; i++ )
if ( NodeTable[i].data == vertex ) return i;
return -1;
}
template <Class Type> int Graph <Type>,:
GetFirstNeighbor ( int v ) {
//查找顶点 v 第一个邻接顶点在邻接表中位置
if ( v != -1 ) { //若顶点存在
Edge<Type> * p = NodeTable[v].adj;
if ( p != NULL ) return p->dest;
}
return -1; //若顶点不存在
}
template <Class Type> int Graph <Type>,,
GetNextNeighbor ( int v,int w ) {
//查找顶点 v 在邻接顶点 w 后下一个邻接顶点
if ( v != -1 ) {
Edge<Type> * p = NodeTable[v1].adj;
while ( p != NULL ) {
if ( p->dest == w && p->link != NULL )
return p->link->dest;
//返回下一个邻接顶点在邻接表中位置
else p = p->link;
}
}
return -1; //没有查到下一个邻接顶点
}
template <Class Type> float Graph <Type>,:
GetWeight ( int v1,int v2) {
//取两端点为 v1 和 v2 的边上的权值
if ( v1 != -1 && v2 != -1 ) {
Edge<Type> * p = NodeTable[v1].adj;
while ( p != NULL ) {
if ( p->dest == v2 ) return p->cost;
else p = p->link;
}
}
return 0;
}
邻接多重表 (Adjacency Multilist)
? 在邻接多重表中,每一条边只有一个边结点。
为有关边的处理提供了方便。
? 无向图的情形
? 边结点的结构
mark vertex1 vertex2 path1 path2
其中,mark 是记录是否处理过的标记 ; vertex1
和 vertex2是该边两顶点位置。 path1域是链接
指针,指向下一条依附顶点 vertex1的边； path2
是指向下一条依附顶点 vertex2的边链接指针。
?顶点结点的结构
存储顶点信息的结点表 以顺序表方式组织,
每一个顶点结点有两个数据成员：其中，
data 存放与该顶点相关的信息,Firstout
是指示第一条依附该顶点的边的指针。在
邻接多重表中,所有依附同一个顶点的边
都链接在同一个单链表中。
data Firstout
需要时还可设置一个存放与该边相关的权
值的域 cost。
? 从 顶点 i 出发,可以循链找到所有依附于该
顶点的边，也可以找到它的所有邻接顶点。
? 有向图的情形
? 在用邻接表表示有向图时,有时需要同时使
用邻接表和逆邻接表。用有向图的邻接多
重表 (十字链表 )可把两个表结合起来表示。
? 边结点的结构
mark vertex1 vertex2 path1 path2
其中,mark是处理标记； vertex1和 vertex2
指明该有向边始顶点和终顶点的位置。
?顶点结点的结构
每个顶点有一个结点，它相当于出边表和
入边表的表头结点：其中，数据成员 data
存放与该顶点相关的信息，指针 Firstin指
示以该顶点为始顶点的出边表的第一条边，
Firstout指示以该顶点为终顶点的入边表
的第一条边。
data Firstin Firstout
path1是指向始顶点与该边相同的下一条边
的指针； path2是指向终顶点与该边相同的下
一条边的指针。需要时还可有权值域 cost。
–邻接多重表的结构
mark vtx1 vtx2 path1 path2
?
?
? ?
? ?
? ?
? ?
0 1
0 3
1 2
2 3
3 4
4 0
e1
e2
e3
e4
e5
e6
data Fin Fout
A
B
C
D
E
0
1
2
3
4
e1
e2
e3 e4
e5
e6
A
B C
D
E
图的遍历与连通性
? 从已给的连通图中某一顶点出发，沿着一
些边访遍图中所有的顶点，且使每个顶点
仅被访问一次，就叫做图的遍历 ( Graph
Traversal )。
? 图中可能存在回路，且图的任一顶点都可
能与其它顶点相通，在访问完某个顶点之
后可能会沿着某些边又回到了曾经访问过
的顶点。
? 为了避免重复访问，可设置一个标志顶点
是否被访问过的辅助数组 visited [ ]。
? 辅助数组 visited [ ] 的初始状态为 0,在图
的遍历过程中,一旦某一个顶点 i 被访问,
就立即让 visited [i] 为 1,防止它被多次访
问。
? 图的遍历的分类,
? 深度优先搜索
DFS (Depth First Search)
? 广度优先搜索
BFS (Breadth First Search)
深度优先搜索 DFS ( Depth First Search )
? 深度优先搜索的示例
A
CD
E
G
B
F IH
A
CD
E
G
B
F IH
1 2 3
45
6
7
8 9
1 2 3
45
6
7
8 9前进 回退
深度优先搜索过程 深度优先生成树
? DFS 在访问图中某一 起始顶点 v 后,由 v 出
发,访问它的任一 邻接顶点 w1; 再从 w1 出发,
访问 与 w1邻 接 但还 没有访问过的顶点 w2;
然后再从 w2 出发,进行类似的访问,… 如此
进行下去,直至到达所有的邻接顶点都被访
问过的顶点 u 为止 。接着,退回一步,退到
前一次刚访问过的顶点,看是否还有其它没
有被访问的邻接顶点。 如果有,则访问此顶
点,之后再从此顶点出发,进行与前述类似
的访问 ; 如果没有,就再退回一步进行搜索。
重复上述过程,直到连通图中所有顶点都被
访问过为止。
图的深度优先搜索算法
template<class Type> void Graph <Type>,:
DFS ( ) {
int * visited = new int [NumVertices];
for ( int i = 0; i < NumVertices; i++ )
visited [i] = 0; //访问数组 visited 初始化
DFS (0,visited ); //从顶点 0出发开始搜索
delete [ ] visited; //释放 visited
}
template<class Type> void Graph <Type>,:
DFS ( const int v,int visited [ ] ) {
cout << GetValue (v) << ? ?; //访问顶点 v
visited[v] = 1; //顶点 v 作访问标记
int w = GetFirstNeighbor (v);
//取 v 的第一个邻接顶点 w
while ( w != -1 ) { //若邻接顶点 w 存在
if ( !visited[w] ) DFS ( w,visited );
//若 顶点 w 未访问过,递归访问顶点 w
w = GetNextNeighbor ( v,w );
//取顶点 v 排在 w 后的下一个邻接顶点
}
}
广度优先搜索 BFS ( Breadth First Search )
? 广度优先搜索的示例
A
CD
E
G
B
F IH
A
CD
E
G
B
F H
1 2
34
5
6
7
8 9
1 2
34
5
6
7
8 9
广度优先搜索过程 广度优先生成树
I
? BFS在访问了 起始顶点 v 之后,由 v 出发,依
次访问 v 的各个 未被访问过的邻接顶点 w1,
w2,…,wt,然后再顺序访问 w1,w2,…,wt 的
所有还未被访问过的邻接顶点。再从这些访
问过的顶点出发，再访问它们的所有还未被
访问过的邻接顶点,… 如此做下去，直到
图中所有顶点都被访问到为止。
? 广度优先搜索是一种分层的搜索过程,每向
前走一步可能访问一批顶点,不像深度优先
搜索那样有往回退的情况。因此,广度优先
搜索不是一个递归的过程。
? 为了实现逐层访问,算法中使用了一个 队列,
以记忆正在访问的这一层和上一层的顶点,
以便于向下一层访问。
? 为避免重复访问,需要一个辅助数组 visited
[ ]，给被访问过的顶点加标记。
图的广度优先搜索算法
template<class Type> void Graph <Type>,:
BFS ( int v ) {
int * visited = new int[NumVertices];
for ( int i = 0; i < NumVertices; i++ )
visited[i] = 0; //visited初始化
cout << GetValue (v) << ' '; visited[v] = 1;
Queue<int> q; q.EnQueue (v); //进队列
while ( !q.IsEmpty ( ) ) { //队空搜索结束
v = q.GetFront( ); q.DeQueue ( );
int w = GetFirstNeighbor (v);
while ( w != -1 ) { //若邻接顶点 w 存在
if ( !visited[w] ) { //未访问过
cout << GetValue (w) << ? ?;
visited[w] = 1; q.EnQueue (w);
}
w = GetNextNeighbor (v,w);
} //重复检测 v 的所有邻接顶点
} //外层循环，判队列空否
delete [ ] visited;
}
连通分量 (Connected component)
? 当无向图为非连通图时,从图中某一顶点出
发,利用深度优先搜索算法或广度优先搜索
算法 不可能遍历到图中的所有顶点,只能访
问到该顶点所在的最大连通子图 (连通分量 )
的所有顶点 。
? 若从无向图的每一个连通分量中的一个顶
点出发进行遍历,可求得无向图的所有连
通分量。
? 在算法中,需要对图的每一个顶点进行检
测：若已被访问过，则该顶点一定是落在
图中已求得的连通分量上；若还未被访问，
则从该顶点出发遍历图，可求得图的另一
个连通分量。
? 对于非连通的无向图，所有连通分量的生
成树组成了非连通图的生成森林 。
A
C D E IB
F OG
H
J
NML
K
非连通无向图
A H K
C D E IB
F OG J
NML
非连通图的连通分量
确定连通分量的算法
template <class Type> void Graph <Type>,:
Components ( ) {
int *visited = new int[NumVertices];
for ( int i = 0; i < NumVertices; i++ )
visited[i] = 0; //visited 初始化
for ( i = 0; i < NumVertices; i++ )
if ( !visited[i] ) { //检测顶点是否访问过
DFS ( i,visited ); //未访问,出发访问
OutputNewComponent ( ); //连通分量
}
【 例 】 以深度优先搜索方法从顶点 出发遍
历图,建立深度优先生成森林。
A B C
D E F
G
A
A
B
DE
C
F
G有向图 深度优先生成森林
delete [ ] visited;
}
template<class Type> void Graph <Type>,:
DFS_Forest ( Tree <Type> &T ) {
TreeNode <Type> * rt,* subT;
int *visited = new int[n]; //创建访问数组
for ( int i = 0; i < n; i++ )
visited [i] = 0; //初始化
for ( i = 0; i < n; i++ ) //遍历所有顶点
if ( !visited[i] ) { //顶点 i 未访问过
if ( T.IsEmpty ( ) ) //原为空森林,建根
subT = rt = T.BuildRoot ( GetValue(i) );
//顶点 i 的值成为根 rt 的值
else
subT = T.InsertRightSibling
( subT,GetValue(i) );
//顶点 i 的值成为 subT 右兄弟的值
DFS_Tree ( T,subT,i,visited );
//从顶点 i 出发深度优先遍历,建立以
// subT为根的 T 的子树
}
}
template<class Type> void Graph <Type>,,
DFS_Tree ( Tree<Type> &T,TreeNode
<Type>*RT,int v,int visited [ ] ) {
TreeNode<Type> * p;
visited [v] = 1; //顶点 v 作访问过标志
int w = GetFirstNeighbor (v);
//取顶点 v 的第一个邻接顶点 w
int FirstChild = 1;
//第一个未访问子女应是 v 的左子女
while ( w ) { //邻接顶点 w 存在
if ( ! visited [w] ) {
// w未访问过,将成为 v 的子女
if ( FirstChild ) {
p = T.InsertLeftChild ( RT,GetValue(w) );
// p 插入为 RT 的左子女
FirstChild = 0; //建右兄弟
}
else p = T.InsertRightSibling
( p,GetValue(w) );
// p 插入为 p 的左子女
DFS_Tree ( T,p,w,visited );
//递归建立 w 的以 p 为根的 子树
} //邻接顶点 w 处理完
w = GetNextNeighbor ( v,w );
//取 v 的下一个邻接顶点 w
} //回到 while 判邻接顶点 w 存在
}
重连通分量 (Biconnected Component)
? 在无向连通图 G中,当且仅当删去 G中的顶
点 v及 所有依附于 v的所有边 后,可将图分割
成两个或两个以上的连通分量，则称顶点 v
为 关节点 。
? 没有 关节点 的连通图叫做重连通图。
? 在重连通图上,任何一对顶点之间至少存在
有两条路径,在删去某个顶点及与该顶点相
关联的边时,也不破坏图的连通性。
? 一个连通图 G如果不是重连通图，那么它可
以包括几个重连通分量。
? 在一个无向连通图 G中,重连通分量可以利
用深度优先生成树找到 。
? 在图中各 顶点旁标明的深度优先数,给出进
行深度优先搜索时各顶点访问的次序。
? 深度优先生成树的根是 关节点 的充要条件
是 它至少有两个子女 。
? 其它顶点 u 是 关节点 的充要条件是 它至少
有一个子女 w,从 w 出发,不能通过 w,w
的子孙及一条回边所组成的路径到达 u 的
祖先 。
A
B
C D
E
F
G
H
I J A
B
C D
E
F
G
H
J
A
B
C D
E
F
G
H
JI
I
12
3
4
5
6
7
8
9 10
根有两
个子女
关
节
点
关
节
点
关节点
最小生成树
( minimum cost spanning tree )
? 使用不同的遍历图的方法，可以得到不同
的生成树；从不同的顶点出发，也可能得
到不同的生成树。
? 按照生成树的定义,n 个顶点的连通网络
的生成树有 n 个顶点,n-1 条边。
? 构造最小生成树的准则
? 必须使用且仅使用该网络中的 n-1 条边
来联结网络中的 n 个顶点；
? 不能使用产生回路的边；
? 各边上的权值的总和达到最小。
克鲁斯卡尔 (Kruskal) 算法
? 克鲁斯卡尔算法的基本思想：
设有一个有 n 个顶点的连通网络 N = { V,
E },最初先构造一个只有 n 个顶点,没有边
的非连通图 T = { V,? },图中每个顶点自
成一个连通分量。当在 E 中选到一条具有
最小权值的边时,若该边的两个顶点落在不
同的连通分量上，则将此边加入到 T 中 ; 否
则将此边舍去，重新选择一条权值最小的
边。 如此重复下去,直到所有顶点在同一个
连通分量上为止。
? 算法的框架 利用 最小堆 (MinHeap)和 并查
集 (DisjointSets)来实现 克鲁斯卡尔算法 。
? 首先,利用 最小堆 来存放 E中的所有的边,堆
中每个结点的格式为
? 在构造最小生成树过程中,利用 并查集 的运
算检查依附一条边的两顶点 tail,head是否
在同一连通分量 (即 并查集的同一个子集合 )
上,是则舍去这条边；否则将此边加入 T,
同时将这两个顶点放在同一个连通分量上。
tail head cost
边的两个顶点位置 边的权值
10
? 随着各边逐步加入到最小生成树的边集合中,
各连通分量也在逐步合并,直到形成一个连
通分量为止。
应用克鲁斯卡尔算法构造最小生成树的过程
5
0
4
6
1
3
2
28
10
25
14
24
22
16
18 12
5
0
4
6
1
3
2 5
0
4
6
1
3
2
原图 (a) (b)
10
12
5
0
4
6
1
3
2
28
10
25
14
24
22
16
18 12
5
0
4
6
1
3
2 5
0
4
6
1
3
2
10 14
12
原图 (c) (d)
5
0
4
6
1
3
2
10 14 16
12
(e) (f) (g)
5
0
4
6
1
3
2
10 14
22
16
12
5
0
4
6
1
2
10
25
14
22
16
123
最小生成树类定义
const int MAXNUM = 机器可表示的,问题中
不可能出现的大数
class MinSpanTree;
class MSTEdgeNode { //生成树边结点类
friend class MinSpanTree;
private:
int tail,head; //生成树各边的两顶点
float cost; //生成树各边的权值
public:
MSTEdgeNode ( ) //构造函数
,tail ( -1 ),head ( -1 ),cost ( 0 ) { }
};
class MinSpanTree {
protected:
MSTEdgeNode * edgevalue;
int MaxSize,n;
public:
MinSpanTree ( int sz = NumVertices-1 )
,MaxSize(sz),n (0) {
edgevalue = new MSTEdgeNode[MaxSize];
}
int Insert ( MSTEdgeNode& item );
}
利用克鲁斯卡尔算法建立最小生成树
void Graph<string>,:
Kruskal ( MinSpanTree& T ) {
MSTEdgeNode e; //边结点辅助单元
MinHeap <MSTEdgeNode> H( NumEdges );
int NumVertices = VerticesList.last; //顶点数
UFSets F ( NumVertices ); //并查集
for ( int u = 0; u < NumVertices; u++ )
for ( int v = u +1; v < NumVertices; v++ )
if ( Edge[u][v] != MAXNUM ) {
e.tail = u; e.head = v; //插入堆
e.cost = Edge[u][v]; H.Insert (e);
}
int count = 1; //最小生成树加入边数计数
while ( count < NumVertices ) {
H.RemoveMin ( e ); //从堆中退出一条边
u = F.Find ( e.tail ); //检测两端点的根
v = F.Find ( e.head );
if ( u != v ) { //根不在同一连通分量
F.Union ( u,v ); //合并
T.Insert ( e ); //该边存入最小生成树
count++;
}
}
}
出堆顺序 (0,5,10) 选中 (2,3,12) 选中
(1,6,14)选中 (1,2,16) 选中 (3,6,18) 舍弃
(3,4,22)选中 (4,6,24) 舍弃 (4,5,25) 选中
并查集 邻接矩阵表示
-2
-2
-2
-2
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -10
2-1 -1 -10
-2 2 0
0
0
0
0 1 2 3 4 5 6
-2 1-1
1-2 -1-4 21
-2 -5 1 2 11
-71 1 2 1 1
F 0 1 2 3 4 5 6
0 28 ? ? ? 10 ? 0
28 0 16 ? ? ? 14 1
? 16 0 12 ? ? ? 2
? ? 12 0 22 ? 18 3
? ? ? 22 0 25 24 4
10 ? ? ? 25 0 ? 5
? 14 ? 18 24 ? 0 6
普里姆 (Prim)算法
? 普里姆算法的基本思想：
从连通网络 N = { V,E }中的某一顶点 u0 出
发,选择与它关联的具有最小权值的边 ( u0,
v ),将其顶点加入到 生成树顶点集合 U中。
以后每一步从 一个顶点在 U 中,而 另一个
顶点不在 U 中 的各条边中选择 权值最小的
边 (u,v),把它的顶点加入到 集合 U 中。如
此继续下去,直到网络中的所有顶点都加入
到生成树顶点集合 U 中为止。
? 采用邻接矩阵作为图的存储表示。
2525
10
5
0
4
6
1
3
2
28
10
25
14
24
22
16
18
5
0
4
6
1
3
2 5
0
4
6
1
3
2
10
原图 (a) (b)
5
0
4
6
1
3
2
10
(c) (d) (e) (f)
5
0
4
6
1
3
2
10
22
12
5
0
4
6
1
2
10
25
14
22
16
123
25
22
12
? 在构造过程中, 还设置了两个辅助数组：
? lowcost[ ] 存放 生成树顶点集合内顶点 到
生成树外各顶点 的各边上的当前最小权值；
? nearvex[ ] 记录 生成树顶点集合外各顶点
距离 集合内哪个顶点 最近 (即权值最小 )。
? 例子
5
0
4
6
1
3
2
28
10
25
14
24
22
16
18 12
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
????
???
???
????
???
????
0241814
02510
2425022
1822012
12016
1416028
10280
? 若选择从顶点 0出发，即 u0 = 0，则两个辅
助数组的初始状态为：
? 然后反复做以下工作：
? 在 lowcost [ ]中选择 nearvex[i] ? -1 &&
lowcost[i]最小 的边,用 v 标记它。则选中
的权值最小的边为 (nearvex[v],v),相应的
权值为 lowcost[v]。
0 28 ? ? ? 10 ?
-1 0 0 0 0 0 0
lowcost
nearvex
0 1 2 3 4 5 6
? 将 nearvex[v] 改为 -1,表示它已加入生
成树顶点集合。
? 将边 (nearvex[v],v,lowcost[v] ) 加入生
成树的边集合。
? 取 lowcost[i] = min{ lowcost[i],
Edge[v][i] },即用 生成树顶点集合外各
顶点 i 到刚加入该集合的新顶点 v 的距
离 Edge[v][i] 与 原来它们到生成树顶点
集合中顶点的最短距离 lowcost[i] 做比较,
取距离近的作为这些集合外顶点到生成
树顶点集合内顶点的最短距离。
? 如果 生成树顶点集合外顶点 i 到 刚加入
该集合的新顶点 v 的距离比原来它到生
成树顶点集合中顶点的最短距离还要近，
则修改 nearvex[i], nearvex[i] = v。表示
生成树外顶点 i到生成树内顶点 v当前距
离最近。
0 28 ? ? ? 10 ?
-1 0 0 0 0 0 0
lowcost
nearvex
0 1 2 3 4 5 6
选 v=5 选边 (0,5)
顶点 v=5加入生成树顶点集合：
0 28 ? ? 25 10 ?
-1 0 0 0 5 -1 0
lowcost
nearvex
0 1 2 3 4 5 6
选 v=4 选边 (5,4)
5
0
4
6
1
3
2
28
10
25
14
24
22
16
18
原图 边 (0,5,10) 加入生成树
12
0
4
6
1
3
2
10
25
5
0 1 2 3 4 5 6
顶点 v=4加入生成树顶点集合：
0 28 ? 22 25 10 24
-1 0 0 4 -1 -1 4
lowcost
nearvex
选 v=3 选边 (4,3)
5
0
4
6
1
3
2
28
10
25
14
24
22
16
18
原图 边 (5,4,25) 加入生成树
12
5
0
4
6
1
3
2
10
25
22
顶点 v=3加入生成树顶点集合：
0 28 12 22 25 10 18
-1 0 3 -1 -1 -1 3
lowcost
nearvex
0 1 2 3 4 5 6
选 v=2 选边 (3,2)
5
0
4
6
1
3
2
28
10
25
14
24
22
16
18
原图 边 (4,3,22) 加入生成树
12
5
0
4
6
1
3
2
10
25
22
12
lowcost
nearvex
0 1 2 3 4 5 6
顶点 v=2加入生成树顶点集合：
0 16 12 22 25 10 18
-1 2 -1 -1 -1 -1 3
选 v=1 选边 (2,1)
5
0
4
6
1
3
2
28
10
25
14
24
22
16
18
原图 边 (3,2,12) 加入生成树
12
5
0
4
1
3
2
10
25
22
16
12
顶点 v=1加入生成树顶点集合：
0 16 12 22 25 10 14
-1 -1 -1 -1 -1 -1 1
lowcost
nearvex
0 1 2 3 4 5 6
选 v=6 选边 (1,6)
5
0
4
6
1
3
2
28
10
25
14
24
22
16
18
原图 边 (2,1,16) 加入生成树
12
5
0
4
6
1
3
2
10
25
14
22
16
12
lowcost
nearvex
0 1 2 3 4 5 6
顶点 v=6加入生成树顶点集合：
0 16 12 22 25 10 14
-1 -1 -1 -1 -1 -1 -1
5
0
4
6
1
3
2
28
10
25
14
24
22
16
18
原图 边 (1,6,14) 加入生成树
12
5
0
4
6
1
3
2
10
25
14
22
16
12
最后生成树中边集合里存入得各条边为,
(0,5,10),(5,4,25),(4,3,22),
(3,2,12),(2,1,16),(1,6,14)
利用普里姆算法建立最小生成树
void Graph<string>,:
Prim ( MinSpanTree &T ) {
int NumVertices = VerticesList.last; //顶点数
float * lowcost = new float[NumVertices];
int * nearvex = new int[NumVertices];
for ( int i = 1; i < NumVertices; i++ ) {
lowcost[i] = Edge[0][i]; //顶点 0到各边代价
nearvex[i] = 0; //及最短带权路径
}
nearvex[0] = -1; //加到生成树顶点集合
MSTEdgeNode e; //最小生成树结点单元
for ( i = 1; i < NumVertices; i++ ) {
//循环 n-1次,加入 n-1条边
float min = MAXNUM; int v = 0;
for ( int j = 0; j < NumVertices; j++ )
if ( nearvex[j] != -1 && lowcost[j] < min )
{ v = j; min = lowcost[j]; }
//求生成树外顶点到生成树内顶点具有最
//小权值的边,v是 当前具最小权值的边
if ( v ) { //v=0表示再也找不到要求顶点
e.tail = nearvex[v]; e.head = v;
e.cost = lowcost[v];
T.Insert (e); //选出的边加入生成树
nearvex[v] = -1; //该边加入生成树标记
for ( j = 1; j < NumVertices; j++ )
if ( nearvex[j] != -1 &&
Edge[v][j] < lowcost[j] ) {
lowcost[j] = Edge[v][j]; //需要修改
nearvex[j] = v;
}
}
} //循环 n-1次,加入 n-1条边
}
? 分析以上算法,设连通网络有 n 个顶点,则
该算法的时间复杂度为 O(n2),它适用于边
稠密的网络。
最短路径 (Shortest Path)
? 最短路径问题,如果从图中某一顶点 (称为
源点 )到达另一顶点 (称为终点 )的路径可能
不止一条，如何找到一条路径使得沿此路
径上各边上的权值总和达到最小。
? 问题解法
? 边上权值非负情形的单源最短路径问题
— Dijkstra算法 ? (仅讲此算法 )
? 边上权值为任意值的单源最短路径问题
— Bellman和 Ford算法 ? (不讲 )
? 所有顶点之间的最短路径
— Floyd算法 ? (不讲 )
边上权值非负情形的单源最短路径问题
? 问题的提法,给定一个带权有向图 D与源
点 v，求从 v 到 D中其它顶点的最短路径。
限定各边上的权值大于或等于 0。
? 为求得这些最短路径,Dijkstra提出按路径
长度的递增次序,逐步产生最短路径的算
法。首先求出长度最短的一条最短路径，
再参照它求出长度次短的一条最短路径，
依次类推，直到从顶点 v到其它各顶点的最
短路径全部求出为止。
? 举例说明
Dijkstra逐步求解的过程
1
0
4
32
10 100
30
50
20
60
10
源点 终点 最短路径 路径长度
v0 v1 (v0,v1) 10
v2 (v0,v1,v2) (v0,v3,v2) ?,60,50
v3 (v0,v3) 30
v4 (v0,v4) (v0,v3,v4) (v0,v3,v2,v4) 100,90,60
? 引入辅助数组 dist。它的每一个分量 dist[i]表
示当前找到的从 源点 v0到 终点 vi 的最短路径
的长度。初始状态：
? 若从源点 v0到顶点 vi 有边,则 dist[i]为该边
上的权值；
? 若从源点 v0到顶点 vi 无边,则 dist[i]为 ?。
? 假设 S 是已求得的最短路径的终点的集合，
则可证明,下一条最短路径必然是从 v0 出发，
中间只经过 S 中的顶点便可到达的那些顶点
vx (vx?V-S )的路径中的一条。
? 每次求得一条最短路径后,其终点 vk加入集合
S，然后 对所有的 vi?V-S，修改其 dist[i]值 。
Dijkstra算法可描述如下：
① 初始化,S ← { v0 };
dist[j] ← Edge[0][j],j = 1,2,…,n-1;
// n为图中顶点个数
② 求出最短路径的长度：
dist[k] ← min { dist[ i] },i ? V- S ;
S ← S U { k };
③ 修改：
dist[i] ← min{ dist[ i],dist[k] + Edge[k][i] },
对于每一个 i ? V- S ;
④ 判断：若 S = V,则算法结束，否则转 ② 。
用于计算最短路径的图邻接矩阵类
const int NumVertices = 6; //图最大顶点个数
class Graph { //图的类定义
private:
float Edge[NumVertices][NumVertices];
float dist[NumVertices]; //最短路径长度数组
int path[NumVertices]; //最短路径数组
int S[NumVertices]; //最短路径顶点集
public:
void ShortestPath ( int,int );
int choose ( int );
};
计算从单个顶点到其它各顶点最短路径
void Graph,,ShortestPath ( int n,int v ){
//Graph是一个具有 n 个顶点的带权有向图,各
//边上的权值由 Edge[i][j]给出。本算法建立起
//一个数组, dist[j],0? j<n,是当前求到的从顶
//点 v 到顶点 j 的最短路径长度,同时用数组
//path[j],0? j<n,存放求到的最短路径 。
for ( int i = 0; i < n; i++) {
dist[i] = Edge[v][i]; //dist数组初始化
S[i] = 0;
if ( i != v && dist[i] < MAXNUM)
path[i] = v;
else path[i] = -1; //path数组初始化
}
S[v] = 1; dist[v] = 0; //顶点 v加入顶点集合
//选当前不在集合 S中具有最短路径的顶点 u
for ( i = 0; i < n-1; i++ ) {
float min = MAXNUM; int u = v;
for ( int j = 0; j < n; j++ )
if ( !S[j] && dist[j] < min )
{ u = j; min = dist[j]; }
S[u] = 1; //将顶点 u加入集合 S
for ( int w = 0; w < n; w++ ) //修改
if ( !S[w] && Edge[u][w] < MAXNUM
&& dist[u] + Edge[u][w] < dist[w] ) {
//顶点 w未加入 S,且绕过 u可以缩短路径
dist[w] = dist[u] + Edge[u][w];
path[w] = u; //修改到 w的最短路径
}
}
}
Dijkstra算法中各辅助数组的最终结果
从表中读取源点 0到终点 v的最
短路径的方法, 举顶点 4为例
path[4] = 2 path[2] = 3
path[3] = 0,反过来排列，得
到路径 0,3,2,4,这就是源点 0
到终点 4的最短路径。
0
41
2 3
10
50 10
20
60
30
100
序号 顶点 1 顶点 2 顶点 3 顶点 4
Dist 10 50 30 60
path 0 3 0 2
活动网络 (Activity Network)
? 计划、施工过程、生产流程、程序流程等都
是, 工程,。除了很小的工程外，一般都把
工程分为若干个叫做,活动,的子工程。完
成了这些活动，这个工程就可以完成了。
? 例如，计算机专业学生的学习就是一个工程，
每一门课程的学习就是整个工程的一些活动。
其中有些课程要求先修课程，有些则不要求。
这样在有的课程之间有领先关系，有的课程
可以并行地学习。
用顶点表示活动的网络 (AOV网络 )
C1 高等数学
C2 程序设计基础
C3 离散数学 C1,C2
C4 数据结构 C3,C2
C5 高级语言程序设计 C2
C6 编译方法 C5,C4
C7 操作系统 C4,C9
C8 普通物理 C1
C9 计算机原理 C8
学生课程学习工程图
C8
C3
C5
C4
C9
C6
C7C1
C2
? 可以用 有向图 表示一个工程。在这种有向
图中,用顶点表示活动, 用有向边 <Vi,Vj>
表示 活动 Vi 必须先于活动 Vj进行 。这种有
向图叫做顶点表示活动的 AOV网络
(Activity On Vertices)。
? 在 AOV网络中不能出现有向回路,即有向
环。如果出现了有向环，则意味着某项活
动应以自己作为先决条件。
? 因此，对给定的 AOV网络，必须先判断它
是否存在有向环。
? 检测有向环的一种方法是对 AOV网络构造
它的拓扑有序序列。即将各个顶点 (代表各
个活动 )排列成一个线性有序的序列，使得
AOV网络中所有应存在的前驱和后继关系
都能得到满足。
? 这种 构造 AOV网络全部顶点的拓扑有序序
列的运算就叫做拓扑排序。
? 如果通过拓扑排序能将 AOV网络的所有顶
点都排入一个拓扑有序的序列中,则该网络
中必定不会出现有向环。
? 如果 AOV网络中存在有向环，此 AOV网络
所代表的工程是不可行的。
? 例如,对学生选课工程图进行拓扑排序,得
到的拓扑有序序列为
C1,C2,C3,C4,C5,C6,C8,C9,C7
或 C1,C8,C9,C2,C5,C3,C4,C7,C6
C8
C3
C5
C4
C9
C6
C7C1
C2
进行拓扑排序的方法
① 输入 AOV网络。令 n 为顶点个数。
② 在 AOV网络中选一个 没有直接前驱 的顶点,
并输出之 ;
③ 从图中删去该顶点,同时删去所有它发出
的有向边 ;
④ 重复以上 ②, ③ 步,直到
?全部顶点均已输出,拓扑有序序列形成，
拓扑排序完成；或
?图中还有未输出的顶点,但已跳出处理
循环 。说明图中还剩下一些顶点,它们都
有直接前驱。这时网络中必存在有向环。
C0 C1 C2
C3 C4 C5
拓扑排序的过程
(a) 有向无环图
C2
C5
C1C0
C3
(b) 输出顶点 C4
C1 C2
C5C3
(c) 输出顶点 C0
C4
C0 C2
C5
C1
C3
(d) 输出顶点 C3
C1 C2
C5
(e) 输出顶点 C2
C5
C1
(f) 输出顶点 C1
C5
(g) 输出顶点 C5
最后得到的拓扑有序序列为 C4,C0,C3,C2,
C1,C5 。它满足图中给出的所有前驱和后继关系，
对于本来没有这种关系的顶点，如 C4和 C2，也
排出了先后次序关系。
(h) 拓扑排序完成
AOV网络及其邻接表表示
C0 C1 C2
C3 C4 C5
C0
C1
C2
C3 0
C4
C5 0
0
1
2
3
4
5
count data adj
1
3
0
1
0
3
1
dest link
3 0
5
1 5 0
0 1 5 0
? 在邻接表中增设一个数组 count[ ],记录各
顶点入度 。 入度为零的顶点即无前驱顶点 。
? 在输入数据前,顶点表 NodeTable[ ]和入度数
组 count[ ]全部初始化 。 在输入数据时,每输
入一条边 <j,k>,就需要建立一个边结点,并
将它链入相应边链表中,统计入度信息：
Edge<int> * p = new Edge<int> (k);
//建立边结点,dest 域赋为 k
p->link = NodeTable[j].adj;
NodeTable[j].adj = p;
//链入顶点 j 的边链表的前端
count[k]++; //顶点 k 入度加一
? 在算法中,使用一个存放入度为零的顶点的
链式栈,供选择和输出无前驱的顶点。
? 拓扑排序算法可描述如下：
? 建立入度为零的顶点栈 ;
? 当入度为零的顶点栈不空时,重复执行
? 从顶点栈中退出一个顶点,并输出之 ;
? 从 AOV网络中删去这个顶点和它发出
的边,边的终顶点入度减一 ;
? 如果边的终顶点入度减至 0,则该顶点
进入度为零的顶点栈 ;
? 如果输出顶点个数少于 AOV网络的顶点
个数,则报告网络中存在有向环。
? 在算法实现时,为了建立入度为零的顶点栈,
可以不另外分配存储空间,直接利用入度为
零的顶点的 count[ ]数组元素。设立一个栈
顶指针 top,指示当前栈顶位置,即某一个入
度为零的顶点。栈初始化时置 top = -1。
? 将 顶点 i 进栈时执行以下指针的修改：
count[i] = top; top = i ;
// top指向新栈顶 i,原栈顶元素在 count[i]中
? 退栈操作可以写成：
j = top; top = count[top];
//位于栈顶的顶点记于 j,top退到次栈顶
拓扑排序时入度
为零的顶点栈在
count[]中的变化
C0 C1 C2
C3 C4 C5
1
3
0
1
0
3
1
3
-1
1
2
3
2
2
-1
1
2
2
2
1
-1
2
2
2
0
1
2
3
4
5
0
1
2
3
4
5
0
1
2
3
4
5
0
1
2
3
4
5
top top
top
top
建栈
top
top
顶点 4
出栈
top
top
顶点 0
出栈
拓扑排序时入度
为零的顶点栈在
count[]中的变化
C0 C1 C2
C3 C4 C5
2
1
-1
2
2
2
2
-1
-1
2
2
1
2
-1
-1
2
2
-1
2
-1
-1
2
2
-1
0
1
2
3
4
5
0
1
2
3
4
5
0
1
2
3
4
5
0
1
2
3
4
5
top
top
top
top
top顶点 1出栈
top
顶点 5
出栈
顶点 3
出栈
顶点 2
出栈
class Graph { //图的邻接表的类定义
friend class <int> Vertex;
friend class <int> Edge;
private:
Vertex<int> * NodeTable; //顶点表数组
int *count; //入度数组兼栈
int n; //顶点个数
public:
Graph ( const int vertices = 0 ), n ( vertices ) {
NodeTable = new vertex <int> [n];
count = new int[n];
};
void TopologicalOrder ( );
}
拓扑排序的算法
void Graph,,TopologicalSort ( ) {
int top = -1; //入度为零的顶点栈初始化
for ( int i = 0; i < n; i++ ) //入度为零顶点
if ( count[i] == 0 ) //进栈
{ count[i] = top; top = i; }
for ( i = 0; i < n; i++ ) //期望输出 n个顶点
if ( top == -1 ) { //中途栈空,转出
cout <<,网络中有回路 ！ " << endl;
return;
}
else { //继续拓扑排序
int j = top; top = count[top]; //退栈
cout << j << endl; //输出
Edge<float> * p = NodeTable[j].adj;
while ( p != NULL ) { //扫描出边表
int k = p->dest; //另一顶点
if ( --count[k] == 0 ) //顶点入度减一
{ count[k] = top; top = k; }
//顶点的入度 减至零,进栈
p = p->link;
}
}
}
用边表示活动的网络 (AOE网络 )
? 如果在 无有向环的带权有向图 中,用有向边
表示一个工程中的活动 (Activity),用边上权
值表示活动持续时间 (Duration),用顶点表
示事件 (Event),则这样的有向图叫做用边
表示活动的网络,简称 AOE ( Activity On
Edges ) 网络。
? AOE网络在某些工程估算方面非常有用。
例如，可以使人们了解：
? 完成整个工程至少需要多少时间 (假设网
络中没有环 )?
? 为缩短完成工程所需的时间,应当加快哪
些活动?
? 从源点到各个顶点,以至从源点到汇点的有
向路径可能不止一条。 这些路径的长度也
可能不同。 完成不同路径的活动所需的时
间虽然不同,但只有各条路径上所有活动都
完成了,整个工程才算完成。
? 因此,完成整个工程所需的时间取决于从源
点到汇点的最长路径长度,即在这条路径上
所有活动的持续时间之和。 这条路径长度最
长的路径就叫做关键路径 (Critical Path)。
a9=6
1
3
2
4
a1=8
a2=12
5
6
7 8a10=12
a8=18
a5=28
a6=8
a7=6
a3=14
a4=10
? 要找出关键路径，必须找出 关键活动,即不
按期完成就会影响整个工程完成的活动。
? 关键路径上的所有活动都是关键活动 。因
此,只要找到了关键活动,就可以找到关键
路径。例如,下图就是一个 AOE网。
定义几个与计算关键活动有关的量：
① 事件 Vi 的最早可能开始时间 Ve(i)
是从 源点 V0到 顶点 Vi的最长路径长度 。
② 事件 Vi的最迟允许开始时间 Vl[i]
是在保证汇点 Vn-1 在 Ve[n-1] 时刻完成的前
提下, 事件 Vi 的允许的最迟开始时间 。
③ 活动 ak的最早可能开始时间 e[k]
设活动 ak 在边 < Vi,Vj >上,则 e[k]是从源点
V0到顶点 Vi 的最长路径长度 。 因此,
e[k] = Ve[i]。
④ 活动 ak的最迟允许开始时间 l[k]
l[k]是在不会引起时间延误的前提下,该活
动允许的最迟开始时间。
l[k] = Vl[j] - dur(<i,j>)。
其中,dur(<i,j>)是完成 ak 所需的时间。
⑤ 时间余量 l[k] - e[k]
表示活动 ak 的最早可能开始时间和最迟允
许开始时间的时间余量。 l[k] == e[k] 表示活
动 ak 是没有时间余量的关键活动。
? 为找出关键活动,需要求各个活动的 e[k] 与
l[k]，以判别是否 l[k] == e[k]。
? 为求得 e[k]与 l[k],需要先求得从源点 V0 到
各个顶点 Vi 的 Ve[i] 和 Vl[i]。
? 求 Ve[i]的递推公式
? 从 Ve[0] = 0 开始，向前递推
< Vj,Vi > ? S2,i = 1,2,?,n-1
S2 是所有指向 Vi 的有向边 < Vj,Vi >的集合。
? 从 Vl[n-1] = Ve[n-1]开始，反向递推
< Vi,Vj > ? S1,i = n-2,n-3,?,0
S1是所有源自 Vi的有向边 < Vi,Vj >的集合。
},),(][ {][ ???? ij
j
VVdu rjVem axiVe
},),(][ {][ ???? ji
j
VVdu rjVlm i niVl
? 这两个递推公式的计算必须分别在 拓扑有序
及 逆拓扑有序 的前提下进行。
? 设 活动 ak(k=1,2,…,e)在带权有向边 < Vi,Vj >
上,其持续时间用 dur (<Vi,Vj >) 表示,则有
e[k] = Ve[i]；
l[k] = Vl[j] - dur(<Vi,Vj >)； k = 1,2,…,e。
这样就得到计算关键路径的算法。
? 为了简化算法,假定在求关键路径之前已经
对各顶点实现了拓扑排序,并按拓扑有序的
顺序对各顶点重新进行了编号。
1
3
2
4
a1=8
a2=12
5
6
7 8a10=12
a9=6
a8=18
a5=28
a6=8
a7=6
a3=14
a4=10
Ve
Vl
1 2 3 4 5 6 7 8
0 8 12 22 28 40 46 58
0 8 12 22 28 40 46 58
e
l
0 0 8 12 12 22 22 28 40 46
0 0 8 12 12 32 22 28 40 46
1 2 3 4 5 6 7 8 9 10
利用关键路径法求 AOE网的各关键活动
void graph,,CriticalPath ( ) {
//在此算法中需要在邻接表中单链表的结点内
//增加一个 int型 cost域,记录该边上的权值。
int i,j; int p,k; float e,l;
float * Ve = new float[n];
float * Vl = new float[n];
for ( i = 0; i < n; i++ ) Ve[i] = 0;
for ( i = 0; i < n; i++ ) { //顺向计算 Ve[ ]
Edge<float> *p = NodeTable[i].adj;
while ( p != NULL ) {
k = p->dest;
if ( Ve[i] + p->cost > Ve[k] )
Ve[k] = Ve[i] + p->cost;
p = p->link;
}
}
Vl[n-1] = Ve[n-1];
for ( i = n-2; i > 0; i-- ) { //逆向计算 Vl[ ]
p = NodeTable[i].adj;
while ( p != NULL ) {
k = p->dest;
if ( Vl[k] - p->cost < Vl[i])
Vl[i] = Vl[k] - p->cost;
p = p->link;
}
}
for ( i = 0; i < n; i++ ) { //求各活动的 e,l
p = NodeTable[i].adj;
while ( p != NULL ) {
k = p->dest;
e = Ve[i]; l = Vl[k] - p->cost;
if ( l == e ) cout << "<" << i << "," << k
<<,>” <<,是关键活动, << endl;
p = p->link;
}
}
}
注意
?所有顶点按拓扑有序的次序编号
?仅计算 Ve [i] 和 Vl[i] 是不够的，还须计算
e[k] 和 l[k]。
?不是任一关键活动加速一定能使整个工程
提前。
?想使整个工程提前，要考虑各个关键路径
上所有关键活动。
