CHAPTER 9
GRAPH ALGORITHMS § 1 Definitions
G( V,E ) where G,:= graph,V = V( G ),:= finite nonempty set of
vertices,and E = E( G ),:= finite set of edges.
Undirected graph,( vi,vj ) = ( vj,vi ),:= the same edge.
Directed graph (digraph),< vi,vj >,:=? < vj,vi >vi vj
tail head
Restrictions,
(1) Self loop is illegal.
(2) Multigraph is not considered
0 1 0
1 2
Complete graph,a graph that has the maximum number of edges
0
2
1 3
2
)1(2 E of #
V of #
nn
nC
n
0
2
1 3
)1( E of #
V of #
2
nnP
n
n
vi vj? vi and vj are adjacent ;
( vi,vj ) is incident on vi and vj
vi vj? vi is adjacent to vj ; vj is adjacent from vi ;
< vi,vj > is incident on vi and vj
Subgraph G‘? G,:= V( G‘ )? V( G ) && E( G‘ )? E( G )
Path (? G) from vp to vq,:= { vp,vi1,vi2,,vin,vq } such that ( vp,vi1 ),
( vi1,vi2 ),,( vin,vq ) or < vp,vi1 >,,< vin,vq > belong to E( G )
Length of a path,:= number of edges on the path
Simple path,:= vi1,vi2,,vin are distinct
Cycle,:= simple path with vp = vq
vi and vj in an undirected G are connected if there is a path from vi to vj
(and hence there is also a path from vj to vi)
An undirected graph G is connected if every pair of distinct vi and vj are
connected
(Connected) Component of an undirected G,:= the maximal connected
subgraph
A tree,:= a graph that is connected and acyclic
Strongly connected directed graph G,:= for every pair of vi and vj in
V( G ),there exist directed paths from vi to vj and from vj to vi,If the
graph is connected without direction to the edges,then it is said to be
weakly connected
Strongly connected component,:= the maximal subgraph that is
strongly connected
Degree( v ),:= number of edges incident to v,For a directed G,we have
in-degree and out-degree,For example:
v in-degree(v) = 3; out-degree(v) = 1; degree(v) = 4
Given G with n vertices and e edges,then
)(d e g r e e w h e r e 2
1
0
ii
n
i
i vdde
A DAG,:= a directed acyclic graph
To describe the Adjacency Matrix of the
graph,we need a table to record the
information of each vertex and an Adjacency
Matrix contains the relations among each
vertex,
Suppose that A = (V,E) is a graphg includes n
vertex,the graph‘s Adjacency Matrix is a two
dimensional array A.edge[n][n],
Adjacency Matrix
e l s e,
),(,if,
]][[,
or
0
><1
A
EjiEji
jiE d g e
§ 2 The structure of graph‘s storage
The adjacency matrix of non-directional graph is
symmetrical
The adjacency matrix of directional graph is not always
symmetrical
0
1 2
3
0101
1010
0101
1010
A,e dg e
0
1
2?
000
101
010
A,e d g e
Among the directed graph,compute the
number of 1 on line i,can get the vertex i‘s
outdegree,Compute the number of 1 on
row i,can get the vertex i‘s indegree.
As for the undirected graph,Compute the
number of 1 on row i,can get the vertex i‘s
degree.
1
8
6
3 29 5
4
2
0
3
1
06
8053
290
410
A,e d g e
Adjacency Matrix in the network
ji
ji,ji,ji
ji,ji,j iji
ji
if
orand if
or andif
,
)(,
)(),,(
]][[
0
E E
EEW
A,e d g e
#define MaxValue Int_Max //在 <limits.h>中
const int NumEdges = 50; //edges’ number
const int NumVertices = 10; // vertex’s number
typedef char VertexData; // vertex’s data type
typedef int EdgeData; // Edge’s weight
typedef struct {
VertexData vexList[NumVertices]; //vertex table
EdgeData Edge[NumVertices][NumVertices];
//adjacency can be treat as the edge’ relation
int n,e; //the number of the vertex and edge
} MTGraph;
using Adjacency Matrix to define the graph
Adjacency List
Adjacency List,A list type of storage structure。
The structure of arc
adjvex; // the vertex which arc point to
nextarc;// point to the next arc ‘pointer
info; // the relative information of arc
adjvex nextarc info
顶点的结点结构 data firstarc
data; // the vertex’ information
firstarc; //point to the first arc which associate the vertex
The adjacency list of undirected graph
These edges come from the same vertex are in
the same list,Each list node is delegated a
certain edge(edge node),the node contain
another vertex‘ suffix--dest and pointer--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
The adjacency list and the inverse one of the
directed graph
A
B
C
data adj
A
B
C
0
1
2
dest link
dest link
adjacency list (out edge)
data adj
A
B
C
0
1
2
dest link
Retrorse one(in edge)
1
0 2
0
1
1
Adjacency list of Network
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
(adjacency list)(vertex list)
Linked list implementation of graph
#define MAX_VERTEX_NUM 20
typedef struct ArcNode {
int adjvex; // // the vertex which arc point to
struct ArcNode *nextarc;// point to the next arc ‘pointer
InfoType *info; //the relative information of arc
} ArcNode;
typedef struct VNode {
VertexType data; // the vertex’ information
ArcNode *firstarc; // point to the first arc which associate
the vertex
} VNode,AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjList vertices;
Int vexnum,arcnum;//number of vertex and edge in
the graph
Int kind;//sign of graph‘s type
}ALGraph;
typedef char VertexData; //data type of
vertex
typedef int EdgeData; //weight type of
edge
typedef struct node { //edge node
int dest; //suffix of target
vertex
EdgeData cost; //weight of edge
Struct node * link; //pointer of the next
edge
} EdgeNode;
Using adjacency list to define graph
typedef struct { //node of vertex
VertexData data; //data domain of vertex
EdgeNode * firstAdj; //head pointer of edge list
} VertexNode;
typedef struct { // adjacency list of graph
VertexNode VexList [NumVertices]; // adjacency
list
int n,e; //the number of vertex and edge
} AdjGraph;
The construction algorithm of adjacency list
void CreateGraph (AdjGraph G) {
cin >> G.n >> G.e; //input the number of vertex
and edge
for ( int i = 0; i < G.n; i++) {
cin >> G.VexList[i].data; //input the vertex’’s
information
G.VexList[i].firstAdj = NULL;
}
for ( i = 0; i < e; i++) { //input each edge
cin >> tail >> head >> weight;
EdgeNode * p = new EdgeNode;
p->dest = head; p->cost = weight;
//associate the head of the list(number tail)
p->link = G.VexList[tail].firstAdj;
G.VexList[tail].firstAdj = p;
p = new EdgeNode;
p->dest = tail; p->cost = weight;
//associate the head of the list(number head)
p->link = G.VexList[head].firstAdj;
G.VexList[head].firstAdj = p;
}
}
Start from a certain vertex to visit all of the
vertex in the graph,make sure each vertex can
only be visited one time,This process can be
called Traversing Graph
There may exist some loop in the graph and the
vertex may connect to each vertex,We may
return to the same vertex which once be visited
through some edges
In order to avoid this case,we can set an array
visited [ ] to sign if or not this vertex was once be
visited 。
§ 3 Traversing Graph
The original status of visited [ ] is 0,once
a vertex be visited,we set the value of
visited [i] to 1,to avoid the vertex be
visited one more times。
Two travesing method
Depth First Search
DFS (Depth First Search)
Breadth First Search
BFS (Breadth First Search)
DFS ( Depth First Search )
The process of Depth First Search
6
7
A
CD
E
G
B
F IH
A
CD
E
G
B
F IH
1 2 3
45
8 9
1 2 3
45
6
7
8 9
forward
backward
Tree of Depth First Search
After visiting certain initial vertex v in the graph,
DFS visits one of its neighbor vertexes w1,then
start from w1,it visits one of the neighbor vertexes
of w1 that has not been visited yet; then again start
from w2,……keep visiting with the same rule until
it arrives at the vertex u,all of whose neighbors
have been visited,Then go back to the vertex that
has just been visited and see if there are any other
connected vertexes that have not been visited,If
there is,visit it,then start form this vertex,keep
visiting as before,If there isn‘t,go back another
step to search,Repeat the process until all vertexes
in the connected graph have been visited,
arithmetic of Depth First Search
void Graph_Traverse (AdjGraph G) {
int * visited = new int [NumVertices];
for ( int i = 0; i < G.n; i++ )
visited [i] = 0; // The original status of visited [ ]
for ( int i = 0; i < G.n; i++ )
if ( ! visited[i] ) DFS (G,i,visited );
//start from vertex i
delete [ ] visited; //delete visited
}
void DFS (AdjGraph G,int v,int visited [ ] ) {
cout << GetValue (G,v) << ‘ ’; //visit vertex v
visited[v] = 1; //sign the vertex
int w = GetFirstNeighbor (G,v);
//get v’s first adjacent vertex named w
while ( w != -1 ) { //if w exist
if ( !visited[w] ) DFS (G,w,visited );
//if w haven’t be visited,visit it
w = GetNextNeighbor (G,v,w );
//get w
}
}
BFS ( Breadth First Search )
The process of 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
tree of Breadth First Search
I
After BFS has visited initial vertex v,it visits every
neighbor vertex w1,w2,…,w t,then again it visits
all neighbor vertexes of w1,w2,…,w t,which has
not been visited yet,And starting from these
vertexes,it visits their neighbors that haven‘t been
visited…,Keep doing this until all the vertexes in
the graph have been visited,
BFS is an layered search process,in which you can
visit a batch of vertexes in each step,Different
from DFS,there isn‘t backward steps,So BFS is
not a recursive process.
In order to implement layered visit,the algorithm uses a
queue to record vertexes in the current layer being visited
and also in the following layer which is convenient for the
following visit,
To avoid repeat visits,we need an accessorial array visited
[ ],which marks vertexes that have been visited.
Breath First Search algorithm of graph
void Graph_Traverse (AdjGraph G) {
‥‥‥‥‥
for ( int i = 0; i < G.n; i++ )
if ( ! visited[i] ) BFS (G,i,visited );
‥‥‥‥‥
}
void BFS (AdjGraph G,int v,int visited[ ] ) {
cout << GetValue (v) << ' '; visited[v] = 1;
Queue<int> q; InitQueue(&q);
EnQueue (&q,v); //进队列
while ( ! QueueEmpty (&q) ) { //队空搜索结束
DeQueue (&q,v);
int w = GetFirstNeighbor (G,v);
while ( w != -1 ) { //若邻接顶点 w 存在
if ( !visited[w] ) { //未访问过
cout << GetValue (w) << ‘ ’;
visited[w] = 1; EnQueue (&q,w);
}
w = GetNextNeighbor (G,v,w);
} //重复检测 v 的所有邻接顶点
} //外层循环，判队列空否
delete [ ] visited;
}
Connected component
When an undirected graph is an unconnected one,
if we start from a certain vertex and use DFS or BFS,
it is not possible to visit all the vertexes,We can
only visit all the vertexes in the biggest connected
sub-graph (connected component) 。
If we start from a vertex of each connected
component,we can get all the connected
component in undirected graph.
Connectivity problem of graph
The algorithm of getting connected component
needs to check every vertex in the graph,if one
vertex has been visited,then it must be in the
connected component we have got; if it has not
been visited yet,we can get another connected
component of the graph if we start visiting from
the vertex,
For unconnected undirected graph,all spanning
trees of connected components compose
unconnected spanning forest.
A
C D E IB
F OG
H
J
NML
K
Three Connected component
of undirected and unconnected graph
A H K
C D E IB
F OG J
NML
Minimum connected sub-graph of unconnected graph
Biconnected Component
In undirected connected graph G,v is called joint vertex if
and only if the graph is divided into two or more than two
connected components after v and all the vertexes
connected v in graph G is deleted.
Connected graph without joint vertex is called biconnected
graph.
In biconnected graph,there are at least two paths between
any pair of vertexes,The connectivity of graph is not
affected after certain vertex and edges incident with it is
deleted.
If a connected graph G is not a biconnected graph,it
consists of several biconnected component,。
Biconnected component in an undirected
connected graph G can be found using depth first
spanning tree.
The number of depth first marked next to the
vertexes in the graph gives the order of visit when
depth first search is processed.
The sufficient and necessary condition of the root
of depth first spanning tree is the joint vertex is
that it has at least two children,
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
根有两个子女关节点关节点关节点
A
B
C D
E
F
G
H
I J
A
B H
I
D F
B
C D
E
F
G
H
Connected graph and it’s connected component
Using a different method of traversing the map can
get a different spanning tree; Starting from a
different vertex,may also be different spanning
tree.
According to the definition of spanning tree,a
connected network with n vertexes,it's spanning
tree has n vertexes and n-1 edges.
The criteria of constructing a minimum cost
spanning tree
Must use and only use n-1 edges in this network
to link n vertices ；
Can not use the edge who can bring in a loop ；
Add the cost of every edge together and make
the sum minimum 。
§ 4 Minimum Spanning Tree
Prim algorithm
The basic idea of Prim algorithm,
Starting from a vertex u0 which is in the connected
network N={V,E}.choose the minimum cost edge
associated with N,as (uo,v),add its vertexes to the
spanning tree vertexes collection U.Then,in every
step,choose the minimum cost one from the edges
those one vertex is in collection U and the other one is
not in.Add their vertexes to the collection U.
Continue like this,until all the vertexes in this
network have already been added to the spanning
tree vertexes collection U.
Use Adjacency matrix as a storage of a graph 。
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
In the course of construction,also set up two auxiliary array,
lowcost[ ] store the current minimum cost of edges which
like one vertex in the spanning tree to the other vertex outside
the spanning tree ；
nearvex[ ] record the vertex in spanning tree,the distance
between it to vertex outside the spanning tree is the most
short.That means the minimum cost.
5
0
4
6
1
3
2
28
10
25
14
24
22
16
18 12
0241814
02510
2425022
1822012
12016
1416028
10280
If we start from vertex 0,that is u0=0,the
initial state of the two auxiliary array are:
then repeatedly to do the following work：
Choose the edge which meet the condition that
neravex[i]!=1 and lowcost[i] is smallest from
lowcost[],mark it with v,so the minimum cost
edge is(nearvex[v],v),the corresponding cost is
lowcost[v].
0 28 10?
-1 0 0 0 0 0 0
lowcost
nearvex
0 1 2 3 4 5 6
Change nearvex[v] to -1,that it has joined the
spanning tree vertexes collection.
Add the edge (nearvex[v],v,lowcost[v]) to the
spanning tree edges collection.
set lowcost[i] = min{ lowcost[i],Edge[v][i] }，
lowcost[i] is the shortest one of the distances
between vertex i which outside the spanning tree
and every vertex in the spanning tree,Edge[v][i]
is the distance between vertex i which outside the
spanning tree and vertex v which is a new one and
has just joined the collection,that is comparing
lowcost[i] and Edge[v][i],choosing the smaller one
as the shortest distance between the vertex outside
the collection and the vertex in the spanning tree.
set A as the distance between vertex i which comes
from the outside of the spanning tree vertexes
collection to the new vertex i which has just joined this
collection,set B as the shortest distance between vertex i
and each vertex in the spanning tree.If A is smaller
than B,change nearvex[i]:nearvex[i]=v.That means the
distance between vertex i which is outside the spanning
tree and the vertex v which is in the spanning tree is
the shortest,
0 28 10?
-1 0 0 0 0 0 0
lowcost
nearvex
0 1 2 3 4 5 6
choose v=5 choose edge (0,5)
Add the vertex v=5 to the spanning tree vertexes collection：
0 28 25 10?
-1 0 0 0 5 -1 0
lowcost
nearvex
0 1 2 3 4 5 6
choose v=4 edge(5,4)
5
0
4
6
1
3
2
28
10
25
14
24
22
16
18
Orginial graph add edge (0,5,10) to the spanning tree
12
0
4
6
1
3
2
10
25
5
0 1 2 3 4 5 6
Add the vertex v=4 to the spanning tree vertexes collection：
0 28? 22 25 10 24
-1 0 0 4 -1 -1 4
lowcost
nearvex
choose v=3 edge(4,3)
5
0
4
6
1
3
2
28
10
25
14
24
22
16
18 12 5
0
4
6
1
3
2
10
25
22
Orginial graph add edge (5,4,25) to the spanning tree
0 28 12 22 25 10 18
-1 0 3 -1 -1 -1 3
lowcost
nearvex
0 1 2 3 4 5 6
choose v=2 edge (3,2)
5
0
4
6
1
3
2
28
10
25
14
24
22
16
18 12 5
0
4
6
1
3
2
10
25
22
12
Add the vertex v=3 to the spanning tree vertexes collection：
Orginial graph add edge (4,3,22) to the spanning tree
lowcost
nearvex
0 1 2 3 4 5 6
0 16 12 22 25 10 18
-1 2 -1 -1 -1 -1 3
choose v=1 edge(2,1)
5
0
4
6
1
3
2
28
10
25
14
24
22
16
18 12 5
0
4
1
3
2
10
25
22
16
12
Add the vertex v=2 to the spanning tree vertexes collection：
Orginial graph add edge (3,2,12) to the spanning tree
0 16 12 22 25 10 14
-1 -1 -1 -1 -1 -1 1
lowcost
nearvex
0 1 2 3 4 5 6
choose v=6 edge(1,6)
5
0
4
6
1
3
2
28
10
25
14
24
22
16
18 12 5
0
4
6
1
3
2
10
25
14
22
16
12
Orginial graph add edge (2,1,16) to the spanning tree
Add the vertex v=1 to the spanning tree vertexes collection：
lowcost
nearvex
0 1 2 3 4 5 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 12 5
0
4
6
1
3
2
10
25
14
22
16
12
Add the vertex v=6 to the spanning tree vertexes collection：
Orginial graph add edge (1,6,14) to the spanning tree
Finally,the edges storaged in the spanning tree edges collection are,
(0,5,10),(5,4,25),(4,3,22),
(3,2,12),(2,1,16),(1,6,14)
Use Prim algorithm to construct a minimum cost
spanning tree:
void Prim ( Graph G,MST& T,int u ) {
float * lowcost = new float[NumVertices];
int * nearvex = new int[NumVertices];
for ( int i = 0; i < NumVertices; i++ ) {
lowcost[i] = G.Edge[u][i]; //Vu到各点代价
nearvex[i] = u; //及最短带权路径
}
nearvex[u] = -1; //加到生成树顶点集合
int k = 0; //存放最小生成树结点的变量
for ( i = 0; i < G.n; i++ )
if ( i != u ) { //循环 n-1次,加入 n-1条边
EdgeData min = MaxValue; int v = 0;
for ( int j = 0; j < NumVertices; j++ )
if ( nearvex[j] != -1 && // =-1不参选
lowcost[j] < min )
{ v = j; min = lowcost[j]; }
//求生成树外顶点到生成树内顶点具有最
//小权值的边,v是 当前具最小权值的边
if ( v ) { //v=0表示再也找不到要求顶点
T[k].tail = nearvex[v]; //选边加入生成树
T[k].head = v;
T[k++].cost = lowcost[v];
nearvex[v] = -1; //该边加入生成树标记
for ( j = 0; j < G.n; j++ )
if ( nearvex[j] != -1 &&
G.Edge[v][j] < lowcost[j] ) {
lowcost[j] = G.Edge[v][j]; //修改
nearvex[j] = v;
}
}
} //循环 n-1次,加入 n-1条边
}
Analysis of these algorithms,assume the
connected network has n vertexes,the time
complexity of this algorithm is O(n2).This
algorithm applies to the network which has a
lot of edges.
Note:When every edge has the same cost,the
spanning tree may not be the only because of
the arbitrary of the choice.
2,Kruskal‘s Algorithm – maintain a forest
void Kruskal ( Graph G )
{ T = { } ;
while ( T contains less than |V|?1 edges
&& E is not empty ) {
choose a least cost edge (v,w) from E ;
delete (v,w) from E ;
if ( (v,w) does not create a cycle in T )
add (v,w) to T ;
else
discard (v,w) ;
}
if ( T contains fewer than |V|?1 edges )
Error (,No spanning tree” ) ;
}
/* DeleteMin */
/* Union / Find */
A more detailed pseudocode is given by Figure 9.58 on p.321
T = O( |E| log |E| )
活动网络 (Activity Network)
计划、施工过程、生产流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分为若干个叫做“活动”的子工程。完成了这些活动，这个工程就可以完成了。
例如，计算机专业学生的学习就是一个工程
，每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。这样在有的课程之间有领先关系，有的课程可以并行地学习。
用顶点表示活动的网络 (AOV网络 )
§ 5 Topological Sort
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[ ],记录各顶点入度 。 入度为零的顶点即无前驱顶点 。
在输入数据前,顶点表 VexList[ ]和入度数组
count[ ]全部初始化 。 在输入数据时,每输入一条边 <j,k>,就需要建立一个边结点,并将它链入相应边链表中,统计入度信息：
EdgeNode * p = new EdgeNode;
p->dest = k; //建立边结点
p->link = G.VexList[j].firstAdj;
VexList[j].firstAdj = p;
//链入顶点 j 的边链表的前端
count[k]++; //顶点 k 入度加一
在算法中,使用一个存放入度为零的顶点的链式栈,供选择和输出无前驱的顶点。
拓扑排序算法可描述如下：
建立入度为零的顶点栈 ;
当入度为零的顶点栈不空时,重复执行
从顶点栈中退出一个顶点,并输出之 ;
从 AOV网络中删去这个顶点和它发出的边,边的终顶点入度减一 ;
如果边的终顶点入度减至 0,则该顶点进入度为零的顶点栈 ;
如果输出顶点个数少于 AOV网络的顶点个数,则报告网络中存在有向环。
拓扑排序的算法
void TopologicalSort (AdjGraph G) {
Stack S; StackEmpty(S); int j;
//入度为零的顶点栈初始化
for ( int i = 0; i < n; i++ ) //入度为零顶点
if ( count[i] == 0 ) Push(S,i); //进栈
for ( i = 0; i < n; i++ ) //期望输出 n 个顶点
if ( StackEmpty(S) ) { //中途栈空,转出
cout << ―网络中有回路！ " << endl;
return;
}
else { //继续拓扑排序
Pop( S,j ); //退栈
cout << j << endl; //输出
EdgeNode * p = VexList[j].firstAdj;
while ( p != NULL ) { //扫描出边表
int k = p->dest; //另一顶点
if ( --count[k] == 0 ) //顶点入度减一
Push( S,k );
//顶点的入度 减至零,进栈
p = p->link;
}
}
}
§ 5 Topological Sort
〖 Example〗 Courses needed for a computer science
degree at a hypothetical university
Co urs e n um ber Co urs e n ame Pr er equi si tes
C1 Pr og r amm i n g I No ne
C2 Di sc r ete M athe m a tic s No ne
C3 Da ta S truc t ur e C1,C2
C4 Calc ul us I No ne
C5 Calc ul us II C4
C6 L i near Al gebra C5
C7 An alysi s of Alg ori thms C3,C6
C8 Asse m bl y L angu ag e C3
C9 Ope ra ting S yste m s C7,C8
C1 0 Pr og r amm i n g L an gu a ges C7
C1 1 Com pi l er Desi g n C1 0
C1 2 Arti fic i al I ntel l i gence C7
C1 3 Com pu ta tiona l The or y C7
C1 4 Paral l el Al go ri thms C1 3
C1 5 Num er i cal Ana l y si s C6
AOV Network,:= digraph G in which V( G ) represents activities
( e.g,the courses ) and E( G ) represents precedence relations ( e.g,
means that C1 is a prerequisite course of C3 ).C1 C3
i is a predecessor of j,:= there is a path from i to j
i is an immediate predecessor of j,:= < i,j >? E( G )
Then j is called a successor ( immediate successor ) of i
Partial order,:= a precedence relation which is both transitive
( i? k,k? j? i? j ) and irreflexive ( i? i is impossible ).
Feasible AOV network must be a dag (directed acyclic graph).
Note,If the precedence relation is reflexive,then there must be an
i such that i is a predecessor of i,That is,i must be done
before i is started,Therefore if a project is feasible,it must
be irreflexive.
【 Definition】 A topological order is a linear ordering of the vertices of
a graph such that,for any two vertices,i,j,if i is a predecessor of j in the
network then i precedes j in the linear ordering.
〖 Example〗 One possible suggestion on course schedule for a
computer science degree could be:
C ourse num be r C ourse nam e P r er eq uisi te s
C1 P r og ram m ing I N one
C2 D iscr et e Ma th em atic s N one
C4 C alcul us I N one
C3 D ata S tr uc tu r e C 1,C 2
C5 C alcul us II C4
C6 Lin ear A lgebr a C5
C7 A nalysis of A lgo ri th m s C 3,C 6
C 15 N um er ic al A nalysis C6
C8 A ssem bly L ang uag e C3
C 10 P r og ram m ing Langua ges C7
C9 O pe rati ng S ys te m s C 7,C 8
C 12 A rt if ic ial Int el li gence C7
C 13 C om put ational The ory C7
C 1 1 C om pil er D esign C 10
C 14 P ara ll el A lgo ri th m s C 13
Note,The topological orders may not be unique for a network,
For example,there are several ways (topological orders) to
meet the degree requirements in computer science.
Goal Test an AOV for feasibility,and generate a topological order if possible.
void Topsort( Graph G )
{ int Counter;
Vertex V,W;
for ( Counter = 0; Counter < NumVertex; Counter ++ ) {
V = FindNewVertexOfDegreeZero( );
if ( V == NotAVertex ) {
Error (,Graph has a cycle” ); break; }
TopNum[ V ] = Counter; /* or output V */
for ( each W adjacent to V )
Indegree[ W ] – – ;
}
}
/* O( |V| ) */
T = O( |V|2 )
Improvement,Keep all the unassigned vertices of degree 0 in a special
box (queue or stack).
v1 v2
v6 v7
v3 v4 v5
void Topsort( Graph G )
{ Queue Q;
int Counter = 0;
Vertex V,W;
Q = CreateQueue( NumVertex ); MakeEmpty( Q );
for ( each vertex V )
if ( Indegree[ V ] == 0 ) Enqueue( V,Q );
while ( !IsEmpty( Q ) ) {
V = Dequeue( Q );
TopNum[ V ] = ++ Counter; /* assign next */
for ( each W adjacent to V )
if ( – – Indegree[ W ] == 0 ) Enqueue( W,Q );
} /* end-while */
if ( Counter != NumVertex )
Error(,Graph has a cycle” );
DisposeQueue( Q ); /* free memory */
}
0v1
Indegree
1v2
2v3
3v4
1v5
3v6
2v7
v1
0
v2
1
21
0 v5
0 v4
1
v6
0 v3
2
0
v7
10
T = O( |V| + |E| )
Mistakes in Fig 9.4 on
p.289
§ 6 用边表示活动的网络 (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
VVd u rjVem a xiVe
},),(][ {][ ji
j
VVd u rjVlm iniVl
这两个递推公式的计算必须分别在 拓扑有序及 逆拓扑有序 的前提下进行。
设 活动 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
事件 Ve[i] Vl[i]
V0 0 0
V1 6 6
V2 4 6
V3 5 8
V4 7 7
V5 7 10
V6 16 16
V7 14 14
V8 18 18
边 <0,1><0,2><0,3><1,4><2,4><3,5><4,6><4,7><5,7><6,8><7,8>
活动 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11
e 0 0 0 6 4 5 7 7 7 16 14
l 0 2 3 6 6 8 7 7 10 16 14
l - e 0 2 3 0 2 3 0 0 3 0 0
关键 是 是 是 是 是 是利用关键路径法求 AOE网的各关键活动
void graph::CriticalPath ( ) {
//在此算法中需要对邻接表中单链表的结点加以
//修改,在各结点中增加一个 int域 cost,记录该结
//点所表示的边上的权值 。
int i,j; int p,k; int e,l;
Ve = new int[n]; Vl = new int[n];
for ( i = 0; i < n; i++ ) Ve[i] = 0;//初始化
for ( i = 0; i < n; i++ ) {//顺向计算事件最早允许开始时间
Edge<int> *p = NodeTable[i].adj;//该顶点边链表链头指针 p
while ( p != NULL ) {//找所有后继邻接顶点
k = p→ dest;//i的后继邻接顶点 k
if ( Ve[i] + p→ cost > Ve[k] )
Ve[k] = Ve[i] + p→cost;
p = p→link; //找下一个后继
}
}
for ( i = 0; i < n; i++ ) Vl[i] = Ve[n-1];//逆向计算事件的最迟开始时间
for ( i = n-2; i; i-- ) {//按逆拓扑有序顺序处理
p = NodeTable[i].adj;//该顶点边链表链头指针 p
while ( p != NULL ) {
k = p→ dest; //i的后继邻接顶点 k
if ( Vl[k] - p→ cost < Vl[i])
Vl[i] = Vl[k] - p→ cost;
p = p→ link; //找下一个后继
}
}
for ( i = 0; i < n; i++ ) {//逐个顶点求各活动的 e[k]和 l[k]
p = NodeTable[i].adj; //该顶点边链表链头指针 p
while ( p != NULL ) {
k = p→ dest; //k是 i的后继邻接顶点
e = Ve[i]; l = Vl[k] - p→cost;
if ( l == e )/ /关键活动
cout << "<" << i << "," << k
<<,>” <<,是关键活动,<< endl;
p = p→ link; //找下一个后继
}
}
}
注意在拓扑排序求 Ve[i]和逆拓扑有序求 Vl[i]时,所需为
O(n+e),求各个活动的 e[k]和 l[k]时所需时间为
O(e),总 共花费时间仍然是 O(n+e)。
所有顶点按拓扑有序的次序编号
仅计算 Ve[i] 和 Vl[i] 是不够的，还须计算
e[k] 和 l[k]。
不是任一关键活动加速一定能使整个工程提前。
想使整个工程提前，要考虑各个关键路径上所有关键活动。
§ 6 Activity On Edges Net (AOE Net)
In the weighted directed graph without circles,if
we indicate the activity of project with a directed
edge (Activity),indicate the duration of activity
with the weight on the edge (Duration),indicate
the event with the point (Event),than such a
directed graph is called Activity On Edges Net
(AOE)。
AOE Net is very useful in some project evaluation,
For example,It let people know:
How much time will the whole project cost at
least (assuming there is no circle in the net)?
Which activities should be speeded up in order
to shorter the working period?
There‘s more than one path form the source points
to each point,so there‘s more than one path
between these points,It cost different time to
complete different path,but only all of the
activities in the path finished,the project can be
finished.
So,time we need to complete the whole project
depends on the longest path from the source point
to the end point,In other words,it‘s the total time
of the duration of all the activities in the path,The
longest path is called 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
Aiming at finding the critical path,first we must find
the critical activity,which would delay the whole
project if not completed in time.
All the activities in the critical path are critical
activities,It is to say,as long as we find the critical
activities,we get the critical path,For example,the
following graph is a AOE Net
Define some variables related to calculating
the critical activities:
① The earliest possible time for event Vi‘ beginning,Ve(i)
it‘s the longest path length from source point V0 to Vi 。
② The latest possible time for event Vi‘s beginning,Vl[i]
It‘s the latest permitting time for Vi‘s beginning in order
to make sure that the point Vn-1 can be finished at Ve[n-1],
③ The earliest possible time for activity ak?beginning,e[k]
Assuming activity ak is on the edge of < Vi,Vj >,than e[k]
is the longest path length form source point V0to point
Vi,So,
e[k] = Ve[i]
④ the latest permitting time for activity ak?beginningl[k]
l[k] is the the latest permitting time,without
duration delay,of the activity.
l[k] = Vl[j] - dur(<i,j>)。
here,dur(<i,j>) is the necessary time for finishing
ak.
⑤ Time margin,l[k] - e[k]
indicating the margin between the earliest possible
beginning time and the latest permitting beginning
time of activity,ak l[k] == e[k] indicates activity ak
is the critical activity with no margin time.
In order to find critical activities,we need calculate
e[k] and l[k] of each activity,than justify if l[k] ==
e[k]。
In order to get e[k] and l[k],we need to get Ve[i]
and Vl[i] from source point V0 to each point Vi,
The recurrence formulation for Ve[i]
From Ve[0] = 0,forward recurrence
< Vj,Vi >? S2,i = 1,2,?,n-1
S2 is the set containing all the directed edges < Vj,Vi
> pointing to Vi
From Vl[n-1] = Ve[n-1],backward recurrence
< Vi,Vj >? S1,i = n-2,n-3,?,0
S1 is the set containing all the directed edges < Vi,Vj
> starting from Vi
},),(][ {][ ijj VVd u rjVem a xiVe
},),(][ {][ jij VVd u rjVlm iniVl
Both recurrence formulations must be used only
when the topology ordered and anti-topology
ordered.
Assuming activity ak(k=1,2,…,e)is on the weighted
edge < Vi,Vj > 上,and its duration is indicated
bydur (<Vi,Vj >),So
e[k] = Ve[i]；
l[k] = Vl[j] - dur(<Vi,Vj >)； k = 1,2,…,e 。
Here,we get the algorithm of calculating critical path.
In order to simplify the algorithm,assume the
topology of each point was ready before our work,
and the points were numbered according the
consequence of topology.
1
3
2
4
a1=8
a2=12
5
6
7 8
a10=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
事件 Ve[i] Vl[i]
V0 0 0
V1 6 6
V2 4 6
V3 5 8
V4 7 7
V5 7 10
V6 16 16
V7 14 14
V8 18 18
边 <0,1><0,2><0,3><1,4><2,4><3,5><4,6><4,7><5,7><6,8><7,8>
活动 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11
e 0 0 0 6 4 5 7 7 7 16 14
l 0 2 3 6 6 8 7 7 10 16 14
l - e 0 2 3 0 2 3 0 0 3 0 0
关键 是 是 是 是 是 是
Find the critical activities in AOE Net with critical paths
void graph::CriticalPath ( ) {
//在此算法中需要对邻接表中单链表的结点加以
//修改,在各结点中增加一个 int域 cost,记录该结
//点所表示的边上的权值 。
int i,j; int p,k; int e,l;
Ve = new int[n]; Vl = new int[n];
for ( i = 0; i < n; i++ ) Ve[i] = 0;//初始化
for ( i = 0; i < n; i++ ) {//顺向计算事件最早允许开始时间
Edge<int> *p = NodeTable[i].adj;//该顶点边链表链头指针 p
while ( p != NULL ) {//找所有后继邻接顶点
k = p→dest;//i的后继邻接顶点 k
if ( Ve[i] + p→cost > Ve[k] )
Ve[k] = Ve[i] + p→cost;
p = p→link;//找下一个后继
}
}
for ( i = 0; i < n; i++ ) Vl[i] = Ve[n-1];//逆向计算事件的最迟开始时间
for ( i = n-2; i; i-- ) {//按逆拓扑有序顺序处理
p = NodeTable[i].adj; //该顶点边链表链头指针 p
while ( p != NULL ) {
k = p→dest; //i的后继邻接顶点 k
if ( Vl[k] - p→cost < Vl[i])
Vl[i] = Vl[k] - p→cost;
p = p→link; //找下一个后继
}
}
for ( i = 0; i < n; i++ ) {//逐个顶点求各活动的 e[k]和 l[k]
p = NodeTable[i].adj; //该顶点边链表链头指针 p
while ( p != NULL ) {
k = p→ dest; //k是 i的后继邻接顶点
e = Ve[i]; l = Vl[k] - p→cost;
if ( l == e )/ /关键活动
cout << "<" << i << "," << k
<<,>” <<,是关键活动,<< endl;
p = p→ link; //找下一个后继
}
}
}
Attention
The time complexity of getting Ve[i] topologically and
getting Vl[i] anti-topologically is O(n+e); the time
complexity of getting e[k] and l[k] of each activity isO(e),
so the total cost is still O(n+e)。
All the points is numbered according the topological
sequence.
It’s not enough to calculating Ve[i] and Vl[i],gettint e[k]
and l[k] is necessary.
Not any critical activity’s accelerating can lead to the
whole project’s accelerating.
If we want to finish the whole project advance,we must
think about all the critical activities in all the critical paths.
最短路径 (Shortest Path)
最短路径问题,如果从图中某一顶点 (称为源点 )到达另一顶点 (称为终点 )的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。
问题解法
边上权值非负情形的单源最短路径问题
— Dijkstra算法
边上权值为任意值的单源最短路径问题
— Bellman和 Ford算法
所有顶点之间的最短路径
— Floyd算法
§ 7 Shortest Path Algorithms
边上权值非负情形的单源最短路径问题
问题的提法,给定一个带权有向图 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 ← { v 0 };
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,则算法结束，否则转 ② 。
void ShortestPath (MTGraph G,int v ){
//MTGraph是一个有 n 个顶点的带权有向图,各边上的权值由 Edge[i][j]给出。
//dist[j],0? j<n,是当前求到的从顶点 v 到顶点 j 的最短路径长度,用数组 path[j],0? j<n,存放求到的最短路径。
EdgeData dist[G.n]; //最短路径长度数组
int path[G.n]; //最短路径数组
int S[G.n]; //最短路径顶点集计算从单个顶点到其它各顶点最短路径
for ( int i = 0; i < n; i++) {
dist[i] = G.Edge[v][i]; //dist数组初始化
S[i] = 0; //集合 S初始化
if ( i != v && dist[i] < MaxValue )
path[i] = v;
else path[i] = -1; //path数组初始化
}
S[v] = 1; dist[v] = 0; //顶点 v加入顶点集合
for ( i = 0; i < n-1; i++ ) {#//从顶点 v确定 n-1条路径
float min = MaxValue; int u = v;
for ( int j = 0; j < n; j++ ) //选当前不在集合 S中具有最
if ( !S[j] && dist[j] < min )短路径的顶点 u
{ u = j; min = dist[j]; }
S[u] = 1; //将顶点 u加入集合 S，表示它已在最短路径上
for ( int w = 0; w < n; w++ ) //修改
if (!S[w] && G.Edge[u][w] < MaxValue
&& dist[u] + G.Edge[u][w] < dist[w] ) {
//顶点 w未加入 S,且绕过 u可以缩短路径
dist[w] = dist[u] + G.Edge[u][w];
path[w] = u; //修改到 w的最短路径
}
}# //选定各顶点到顶点 v 的最短路径
}
//打印各顶点的最短路径,路径是逆向输出的
for ( i = 0; i < G.n; i++ ) {
cout << endl;
cout << ―Distance,‖ << dist[i]
<< ― Path,‖ << i;
//输出终点的最短路径长度和终点
int pre = path[i]; //取终点的直接前驱
while ( pre != v ) { //沿路径上溯输出
cout << ―,‖ << pre;
pre = path[pre];
}
}
§ 7 Shortest Path Algorithms
Given a digraph G = ( V,E ),and a cost function c( e )
for e? E( G ),The length of a path P from source to
destination is (also called weighted path length).
Pe
i
i
ec )(
1,Single-Source Shortest-Path Problem
Given as input a weighted graph,G = ( V,E ),and a
distinguished vertex,s,find the shortest weighted path
from s to every other vertex in G.
v1 v2
v6 v7
v3 v4 v5
2
4
2
1 3 10
2
5 8 4 6
1
v1 v2
v6 v7
v3 v4 v5
2
4
2
1
3
–10
2
5 8 4 6
1
Negative-cost
cycleNote,If there is no
negative-cost cycle,
the shortest path
from s to s is
defined to be zero.
Unweighted Shortest Paths
v1 v2
v6 v7
v3 v4 v50
0,? v3
1,? v1 and v6
1
1
2,? v2 and v4
2
2
3,? v5 and v7
3
3
Sketch of the idea
Breadth-first
search
Implementation
Table[ i ].Dist,:= distance from s to vi /* initialized to be? except
for s */
Table[ i ].Known,:= 1 if vi is checked; or 0 if not
Table[ i ].Path,:= for tracking the path /* initialized to be 0 */
void Unweighted( Table T )
{ int CurrDist;
Vertex V,W;
for ( CurrDist = 0; CurrDist < NumVertex; CurrDist ++ ) {
for ( each vertex V )
if ( !T[ V ].Known && T[ V ].Dist == CurrDist ) {
T[ V ].Known = true;
for ( each W adjacent to V )
if ( T[ W ].Dist == Infinity ) {
T[ W ].Dist = CurrDist + 1;
T[ W ].Path = V;
} /* end-if Dist == Infinity */
} /* end-if !Known && Dist == CurrDist */
} /* end-for CurrDist */
}
The worst case,v1v2v6v7 v3v4v5v9 v8
T = O( |V|2 )
If V is unknown
yet has Dist <
Infinity,then Dist
is either CurrDist
or CurrDist+1.
Improvement
void Unweighted( Table T )
{ /* T is initialized with the source vertex S given */
Queue Q;
Vertex V,W;
Q = CreateQueue (NumVertex ); MakeEmpty( Q );
Enqueue( S,Q ); /* Enqueue the source vertex */
while ( !IsEmpty( Q ) ) {
V = Dequeue( Q );
T[ V ].Known = true; /* not really necessary */
for ( each W adjacent to V )
if ( T[ W ].Dist == Infinity ) {
T[ W ].Dist = T[ V ].Dist + 1;
T[ W ].Path = V;
Enqueue( W,Q );
} /* end-if Dist == Infinity */
} /* end-while */
DisposeQueue( Q ); /* free memory */
}
v1 v2
v6 v7
v3 v4 v5
0
v1
Dist Path
v2
0v3
v4
v5
v6
v7
0
0
0
0
0
0
0 v
3
v71 v3
1
1 v3 v6
1
1
2
2
v1
v2
2
2
v1 v4
3
3
v2
v5
3
3
v4
T = O( |V| + |E| )
Dijkstra‘s Algorithm (for weighted shortest paths)
Let S = { s and vi‘s whose shortest paths have been found }
For any u? S,define distance [ u ] = minimal length of
path { s? ( vi? S )? u },If the paths are generated in
non-decreasing order,then
the shortest path must go through ONLY vi? S ;
u is chosen so that distance[ u ] = min{ w?S |
distance[ w ] } (If u is not unique,then we may select
any of them) ; /* Greedy Method */
if distance [ u1 ] < distance [ u2 ] and we add u1 into S,
then distance [ u2 ] may change,If so,a shorter path
from s to u2 must go through u1 and distance’ [ u2 ] =
distance [ u1 ] + length(< u1,u2>).
void Dijkstra( Table T )
{ /* T is initialized by Figure 9.30 on p.303 */
Vertex V,W;
for ( ; ; ) {
V = smallest unknown distance vertex;
if ( V == NotAVertex )
break;
T[ V ].Known = true;
for ( each W adjacent to V )
if ( !T[ W ].Known )
if ( T[ V ].Dist + Cvw < T[ W ].Dist ) {
Decrease( T[ W ].Dist to
T[ V ].Dist + Cvw );
T[ W ].Path = V;
} /* end-if update W */
} /* end-for( ; ; ) */
}
v1 v2
v6 v7
v3 v4 v5
2
4
2
1 3 10
2
5 8 4 6
1
0v1
Dist Path
v2
v3
v4
v5
v6
v7
0
0
0
0
0
0
0
2 v1
1 v1
3 v4
3 v4
9 v4
5 v4
8 36 7
/* not work for edge with negative cost */
Please read Figure 9.31 on p.304 for printing the path.
/* O( |V| ) */
Implementation 1
V = smallest unknown distance vertex;
/* simply scan the table – O( |V| ) */
T = O( |V|2 + |E| ) Good if the graph is dense
Implementation 2
V = smallest unknown distance vertex;
/* keep distances in a priority queue and call DeleteMin – O( log|V| ) */
Decrease( T[ W ].Dist to T[ V ].Dist + Cvw );
/* Method 1,DecreaseKey – O( log|V| ) */
T = O( |V| log|V| + |E| log|V| ) = O( |E| log|V| )
/* Method 2,insert W with updated Dist into the priority queue */
/* Must keep doing DeleteMin until an unknown vertex emerges */
Good if the
graph is sparse
T = O( |E| log|V| ) but requires |E| DeleteMin with |E| space
Other improvements,Pairing heap (Ch.12) and Fibonacci heap (Ch,11)
Graphs with Negative Edge Costs
void WeightedNegative( Table T )
{ /* T is initialized by Figure 9.30 on p.303 */
Queue Q;
Vertex V,W;
Q = CreateQueue (NumVertex ); MakeEmpty( Q );
Enqueue( S,Q ); /* Enqueue the source vertex */
while ( !IsEmpty( Q ) ) {
V = Dequeue( Q );
for ( each W adjacent to V )
if ( T[ V ].Dist + Cvw < T[ W ].Dist ) {
T[ W ].Dist = T[ V ].Dist + Cvw;
T[ W ].Path = V;
if ( W is not already in Q )
Enqueue( W,Q );
} /* end-if update */
} /* end-while */
DisposeQueue( Q ); /* free memory */
} /* negative-cost cycle will cause indefinite loop */
/* no longer once
per edge */
/* each vertex can dequeue at most |V|
times */
T = O( |V|? |E| )
Acyclic Graphs
If the graph is acyclic,vertices may be selected in topological order
since when a vertex is selected,its distance can no longer be lowered
without any incoming edges from unknown nodes.
T = O( |E| + |V| ) and no priority queue is needed.
Application,AOE ( Activity On Edge ) Networks
—— scheduling a project
vjai,:= activity Signals the completion of ai
EC[ j ] \ LC[ j ],:= the earliest \
latest completion time for node vj
CPM ( Critical Path Method ) Lasting Time
Slack Time
EC Time
LC Time
Index of vertex
〖 Example〗 AOE network of a hypothetical project
0
1
2
3
4
5
6
7
8
start
finish
a0=6
a1=4
a2=5
a3=1
a4=1
a5=2
a6=9
a7=7
a8=4
a9=2
a10=4
Calculation of EC,Start from v0,for any ai = <v,w>,we have
}][{m a x][,),( wvEwv CvECwEC
0
6
4
5
7
7
16
14
18
a11=0
Dummy activity
Calculation of LC,Start from the last vertex v8,for any ai = <v,
w>,we have
}][{m i n][,),( wvEwv CwLCvLC
18
16
14
7
75
6
6
0
Slack Time of <v,w> =
wvCvECwLC,][][
2
3
2
Critical Path,:= path consisting entirely of zero-slack edges.
2,All-Pairs Shortest Path Problem
For all pairs of vi and vj ( i? j ),find the shortest path
between.
Method 1 Use single-source algorithm for |V| times.
T = O( |V|3 ) – works fast on sparse graph.
Method 2 O( |V|3 ) algorithm given in Ch.10,works
faster on dense graphs.
§ 8Applications of Depth-First Search
/* a generalization of preorder traversal */
void DFS ( Vertex V ) /* this is only a template */
{ visited[ V ] = true; /* mark this vertex to avoid cycles */
for ( each W adjacent to V )
if ( !visited[ W ] )
DFS( W );
} /* T = O( |E| + |V| ) as long as adjacency lists are used */
0
1 2 3
4 5
6
DFS ( 0 )
1,Undirected Graphs
void ListComponents ( Graph G )
{ for ( each V in G )
if ( !visited[ V ] ) {
DFS( V );
printf(“\n“);
}
}
7
8
0 1 4 6 5 2 3
7 8
2,Biconnectivity
Articulation
point
Biconnected
graph
v is an articulation pointif G‘ = DeleteVertex( G,v ) has at least 2
connected components.
G is a biconnected graph if G is connected and has no articulation
points.
A biconnected component is a maximal biconnected subgraph.
〖 Example〗
0
1
2 3
4
8
7
5
6
9
Connected graph
0
1
1
2 3
4
3 5
8
7
7
5
6
7
9
Biconnected components
Note,No edges can
be shared by two or
more biconnected
components,Hence
E(G) is partitioned
by the biconnected
components of G.
Finding the biconnected components of a connected undirected G
0
1
2 3
4
8
7
5
6
9
Use depth first search to obtain a spanning tree of G
DFS ( 3 )
0
1
2
3
4
5
6
7
89
Depth first spanning tree
3
4 5
2
1
0
6
7
9 8
0
1
2
3
4
5
6
7
8 9
Depth first
number (Num)
Find the articulation points in G
The root is an articulation point iff it has at least 2 children
Any other vertex u is an articulation point iff u has at least 1
child,and it is impossible to move down at least 1 step and
then jump up to u’s ancestor.
Back edges
::= (u,v)? tree
and u (or v) is
an ancestor of
v (or u).
Note,If u is an
ancestor of v,
then Num( u )
< Num( v ).
3
4 5
2
1
0
6
7
9 8
0
1
2
3
4
5
6
7
8 9
}}e d g e b a c k a is ),(|)(m i n {
},of c h i l d a is |)(m i n {
),(m i n {)(
wuwN u m
uwwL o w
uN u muL o w?
vertex
Num
Low
0 1 2 3 4 5 6 7 8 9
4 3 2 0 1 5 6 7 9 8
00 54 0 0 55 9 8
Therefore,u is an articulation point iff
(1) u is the root and has at least 2 children; or
(2) u is not the root,and has at least 1 child such that
Low( child )? Num( u ).
Please read the pseudocodes on p.327 and p.329 for more details.
3,Euler Circuits
Draw each line exactly once without lifting your pen from the
paper – Euler tour
Draw each line exactly once without lifting your pen from the
paper,AND finish at the starting point – Euler curcuit
〖 Proposition〗 An Euler circuit is possible only if the graph is
connected and each vertex has an even degree.
〖 Proposition〗 An Euler tour is possible if there are exactly two
vertices having odd degree,One must start at one of the odd-degree
vertices.
2
6
98
3
7
1
12
4
10
5
11
Note:
The path should be maintained as a linked list.
For each adjacency list,maintain a pointer to the last edge
scanned.
T = O( |E| + |V| )
Find a simple cycle in an undirected graph that visits every
vertex – Hamilton cycle
DFS
GRAPH ALGORITHMS § 1 Definitions
G( V,E ) where G,:= graph,V = V( G ),:= finite nonempty set of
vertices,and E = E( G ),:= finite set of edges.
Undirected graph,( vi,vj ) = ( vj,vi ),:= the same edge.
Directed graph (digraph),< vi,vj >,:=? < vj,vi >vi vj
tail head
Restrictions,
(1) Self loop is illegal.
(2) Multigraph is not considered
0 1 0
1 2
Complete graph,a graph that has the maximum number of edges
0
2
1 3
2
)1(2 E of #
V of #
nn
nC
n
0
2
1 3
)1( E of #
V of #
2
nnP
n
n
vi vj? vi and vj are adjacent ;
( vi,vj ) is incident on vi and vj
vi vj? vi is adjacent to vj ; vj is adjacent from vi ;
< vi,vj > is incident on vi and vj
Subgraph G‘? G,:= V( G‘ )? V( G ) && E( G‘ )? E( G )
Path (? G) from vp to vq,:= { vp,vi1,vi2,,vin,vq } such that ( vp,vi1 ),
( vi1,vi2 ),,( vin,vq ) or < vp,vi1 >,,< vin,vq > belong to E( G )
Length of a path,:= number of edges on the path
Simple path,:= vi1,vi2,,vin are distinct
Cycle,:= simple path with vp = vq
vi and vj in an undirected G are connected if there is a path from vi to vj
(and hence there is also a path from vj to vi)
An undirected graph G is connected if every pair of distinct vi and vj are
connected
(Connected) Component of an undirected G,:= the maximal connected
subgraph
A tree,:= a graph that is connected and acyclic
Strongly connected directed graph G,:= for every pair of vi and vj in
V( G ),there exist directed paths from vi to vj and from vj to vi,If the
graph is connected without direction to the edges,then it is said to be
weakly connected
Strongly connected component,:= the maximal subgraph that is
strongly connected
Degree( v ),:= number of edges incident to v,For a directed G,we have
in-degree and out-degree,For example:
v in-degree(v) = 3; out-degree(v) = 1; degree(v) = 4
Given G with n vertices and e edges,then
)(d e g r e e w h e r e 2
1
0
ii
n
i
i vdde
A DAG,:= a directed acyclic graph
To describe the Adjacency Matrix of the
graph,we need a table to record the
information of each vertex and an Adjacency
Matrix contains the relations among each
vertex,
Suppose that A = (V,E) is a graphg includes n
vertex,the graph‘s Adjacency Matrix is a two
dimensional array A.edge[n][n],
Adjacency Matrix
e l s e,
),(,if,
]][[,
or
0
><1
A
EjiEji
jiE d g e
§ 2 The structure of graph‘s storage
The adjacency matrix of non-directional graph is
symmetrical
The adjacency matrix of directional graph is not always
symmetrical
0
1 2
3
0101
1010
0101
1010
A,e dg e
0
1
2?
000
101
010
A,e d g e
Among the directed graph,compute the
number of 1 on line i,can get the vertex i‘s
outdegree,Compute the number of 1 on
row i,can get the vertex i‘s indegree.
As for the undirected graph,Compute the
number of 1 on row i,can get the vertex i‘s
degree.
1
8
6
3 29 5
4
2
0
3
1
06
8053
290
410
A,e d g e
Adjacency Matrix in the network
ji
ji,ji,ji
ji,ji,j iji
ji
if
orand if
or andif
,
)(,
)(),,(
]][[
0
E E
EEW
A,e d g e
#define MaxValue Int_Max //在 <limits.h>中
const int NumEdges = 50; //edges’ number
const int NumVertices = 10; // vertex’s number
typedef char VertexData; // vertex’s data type
typedef int EdgeData; // Edge’s weight
typedef struct {
VertexData vexList[NumVertices]; //vertex table
EdgeData Edge[NumVertices][NumVertices];
//adjacency can be treat as the edge’ relation
int n,e; //the number of the vertex and edge
} MTGraph;
using Adjacency Matrix to define the graph
Adjacency List
Adjacency List,A list type of storage structure。
The structure of arc
adjvex; // the vertex which arc point to
nextarc;// point to the next arc ‘pointer
info; // the relative information of arc
adjvex nextarc info
顶点的结点结构 data firstarc
data; // the vertex’ information
firstarc; //point to the first arc which associate the vertex
The adjacency list of undirected graph
These edges come from the same vertex are in
the same list,Each list node is delegated a
certain edge(edge node),the node contain
another vertex‘ suffix--dest and pointer--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
The adjacency list and the inverse one of the
directed graph
A
B
C
data adj
A
B
C
0
1
2
dest link
dest link
adjacency list (out edge)
data adj
A
B
C
0
1
2
dest link
Retrorse one(in edge)
1
0 2
0
1
1
Adjacency list of Network
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
(adjacency list)(vertex list)
Linked list implementation of graph
#define MAX_VERTEX_NUM 20
typedef struct ArcNode {
int adjvex; // // the vertex which arc point to
struct ArcNode *nextarc;// point to the next arc ‘pointer
InfoType *info; //the relative information of arc
} ArcNode;
typedef struct VNode {
VertexType data; // the vertex’ information
ArcNode *firstarc; // point to the first arc which associate
the vertex
} VNode,AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjList vertices;
Int vexnum,arcnum;//number of vertex and edge in
the graph
Int kind;//sign of graph‘s type
}ALGraph;
typedef char VertexData; //data type of
vertex
typedef int EdgeData; //weight type of
edge
typedef struct node { //edge node
int dest; //suffix of target
vertex
EdgeData cost; //weight of edge
Struct node * link; //pointer of the next
edge
} EdgeNode;
Using adjacency list to define graph
typedef struct { //node of vertex
VertexData data; //data domain of vertex
EdgeNode * firstAdj; //head pointer of edge list
} VertexNode;
typedef struct { // adjacency list of graph
VertexNode VexList [NumVertices]; // adjacency
list
int n,e; //the number of vertex and edge
} AdjGraph;
The construction algorithm of adjacency list
void CreateGraph (AdjGraph G) {
cin >> G.n >> G.e; //input the number of vertex
and edge
for ( int i = 0; i < G.n; i++) {
cin >> G.VexList[i].data; //input the vertex’’s
information
G.VexList[i].firstAdj = NULL;
}
for ( i = 0; i < e; i++) { //input each edge
cin >> tail >> head >> weight;
EdgeNode * p = new EdgeNode;
p->dest = head; p->cost = weight;
//associate the head of the list(number tail)
p->link = G.VexList[tail].firstAdj;
G.VexList[tail].firstAdj = p;
p = new EdgeNode;
p->dest = tail; p->cost = weight;
//associate the head of the list(number head)
p->link = G.VexList[head].firstAdj;
G.VexList[head].firstAdj = p;
}
}
Start from a certain vertex to visit all of the
vertex in the graph,make sure each vertex can
only be visited one time,This process can be
called Traversing Graph
There may exist some loop in the graph and the
vertex may connect to each vertex,We may
return to the same vertex which once be visited
through some edges
In order to avoid this case,we can set an array
visited [ ] to sign if or not this vertex was once be
visited 。
§ 3 Traversing Graph
The original status of visited [ ] is 0,once
a vertex be visited,we set the value of
visited [i] to 1,to avoid the vertex be
visited one more times。
Two travesing method
Depth First Search
DFS (Depth First Search)
Breadth First Search
BFS (Breadth First Search)
DFS ( Depth First Search )
The process of Depth First Search
6
7
A
CD
E
G
B
F IH
A
CD
E
G
B
F IH
1 2 3
45
8 9
1 2 3
45
6
7
8 9
forward
backward
Tree of Depth First Search
After visiting certain initial vertex v in the graph,
DFS visits one of its neighbor vertexes w1,then
start from w1,it visits one of the neighbor vertexes
of w1 that has not been visited yet; then again start
from w2,……keep visiting with the same rule until
it arrives at the vertex u,all of whose neighbors
have been visited,Then go back to the vertex that
has just been visited and see if there are any other
connected vertexes that have not been visited,If
there is,visit it,then start form this vertex,keep
visiting as before,If there isn‘t,go back another
step to search,Repeat the process until all vertexes
in the connected graph have been visited,
arithmetic of Depth First Search
void Graph_Traverse (AdjGraph G) {
int * visited = new int [NumVertices];
for ( int i = 0; i < G.n; i++ )
visited [i] = 0; // The original status of visited [ ]
for ( int i = 0; i < G.n; i++ )
if ( ! visited[i] ) DFS (G,i,visited );
//start from vertex i
delete [ ] visited; //delete visited
}
void DFS (AdjGraph G,int v,int visited [ ] ) {
cout << GetValue (G,v) << ‘ ’; //visit vertex v
visited[v] = 1; //sign the vertex
int w = GetFirstNeighbor (G,v);
//get v’s first adjacent vertex named w
while ( w != -1 ) { //if w exist
if ( !visited[w] ) DFS (G,w,visited );
//if w haven’t be visited,visit it
w = GetNextNeighbor (G,v,w );
//get w
}
}
BFS ( Breadth First Search )
The process of 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
tree of Breadth First Search
I
After BFS has visited initial vertex v,it visits every
neighbor vertex w1,w2,…,w t,then again it visits
all neighbor vertexes of w1,w2,…,w t,which has
not been visited yet,And starting from these
vertexes,it visits their neighbors that haven‘t been
visited…,Keep doing this until all the vertexes in
the graph have been visited,
BFS is an layered search process,in which you can
visit a batch of vertexes in each step,Different
from DFS,there isn‘t backward steps,So BFS is
not a recursive process.
In order to implement layered visit,the algorithm uses a
queue to record vertexes in the current layer being visited
and also in the following layer which is convenient for the
following visit,
To avoid repeat visits,we need an accessorial array visited
[ ],which marks vertexes that have been visited.
Breath First Search algorithm of graph
void Graph_Traverse (AdjGraph G) {
‥‥‥‥‥
for ( int i = 0; i < G.n; i++ )
if ( ! visited[i] ) BFS (G,i,visited );
‥‥‥‥‥
}
void BFS (AdjGraph G,int v,int visited[ ] ) {
cout << GetValue (v) << ' '; visited[v] = 1;
Queue<int> q; InitQueue(&q);
EnQueue (&q,v); //进队列
while ( ! QueueEmpty (&q) ) { //队空搜索结束
DeQueue (&q,v);
int w = GetFirstNeighbor (G,v);
while ( w != -1 ) { //若邻接顶点 w 存在
if ( !visited[w] ) { //未访问过
cout << GetValue (w) << ‘ ’;
visited[w] = 1; EnQueue (&q,w);
}
w = GetNextNeighbor (G,v,w);
} //重复检测 v 的所有邻接顶点
} //外层循环，判队列空否
delete [ ] visited;
}
Connected component
When an undirected graph is an unconnected one,
if we start from a certain vertex and use DFS or BFS,
it is not possible to visit all the vertexes,We can
only visit all the vertexes in the biggest connected
sub-graph (connected component) 。
If we start from a vertex of each connected
component,we can get all the connected
component in undirected graph.
Connectivity problem of graph
The algorithm of getting connected component
needs to check every vertex in the graph,if one
vertex has been visited,then it must be in the
connected component we have got; if it has not
been visited yet,we can get another connected
component of the graph if we start visiting from
the vertex,
For unconnected undirected graph,all spanning
trees of connected components compose
unconnected spanning forest.
A
C D E IB
F OG
H
J
NML
K
Three Connected component
of undirected and unconnected graph
A H K
C D E IB
F OG J
NML
Minimum connected sub-graph of unconnected graph
Biconnected Component
In undirected connected graph G,v is called joint vertex if
and only if the graph is divided into two or more than two
connected components after v and all the vertexes
connected v in graph G is deleted.
Connected graph without joint vertex is called biconnected
graph.
In biconnected graph,there are at least two paths between
any pair of vertexes,The connectivity of graph is not
affected after certain vertex and edges incident with it is
deleted.
If a connected graph G is not a biconnected graph,it
consists of several biconnected component,。
Biconnected component in an undirected
connected graph G can be found using depth first
spanning tree.
The number of depth first marked next to the
vertexes in the graph gives the order of visit when
depth first search is processed.
The sufficient and necessary condition of the root
of depth first spanning tree is the joint vertex is
that it has at least two children,
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
根有两个子女关节点关节点关节点
A
B
C D
E
F
G
H
I J
A
B H
I
D F
B
C D
E
F
G
H
Connected graph and it’s connected component
Using a different method of traversing the map can
get a different spanning tree; Starting from a
different vertex,may also be different spanning
tree.
According to the definition of spanning tree,a
connected network with n vertexes,it's spanning
tree has n vertexes and n-1 edges.
The criteria of constructing a minimum cost
spanning tree
Must use and only use n-1 edges in this network
to link n vertices ；
Can not use the edge who can bring in a loop ；
Add the cost of every edge together and make
the sum minimum 。
§ 4 Minimum Spanning Tree
Prim algorithm
The basic idea of Prim algorithm,
Starting from a vertex u0 which is in the connected
network N={V,E}.choose the minimum cost edge
associated with N,as (uo,v),add its vertexes to the
spanning tree vertexes collection U.Then,in every
step,choose the minimum cost one from the edges
those one vertex is in collection U and the other one is
not in.Add their vertexes to the collection U.
Continue like this,until all the vertexes in this
network have already been added to the spanning
tree vertexes collection U.
Use Adjacency matrix as a storage of a graph 。
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
In the course of construction,also set up two auxiliary array,
lowcost[ ] store the current minimum cost of edges which
like one vertex in the spanning tree to the other vertex outside
the spanning tree ；
nearvex[ ] record the vertex in spanning tree,the distance
between it to vertex outside the spanning tree is the most
short.That means the minimum cost.
5
0
4
6
1
3
2
28
10
25
14
24
22
16
18 12
0241814
02510
2425022
1822012
12016
1416028
10280
If we start from vertex 0,that is u0=0,the
initial state of the two auxiliary array are:
then repeatedly to do the following work：
Choose the edge which meet the condition that
neravex[i]!=1 and lowcost[i] is smallest from
lowcost[],mark it with v,so the minimum cost
edge is(nearvex[v],v),the corresponding cost is
lowcost[v].
0 28 10?
-1 0 0 0 0 0 0
lowcost
nearvex
0 1 2 3 4 5 6
Change nearvex[v] to -1,that it has joined the
spanning tree vertexes collection.
Add the edge (nearvex[v],v,lowcost[v]) to the
spanning tree edges collection.
set lowcost[i] = min{ lowcost[i],Edge[v][i] }，
lowcost[i] is the shortest one of the distances
between vertex i which outside the spanning tree
and every vertex in the spanning tree,Edge[v][i]
is the distance between vertex i which outside the
spanning tree and vertex v which is a new one and
has just joined the collection,that is comparing
lowcost[i] and Edge[v][i],choosing the smaller one
as the shortest distance between the vertex outside
the collection and the vertex in the spanning tree.
set A as the distance between vertex i which comes
from the outside of the spanning tree vertexes
collection to the new vertex i which has just joined this
collection,set B as the shortest distance between vertex i
and each vertex in the spanning tree.If A is smaller
than B,change nearvex[i]:nearvex[i]=v.That means the
distance between vertex i which is outside the spanning
tree and the vertex v which is in the spanning tree is
the shortest,
0 28 10?
-1 0 0 0 0 0 0
lowcost
nearvex
0 1 2 3 4 5 6
choose v=5 choose edge (0,5)
Add the vertex v=5 to the spanning tree vertexes collection：
0 28 25 10?
-1 0 0 0 5 -1 0
lowcost
nearvex
0 1 2 3 4 5 6
choose v=4 edge(5,4)
5
0
4
6
1
3
2
28
10
25
14
24
22
16
18
Orginial graph add edge (0,5,10) to the spanning tree
12
0
4
6
1
3
2
10
25
5
0 1 2 3 4 5 6
Add the vertex v=4 to the spanning tree vertexes collection：
0 28? 22 25 10 24
-1 0 0 4 -1 -1 4
lowcost
nearvex
choose v=3 edge(4,3)
5
0
4
6
1
3
2
28
10
25
14
24
22
16
18 12 5
0
4
6
1
3
2
10
25
22
Orginial graph add edge (5,4,25) to the spanning tree
0 28 12 22 25 10 18
-1 0 3 -1 -1 -1 3
lowcost
nearvex
0 1 2 3 4 5 6
choose v=2 edge (3,2)
5
0
4
6
1
3
2
28
10
25
14
24
22
16
18 12 5
0
4
6
1
3
2
10
25
22
12
Add the vertex v=3 to the spanning tree vertexes collection：
Orginial graph add edge (4,3,22) to the spanning tree
lowcost
nearvex
0 1 2 3 4 5 6
0 16 12 22 25 10 18
-1 2 -1 -1 -1 -1 3
choose v=1 edge(2,1)
5
0
4
6
1
3
2
28
10
25
14
24
22
16
18 12 5
0
4
1
3
2
10
25
22
16
12
Add the vertex v=2 to the spanning tree vertexes collection：
Orginial graph add edge (3,2,12) to the spanning tree
0 16 12 22 25 10 14
-1 -1 -1 -1 -1 -1 1
lowcost
nearvex
0 1 2 3 4 5 6
choose v=6 edge(1,6)
5
0
4
6
1
3
2
28
10
25
14
24
22
16
18 12 5
0
4
6
1
3
2
10
25
14
22
16
12
Orginial graph add edge (2,1,16) to the spanning tree
Add the vertex v=1 to the spanning tree vertexes collection：
lowcost
nearvex
0 1 2 3 4 5 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 12 5
0
4
6
1
3
2
10
25
14
22
16
12
Add the vertex v=6 to the spanning tree vertexes collection：
Orginial graph add edge (1,6,14) to the spanning tree
Finally,the edges storaged in the spanning tree edges collection are,
(0,5,10),(5,4,25),(4,3,22),
(3,2,12),(2,1,16),(1,6,14)
Use Prim algorithm to construct a minimum cost
spanning tree:
void Prim ( Graph G,MST& T,int u ) {
float * lowcost = new float[NumVertices];
int * nearvex = new int[NumVertices];
for ( int i = 0; i < NumVertices; i++ ) {
lowcost[i] = G.Edge[u][i]; //Vu到各点代价
nearvex[i] = u; //及最短带权路径
}
nearvex[u] = -1; //加到生成树顶点集合
int k = 0; //存放最小生成树结点的变量
for ( i = 0; i < G.n; i++ )
if ( i != u ) { //循环 n-1次,加入 n-1条边
EdgeData min = MaxValue; int v = 0;
for ( int j = 0; j < NumVertices; j++ )
if ( nearvex[j] != -1 && // =-1不参选
lowcost[j] < min )
{ v = j; min = lowcost[j]; }
//求生成树外顶点到生成树内顶点具有最
//小权值的边,v是 当前具最小权值的边
if ( v ) { //v=0表示再也找不到要求顶点
T[k].tail = nearvex[v]; //选边加入生成树
T[k].head = v;
T[k++].cost = lowcost[v];
nearvex[v] = -1; //该边加入生成树标记
for ( j = 0; j < G.n; j++ )
if ( nearvex[j] != -1 &&
G.Edge[v][j] < lowcost[j] ) {
lowcost[j] = G.Edge[v][j]; //修改
nearvex[j] = v;
}
}
} //循环 n-1次,加入 n-1条边
}
Analysis of these algorithms,assume the
connected network has n vertexes,the time
complexity of this algorithm is O(n2).This
algorithm applies to the network which has a
lot of edges.
Note:When every edge has the same cost,the
spanning tree may not be the only because of
the arbitrary of the choice.
2,Kruskal‘s Algorithm – maintain a forest
void Kruskal ( Graph G )
{ T = { } ;
while ( T contains less than |V|?1 edges
&& E is not empty ) {
choose a least cost edge (v,w) from E ;
delete (v,w) from E ;
if ( (v,w) does not create a cycle in T )
add (v,w) to T ;
else
discard (v,w) ;
}
if ( T contains fewer than |V|?1 edges )
Error (,No spanning tree” ) ;
}
/* DeleteMin */
/* Union / Find */
A more detailed pseudocode is given by Figure 9.58 on p.321
T = O( |E| log |E| )
活动网络 (Activity Network)
计划、施工过程、生产流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分为若干个叫做“活动”的子工程。完成了这些活动，这个工程就可以完成了。
例如，计算机专业学生的学习就是一个工程
，每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。这样在有的课程之间有领先关系，有的课程可以并行地学习。
用顶点表示活动的网络 (AOV网络 )
§ 5 Topological Sort
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[ ],记录各顶点入度 。 入度为零的顶点即无前驱顶点 。
在输入数据前,顶点表 VexList[ ]和入度数组
count[ ]全部初始化 。 在输入数据时,每输入一条边 <j,k>,就需要建立一个边结点,并将它链入相应边链表中,统计入度信息：
EdgeNode * p = new EdgeNode;
p->dest = k; //建立边结点
p->link = G.VexList[j].firstAdj;
VexList[j].firstAdj = p;
//链入顶点 j 的边链表的前端
count[k]++; //顶点 k 入度加一
在算法中,使用一个存放入度为零的顶点的链式栈,供选择和输出无前驱的顶点。
拓扑排序算法可描述如下：
建立入度为零的顶点栈 ;
当入度为零的顶点栈不空时,重复执行
从顶点栈中退出一个顶点,并输出之 ;
从 AOV网络中删去这个顶点和它发出的边,边的终顶点入度减一 ;
如果边的终顶点入度减至 0,则该顶点进入度为零的顶点栈 ;
如果输出顶点个数少于 AOV网络的顶点个数,则报告网络中存在有向环。
拓扑排序的算法
void TopologicalSort (AdjGraph G) {
Stack S; StackEmpty(S); int j;
//入度为零的顶点栈初始化
for ( int i = 0; i < n; i++ ) //入度为零顶点
if ( count[i] == 0 ) Push(S,i); //进栈
for ( i = 0; i < n; i++ ) //期望输出 n 个顶点
if ( StackEmpty(S) ) { //中途栈空,转出
cout << ―网络中有回路！ " << endl;
return;
}
else { //继续拓扑排序
Pop( S,j ); //退栈
cout << j << endl; //输出
EdgeNode * p = VexList[j].firstAdj;
while ( p != NULL ) { //扫描出边表
int k = p->dest; //另一顶点
if ( --count[k] == 0 ) //顶点入度减一
Push( S,k );
//顶点的入度 减至零,进栈
p = p->link;
}
}
}
§ 5 Topological Sort
〖 Example〗 Courses needed for a computer science
degree at a hypothetical university
Co urs e n um ber Co urs e n ame Pr er equi si tes
C1 Pr og r amm i n g I No ne
C2 Di sc r ete M athe m a tic s No ne
C3 Da ta S truc t ur e C1,C2
C4 Calc ul us I No ne
C5 Calc ul us II C4
C6 L i near Al gebra C5
C7 An alysi s of Alg ori thms C3,C6
C8 Asse m bl y L angu ag e C3
C9 Ope ra ting S yste m s C7,C8
C1 0 Pr og r amm i n g L an gu a ges C7
C1 1 Com pi l er Desi g n C1 0
C1 2 Arti fic i al I ntel l i gence C7
C1 3 Com pu ta tiona l The or y C7
C1 4 Paral l el Al go ri thms C1 3
C1 5 Num er i cal Ana l y si s C6
AOV Network,:= digraph G in which V( G ) represents activities
( e.g,the courses ) and E( G ) represents precedence relations ( e.g,
means that C1 is a prerequisite course of C3 ).C1 C3
i is a predecessor of j,:= there is a path from i to j
i is an immediate predecessor of j,:= < i,j >? E( G )
Then j is called a successor ( immediate successor ) of i
Partial order,:= a precedence relation which is both transitive
( i? k,k? j? i? j ) and irreflexive ( i? i is impossible ).
Feasible AOV network must be a dag (directed acyclic graph).
Note,If the precedence relation is reflexive,then there must be an
i such that i is a predecessor of i,That is,i must be done
before i is started,Therefore if a project is feasible,it must
be irreflexive.
【 Definition】 A topological order is a linear ordering of the vertices of
a graph such that,for any two vertices,i,j,if i is a predecessor of j in the
network then i precedes j in the linear ordering.
〖 Example〗 One possible suggestion on course schedule for a
computer science degree could be:
C ourse num be r C ourse nam e P r er eq uisi te s
C1 P r og ram m ing I N one
C2 D iscr et e Ma th em atic s N one
C4 C alcul us I N one
C3 D ata S tr uc tu r e C 1,C 2
C5 C alcul us II C4
C6 Lin ear A lgebr a C5
C7 A nalysis of A lgo ri th m s C 3,C 6
C 15 N um er ic al A nalysis C6
C8 A ssem bly L ang uag e C3
C 10 P r og ram m ing Langua ges C7
C9 O pe rati ng S ys te m s C 7,C 8
C 12 A rt if ic ial Int el li gence C7
C 13 C om put ational The ory C7
C 1 1 C om pil er D esign C 10
C 14 P ara ll el A lgo ri th m s C 13
Note,The topological orders may not be unique for a network,
For example,there are several ways (topological orders) to
meet the degree requirements in computer science.
Goal Test an AOV for feasibility,and generate a topological order if possible.
void Topsort( Graph G )
{ int Counter;
Vertex V,W;
for ( Counter = 0; Counter < NumVertex; Counter ++ ) {
V = FindNewVertexOfDegreeZero( );
if ( V == NotAVertex ) {
Error (,Graph has a cycle” ); break; }
TopNum[ V ] = Counter; /* or output V */
for ( each W adjacent to V )
Indegree[ W ] – – ;
}
}
/* O( |V| ) */
T = O( |V|2 )
Improvement,Keep all the unassigned vertices of degree 0 in a special
box (queue or stack).
v1 v2
v6 v7
v3 v4 v5
void Topsort( Graph G )
{ Queue Q;
int Counter = 0;
Vertex V,W;
Q = CreateQueue( NumVertex ); MakeEmpty( Q );
for ( each vertex V )
if ( Indegree[ V ] == 0 ) Enqueue( V,Q );
while ( !IsEmpty( Q ) ) {
V = Dequeue( Q );
TopNum[ V ] = ++ Counter; /* assign next */
for ( each W adjacent to V )
if ( – – Indegree[ W ] == 0 ) Enqueue( W,Q );
} /* end-while */
if ( Counter != NumVertex )
Error(,Graph has a cycle” );
DisposeQueue( Q ); /* free memory */
}
0v1
Indegree
1v2
2v3
3v4
1v5
3v6
2v7
v1
0
v2
1
21
0 v5
0 v4
1
v6
0 v3
2
0
v7
10
T = O( |V| + |E| )
Mistakes in Fig 9.4 on
p.289
§ 6 用边表示活动的网络 (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
VVd u rjVem a xiVe
},),(][ {][ ji
j
VVd u rjVlm iniVl
这两个递推公式的计算必须分别在 拓扑有序及 逆拓扑有序 的前提下进行。
设 活动 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
事件 Ve[i] Vl[i]
V0 0 0
V1 6 6
V2 4 6
V3 5 8
V4 7 7
V5 7 10
V6 16 16
V7 14 14
V8 18 18
边 <0,1><0,2><0,3><1,4><2,4><3,5><4,6><4,7><5,7><6,8><7,8>
活动 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11
e 0 0 0 6 4 5 7 7 7 16 14
l 0 2 3 6 6 8 7 7 10 16 14
l - e 0 2 3 0 2 3 0 0 3 0 0
关键 是 是 是 是 是 是利用关键路径法求 AOE网的各关键活动
void graph::CriticalPath ( ) {
//在此算法中需要对邻接表中单链表的结点加以
//修改,在各结点中增加一个 int域 cost,记录该结
//点所表示的边上的权值 。
int i,j; int p,k; int e,l;
Ve = new int[n]; Vl = new int[n];
for ( i = 0; i < n; i++ ) Ve[i] = 0;//初始化
for ( i = 0; i < n; i++ ) {//顺向计算事件最早允许开始时间
Edge<int> *p = NodeTable[i].adj;//该顶点边链表链头指针 p
while ( p != NULL ) {//找所有后继邻接顶点
k = p→ dest;//i的后继邻接顶点 k
if ( Ve[i] + p→ cost > Ve[k] )
Ve[k] = Ve[i] + p→cost;
p = p→link; //找下一个后继
}
}
for ( i = 0; i < n; i++ ) Vl[i] = Ve[n-1];//逆向计算事件的最迟开始时间
for ( i = n-2; i; i-- ) {//按逆拓扑有序顺序处理
p = NodeTable[i].adj;//该顶点边链表链头指针 p
while ( p != NULL ) {
k = p→ dest; //i的后继邻接顶点 k
if ( Vl[k] - p→ cost < Vl[i])
Vl[i] = Vl[k] - p→ cost;
p = p→ link; //找下一个后继
}
}
for ( i = 0; i < n; i++ ) {//逐个顶点求各活动的 e[k]和 l[k]
p = NodeTable[i].adj; //该顶点边链表链头指针 p
while ( p != NULL ) {
k = p→ dest; //k是 i的后继邻接顶点
e = Ve[i]; l = Vl[k] - p→cost;
if ( l == e )/ /关键活动
cout << "<" << i << "," << k
<<,>” <<,是关键活动,<< endl;
p = p→ link; //找下一个后继
}
}
}
注意在拓扑排序求 Ve[i]和逆拓扑有序求 Vl[i]时,所需为
O(n+e),求各个活动的 e[k]和 l[k]时所需时间为
O(e),总 共花费时间仍然是 O(n+e)。
所有顶点按拓扑有序的次序编号
仅计算 Ve[i] 和 Vl[i] 是不够的，还须计算
e[k] 和 l[k]。
不是任一关键活动加速一定能使整个工程提前。
想使整个工程提前，要考虑各个关键路径上所有关键活动。
§ 6 Activity On Edges Net (AOE Net)
In the weighted directed graph without circles,if
we indicate the activity of project with a directed
edge (Activity),indicate the duration of activity
with the weight on the edge (Duration),indicate
the event with the point (Event),than such a
directed graph is called Activity On Edges Net
(AOE)。
AOE Net is very useful in some project evaluation,
For example,It let people know:
How much time will the whole project cost at
least (assuming there is no circle in the net)?
Which activities should be speeded up in order
to shorter the working period?
There‘s more than one path form the source points
to each point,so there‘s more than one path
between these points,It cost different time to
complete different path,but only all of the
activities in the path finished,the project can be
finished.
So,time we need to complete the whole project
depends on the longest path from the source point
to the end point,In other words,it‘s the total time
of the duration of all the activities in the path,The
longest path is called 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
Aiming at finding the critical path,first we must find
the critical activity,which would delay the whole
project if not completed in time.
All the activities in the critical path are critical
activities,It is to say,as long as we find the critical
activities,we get the critical path,For example,the
following graph is a AOE Net
Define some variables related to calculating
the critical activities:
① The earliest possible time for event Vi‘ beginning,Ve(i)
it‘s the longest path length from source point V0 to Vi 。
② The latest possible time for event Vi‘s beginning,Vl[i]
It‘s the latest permitting time for Vi‘s beginning in order
to make sure that the point Vn-1 can be finished at Ve[n-1],
③ The earliest possible time for activity ak?beginning,e[k]
Assuming activity ak is on the edge of < Vi,Vj >,than e[k]
is the longest path length form source point V0to point
Vi,So,
e[k] = Ve[i]
④ the latest permitting time for activity ak?beginningl[k]
l[k] is the the latest permitting time,without
duration delay,of the activity.
l[k] = Vl[j] - dur(<i,j>)。
here,dur(<i,j>) is the necessary time for finishing
ak.
⑤ Time margin,l[k] - e[k]
indicating the margin between the earliest possible
beginning time and the latest permitting beginning
time of activity,ak l[k] == e[k] indicates activity ak
is the critical activity with no margin time.
In order to find critical activities,we need calculate
e[k] and l[k] of each activity,than justify if l[k] ==
e[k]。
In order to get e[k] and l[k],we need to get Ve[i]
and Vl[i] from source point V0 to each point Vi,
The recurrence formulation for Ve[i]
From Ve[0] = 0,forward recurrence
< Vj,Vi >? S2,i = 1,2,?,n-1
S2 is the set containing all the directed edges < Vj,Vi
> pointing to Vi
From Vl[n-1] = Ve[n-1],backward recurrence
< Vi,Vj >? S1,i = n-2,n-3,?,0
S1 is the set containing all the directed edges < Vi,Vj
> starting from Vi
},),(][ {][ ijj VVd u rjVem a xiVe
},),(][ {][ jij VVd u rjVlm iniVl
Both recurrence formulations must be used only
when the topology ordered and anti-topology
ordered.
Assuming activity ak(k=1,2,…,e)is on the weighted
edge < Vi,Vj > 上,and its duration is indicated
bydur (<Vi,Vj >),So
e[k] = Ve[i]；
l[k] = Vl[j] - dur(<Vi,Vj >)； k = 1,2,…,e 。
Here,we get the algorithm of calculating critical path.
In order to simplify the algorithm,assume the
topology of each point was ready before our work,
and the points were numbered according the
consequence of topology.
1
3
2
4
a1=8
a2=12
5
6
7 8
a10=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
事件 Ve[i] Vl[i]
V0 0 0
V1 6 6
V2 4 6
V3 5 8
V4 7 7
V5 7 10
V6 16 16
V7 14 14
V8 18 18
边 <0,1><0,2><0,3><1,4><2,4><3,5><4,6><4,7><5,7><6,8><7,8>
活动 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11
e 0 0 0 6 4 5 7 7 7 16 14
l 0 2 3 6 6 8 7 7 10 16 14
l - e 0 2 3 0 2 3 0 0 3 0 0
关键 是 是 是 是 是 是
Find the critical activities in AOE Net with critical paths
void graph::CriticalPath ( ) {
//在此算法中需要对邻接表中单链表的结点加以
//修改,在各结点中增加一个 int域 cost,记录该结
//点所表示的边上的权值 。
int i,j; int p,k; int e,l;
Ve = new int[n]; Vl = new int[n];
for ( i = 0; i < n; i++ ) Ve[i] = 0;//初始化
for ( i = 0; i < n; i++ ) {//顺向计算事件最早允许开始时间
Edge<int> *p = NodeTable[i].adj;//该顶点边链表链头指针 p
while ( p != NULL ) {//找所有后继邻接顶点
k = p→dest;//i的后继邻接顶点 k
if ( Ve[i] + p→cost > Ve[k] )
Ve[k] = Ve[i] + p→cost;
p = p→link;//找下一个后继
}
}
for ( i = 0; i < n; i++ ) Vl[i] = Ve[n-1];//逆向计算事件的最迟开始时间
for ( i = n-2; i; i-- ) {//按逆拓扑有序顺序处理
p = NodeTable[i].adj; //该顶点边链表链头指针 p
while ( p != NULL ) {
k = p→dest; //i的后继邻接顶点 k
if ( Vl[k] - p→cost < Vl[i])
Vl[i] = Vl[k] - p→cost;
p = p→link; //找下一个后继
}
}
for ( i = 0; i < n; i++ ) {//逐个顶点求各活动的 e[k]和 l[k]
p = NodeTable[i].adj; //该顶点边链表链头指针 p
while ( p != NULL ) {
k = p→ dest; //k是 i的后继邻接顶点
e = Ve[i]; l = Vl[k] - p→cost;
if ( l == e )/ /关键活动
cout << "<" << i << "," << k
<<,>” <<,是关键活动,<< endl;
p = p→ link; //找下一个后继
}
}
}
Attention
The time complexity of getting Ve[i] topologically and
getting Vl[i] anti-topologically is O(n+e); the time
complexity of getting e[k] and l[k] of each activity isO(e),
so the total cost is still O(n+e)。
All the points is numbered according the topological
sequence.
It’s not enough to calculating Ve[i] and Vl[i],gettint e[k]
and l[k] is necessary.
Not any critical activity’s accelerating can lead to the
whole project’s accelerating.
If we want to finish the whole project advance,we must
think about all the critical activities in all the critical paths.
最短路径 (Shortest Path)
最短路径问题,如果从图中某一顶点 (称为源点 )到达另一顶点 (称为终点 )的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。
问题解法
边上权值非负情形的单源最短路径问题
— Dijkstra算法
边上权值为任意值的单源最短路径问题
— Bellman和 Ford算法
所有顶点之间的最短路径
— Floyd算法
§ 7 Shortest Path Algorithms
边上权值非负情形的单源最短路径问题
问题的提法,给定一个带权有向图 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 ← { v 0 };
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,则算法结束，否则转 ② 。
void ShortestPath (MTGraph G,int v ){
//MTGraph是一个有 n 个顶点的带权有向图,各边上的权值由 Edge[i][j]给出。
//dist[j],0? j<n,是当前求到的从顶点 v 到顶点 j 的最短路径长度,用数组 path[j],0? j<n,存放求到的最短路径。
EdgeData dist[G.n]; //最短路径长度数组
int path[G.n]; //最短路径数组
int S[G.n]; //最短路径顶点集计算从单个顶点到其它各顶点最短路径
for ( int i = 0; i < n; i++) {
dist[i] = G.Edge[v][i]; //dist数组初始化
S[i] = 0; //集合 S初始化
if ( i != v && dist[i] < MaxValue )
path[i] = v;
else path[i] = -1; //path数组初始化
}
S[v] = 1; dist[v] = 0; //顶点 v加入顶点集合
for ( i = 0; i < n-1; i++ ) {#//从顶点 v确定 n-1条路径
float min = MaxValue; int u = v;
for ( int j = 0; j < n; j++ ) //选当前不在集合 S中具有最
if ( !S[j] && dist[j] < min )短路径的顶点 u
{ u = j; min = dist[j]; }
S[u] = 1; //将顶点 u加入集合 S，表示它已在最短路径上
for ( int w = 0; w < n; w++ ) //修改
if (!S[w] && G.Edge[u][w] < MaxValue
&& dist[u] + G.Edge[u][w] < dist[w] ) {
//顶点 w未加入 S,且绕过 u可以缩短路径
dist[w] = dist[u] + G.Edge[u][w];
path[w] = u; //修改到 w的最短路径
}
}# //选定各顶点到顶点 v 的最短路径
}
//打印各顶点的最短路径,路径是逆向输出的
for ( i = 0; i < G.n; i++ ) {
cout << endl;
cout << ―Distance,‖ << dist[i]
<< ― Path,‖ << i;
//输出终点的最短路径长度和终点
int pre = path[i]; //取终点的直接前驱
while ( pre != v ) { //沿路径上溯输出
cout << ―,‖ << pre;
pre = path[pre];
}
}
§ 7 Shortest Path Algorithms
Given a digraph G = ( V,E ),and a cost function c( e )
for e? E( G ),The length of a path P from source to
destination is (also called weighted path length).
Pe
i
i
ec )(
1,Single-Source Shortest-Path Problem
Given as input a weighted graph,G = ( V,E ),and a
distinguished vertex,s,find the shortest weighted path
from s to every other vertex in G.
v1 v2
v6 v7
v3 v4 v5
2
4
2
1 3 10
2
5 8 4 6
1
v1 v2
v6 v7
v3 v4 v5
2
4
2
1
3
–10
2
5 8 4 6
1
Negative-cost
cycleNote,If there is no
negative-cost cycle,
the shortest path
from s to s is
defined to be zero.
Unweighted Shortest Paths
v1 v2
v6 v7
v3 v4 v50
0,? v3
1,? v1 and v6
1
1
2,? v2 and v4
2
2
3,? v5 and v7
3
3
Sketch of the idea
Breadth-first
search
Implementation
Table[ i ].Dist,:= distance from s to vi /* initialized to be? except
for s */
Table[ i ].Known,:= 1 if vi is checked; or 0 if not
Table[ i ].Path,:= for tracking the path /* initialized to be 0 */
void Unweighted( Table T )
{ int CurrDist;
Vertex V,W;
for ( CurrDist = 0; CurrDist < NumVertex; CurrDist ++ ) {
for ( each vertex V )
if ( !T[ V ].Known && T[ V ].Dist == CurrDist ) {
T[ V ].Known = true;
for ( each W adjacent to V )
if ( T[ W ].Dist == Infinity ) {
T[ W ].Dist = CurrDist + 1;
T[ W ].Path = V;
} /* end-if Dist == Infinity */
} /* end-if !Known && Dist == CurrDist */
} /* end-for CurrDist */
}
The worst case,v1v2v6v7 v3v4v5v9 v8
T = O( |V|2 )
If V is unknown
yet has Dist <
Infinity,then Dist
is either CurrDist
or CurrDist+1.
Improvement
void Unweighted( Table T )
{ /* T is initialized with the source vertex S given */
Queue Q;
Vertex V,W;
Q = CreateQueue (NumVertex ); MakeEmpty( Q );
Enqueue( S,Q ); /* Enqueue the source vertex */
while ( !IsEmpty( Q ) ) {
V = Dequeue( Q );
T[ V ].Known = true; /* not really necessary */
for ( each W adjacent to V )
if ( T[ W ].Dist == Infinity ) {
T[ W ].Dist = T[ V ].Dist + 1;
T[ W ].Path = V;
Enqueue( W,Q );
} /* end-if Dist == Infinity */
} /* end-while */
DisposeQueue( Q ); /* free memory */
}
v1 v2
v6 v7
v3 v4 v5
0
v1
Dist Path
v2
0v3
v4
v5
v6
v7
0
0
0
0
0
0
0 v
3
v71 v3
1
1 v3 v6
1
1
2
2
v1
v2
2
2
v1 v4
3
3
v2
v5
3
3
v4
T = O( |V| + |E| )
Dijkstra‘s Algorithm (for weighted shortest paths)
Let S = { s and vi‘s whose shortest paths have been found }
For any u? S,define distance [ u ] = minimal length of
path { s? ( vi? S )? u },If the paths are generated in
non-decreasing order,then
the shortest path must go through ONLY vi? S ;
u is chosen so that distance[ u ] = min{ w?S |
distance[ w ] } (If u is not unique,then we may select
any of them) ; /* Greedy Method */
if distance [ u1 ] < distance [ u2 ] and we add u1 into S,
then distance [ u2 ] may change,If so,a shorter path
from s to u2 must go through u1 and distance’ [ u2 ] =
distance [ u1 ] + length(< u1,u2>).
void Dijkstra( Table T )
{ /* T is initialized by Figure 9.30 on p.303 */
Vertex V,W;
for ( ; ; ) {
V = smallest unknown distance vertex;
if ( V == NotAVertex )
break;
T[ V ].Known = true;
for ( each W adjacent to V )
if ( !T[ W ].Known )
if ( T[ V ].Dist + Cvw < T[ W ].Dist ) {
Decrease( T[ W ].Dist to
T[ V ].Dist + Cvw );
T[ W ].Path = V;
} /* end-if update W */
} /* end-for( ; ; ) */
}
v1 v2
v6 v7
v3 v4 v5
2
4
2
1 3 10
2
5 8 4 6
1
0v1
Dist Path
v2
v3
v4
v5
v6
v7
0
0
0
0
0
0
0
2 v1
1 v1
3 v4
3 v4
9 v4
5 v4
8 36 7
/* not work for edge with negative cost */
Please read Figure 9.31 on p.304 for printing the path.
/* O( |V| ) */
Implementation 1
V = smallest unknown distance vertex;
/* simply scan the table – O( |V| ) */
T = O( |V|2 + |E| ) Good if the graph is dense
Implementation 2
V = smallest unknown distance vertex;
/* keep distances in a priority queue and call DeleteMin – O( log|V| ) */
Decrease( T[ W ].Dist to T[ V ].Dist + Cvw );
/* Method 1,DecreaseKey – O( log|V| ) */
T = O( |V| log|V| + |E| log|V| ) = O( |E| log|V| )
/* Method 2,insert W with updated Dist into the priority queue */
/* Must keep doing DeleteMin until an unknown vertex emerges */
Good if the
graph is sparse
T = O( |E| log|V| ) but requires |E| DeleteMin with |E| space
Other improvements,Pairing heap (Ch.12) and Fibonacci heap (Ch,11)
Graphs with Negative Edge Costs
void WeightedNegative( Table T )
{ /* T is initialized by Figure 9.30 on p.303 */
Queue Q;
Vertex V,W;
Q = CreateQueue (NumVertex ); MakeEmpty( Q );
Enqueue( S,Q ); /* Enqueue the source vertex */
while ( !IsEmpty( Q ) ) {
V = Dequeue( Q );
for ( each W adjacent to V )
if ( T[ V ].Dist + Cvw < T[ W ].Dist ) {
T[ W ].Dist = T[ V ].Dist + Cvw;
T[ W ].Path = V;
if ( W is not already in Q )
Enqueue( W,Q );
} /* end-if update */
} /* end-while */
DisposeQueue( Q ); /* free memory */
} /* negative-cost cycle will cause indefinite loop */
/* no longer once
per edge */
/* each vertex can dequeue at most |V|
times */
T = O( |V|? |E| )
Acyclic Graphs
If the graph is acyclic,vertices may be selected in topological order
since when a vertex is selected,its distance can no longer be lowered
without any incoming edges from unknown nodes.
T = O( |E| + |V| ) and no priority queue is needed.
Application,AOE ( Activity On Edge ) Networks
—— scheduling a project
vjai,:= activity Signals the completion of ai
EC[ j ] \ LC[ j ],:= the earliest \
latest completion time for node vj
CPM ( Critical Path Method ) Lasting Time
Slack Time
EC Time
LC Time
Index of vertex
〖 Example〗 AOE network of a hypothetical project
0
1
2
3
4
5
6
7
8
start
finish
a0=6
a1=4
a2=5
a3=1
a4=1
a5=2
a6=9
a7=7
a8=4
a9=2
a10=4
Calculation of EC,Start from v0,for any ai = <v,w>,we have
}][{m a x][,),( wvEwv CvECwEC
0
6
4
5
7
7
16
14
18
a11=0
Dummy activity
Calculation of LC,Start from the last vertex v8,for any ai = <v,
w>,we have
}][{m i n][,),( wvEwv CwLCvLC
18
16
14
7
75
6
6
0
Slack Time of <v,w> =
wvCvECwLC,][][
2
3
2
Critical Path,:= path consisting entirely of zero-slack edges.
2,All-Pairs Shortest Path Problem
For all pairs of vi and vj ( i? j ),find the shortest path
between.
Method 1 Use single-source algorithm for |V| times.
T = O( |V|3 ) – works fast on sparse graph.
Method 2 O( |V|3 ) algorithm given in Ch.10,works
faster on dense graphs.
§ 8Applications of Depth-First Search
/* a generalization of preorder traversal */
void DFS ( Vertex V ) /* this is only a template */
{ visited[ V ] = true; /* mark this vertex to avoid cycles */
for ( each W adjacent to V )
if ( !visited[ W ] )
DFS( W );
} /* T = O( |E| + |V| ) as long as adjacency lists are used */
0
1 2 3
4 5
6
DFS ( 0 )
1,Undirected Graphs
void ListComponents ( Graph G )
{ for ( each V in G )
if ( !visited[ V ] ) {
DFS( V );
printf(“\n“);
}
}
7
8
0 1 4 6 5 2 3
7 8
2,Biconnectivity
Articulation
point
Biconnected
graph
v is an articulation pointif G‘ = DeleteVertex( G,v ) has at least 2
connected components.
G is a biconnected graph if G is connected and has no articulation
points.
A biconnected component is a maximal biconnected subgraph.
〖 Example〗
0
1
2 3
4
8
7
5
6
9
Connected graph
0
1
1
2 3
4
3 5
8
7
7
5
6
7
9
Biconnected components
Note,No edges can
be shared by two or
more biconnected
components,Hence
E(G) is partitioned
by the biconnected
components of G.
Finding the biconnected components of a connected undirected G
0
1
2 3
4
8
7
5
6
9
Use depth first search to obtain a spanning tree of G
DFS ( 3 )
0
1
2
3
4
5
6
7
89
Depth first spanning tree
3
4 5
2
1
0
6
7
9 8
0
1
2
3
4
5
6
7
8 9
Depth first
number (Num)
Find the articulation points in G
The root is an articulation point iff it has at least 2 children
Any other vertex u is an articulation point iff u has at least 1
child,and it is impossible to move down at least 1 step and
then jump up to u’s ancestor.
Back edges
::= (u,v)? tree
and u (or v) is
an ancestor of
v (or u).
Note,If u is an
ancestor of v,
then Num( u )
< Num( v ).
3
4 5
2
1
0
6
7
9 8
0
1
2
3
4
5
6
7
8 9
}}e d g e b a c k a is ),(|)(m i n {
},of c h i l d a is |)(m i n {
),(m i n {)(
wuwN u m
uwwL o w
uN u muL o w?
vertex
Num
Low
0 1 2 3 4 5 6 7 8 9
4 3 2 0 1 5 6 7 9 8
00 54 0 0 55 9 8
Therefore,u is an articulation point iff
(1) u is the root and has at least 2 children; or
(2) u is not the root,and has at least 1 child such that
Low( child )? Num( u ).
Please read the pseudocodes on p.327 and p.329 for more details.
3,Euler Circuits
Draw each line exactly once without lifting your pen from the
paper – Euler tour
Draw each line exactly once without lifting your pen from the
paper,AND finish at the starting point – Euler curcuit
〖 Proposition〗 An Euler circuit is possible only if the graph is
connected and each vertex has an even degree.
〖 Proposition〗 An Euler tour is possible if there are exactly two
vertices having odd degree,One must start at one of the odd-degree
vertices.
2
6
98
3
7
1
12
4
10
5
11
Note:
The path should be maintained as a linked list.
For each adjacency list,maintain a pointer to the last edge
scanned.
T = O( |E| + |V| )
Find a simple cycle in an undirected graph that visits every
vertex – Hamilton cycle
DFS
