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
§ 4 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
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.
§ 5 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.
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 。
§ 6 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| )
§ 7 Applications 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
§ 4 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
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.
§ 5 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.
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 。
§ 6 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| )
§ 7 Applications 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
