Outline • • • • • • •
Data Structures – Week #10 Graphs & Graph Algorithms
Motivation for Graphs Definitions Representation of Graphs Topological Sort Breadth-First Search (BFS) Depth-First Search (DFS) Single-Source Shortest Path Problem (SSSP) – Dijkstra’s Algorithm
• Minimum Spanning Trees – Prim’s Algorithm – Kruskal’s Algorithm January 5, 2006
Borahan Tümer, Ph.D.
2
Motivation
Graphs & Graph Algorithms
January 5, 2006
Borahan Tümer, Ph.D.
3
Graph Definitions
– Graphs are useful structures for solving many problems computer science is interested in including but not limited to • Computer and telephony networks • Game theory • Implementation of automata
January 5, 2006
Borahan Tümer, Ph.D.
Adjacency Set and Being Adjacent
• A graph G=(V,E) consists a set of vertices V and a set of edges E. • An edge (v,w)E has a starting vertex v and and ending vertex w. An edge sometimes is called an arc. • If the pair is ordered, then the graph is directed. Directed graphs are also called digraphs. • Graphs which have a third component called a weight or cost associated with each edge are called weighted graphs.
• Vertex w is adjacent to v iff (v,w)E. In an undirected graph with e=(v,w), v and w are adjacent to each other. • In Fig. 6.1, the vertices v, w and x form the adjacency set of u or Adj(u)={v,w,x}.
January 5, 2006
January 5, 2006
Borahan Tümer, Ph.D.
4
5
Borahan Tümer, Ph.D.
u
v
w
x
6
More Definitions
Path Definitions • A path in a graph is a sequence of vertices w1, w2, …,wn where each edge (wi, wi+1)E for 1di
• A cycle is a path such that the vertex at the destination of the last edge is the source of the first edge. – A digraph is acyclic iff it has no cycles in it.
• In-degree of a vertex is the number of edges arriving at that vertex. • Out-degree of a vertex is the number of edges leaving that vertex. January 5, 2006
Borahan Tümer, Ph.D.
7
January 5, 2006
Connectedness
Borahan Tümer, Ph.D.
8
Representation of Graphs
An undirected graph is connected if there exists a path from every vertex to every other vertex. • A digraph with the same property is called strongly connected. • If a digraph is not strongly connected, but the underlying graph is connected, then the digraph is said to be weakly connected. • A graph is complete if there is an edge between every pair of vertices
• Two ways to represent graphs: – Adjacency matrix representation – Adjacency list representation
January 5, 2006
January 5, 2006
Borahan Tümer, Ph.D.
9
• Assume you have n vertices. • In a boolean array with n2 elements, where each element represents the connection of a pair of vertices, you assign true to those elements that are connected by an edge and false to others. • Good for dense graphs. • Not very efficient for sparse (i.e., not dense) graphs. • Space requirement: O(|V|2).
Borahan Tümer, Ph.D.
10
Adjacency matrix representation (AMR)
Adjacency Matrix Representation
January 5, 2006
Borahan Tümer, Ph.D.
7
1
5
2 9
8
4
4
5
6
8
6 9 7
7
4
3
1
3
6
3
7
5
3 4
8
1 6
9 3
2
4
5
6
8
9
8
3
9
3
1
7
2
5
3
6
4
7
9
3
4
5
5
4
6
7
7
8
3
6
7
4
8
1
9
3
6
Disadvantage: Waste of space for sparse graphs Advantage: Fast access 11
January 5, 2006
Borahan Tümer, Ph.D.
12
Adjacency List Representation
Adjacency list representation (ALR) array index: source vertex; first number: destination vertex; second number: cost of the corresponding edge
Assume you have n vertices. • We employ an array with n elements, where ith element represents vertex i in the graph. Hence, element i is a header to a list of vertices adjacent to the vertex i. • Good for sparse graphs • Space requirement: O(|E|+|V|). January 5, 2006
Borahan Tümer, Ph.D.
13
7
1
5
2
3
6 8
3
4
4
5
6
8
6 9 7
7
4
9
3
7
5
3 8
4
1 6
9 3
1
2,7
4,8
5,9
8,3
2
3,5
6,4
7,9
9,3
3
4,6
4
9,5
5
2,4
2,4
2,4
2,4
6
9,7
7
8,4
8
9,1
9
9,3
2,4
2,4
2,4
Disadvantage: Sequential search among edges of a node Advantage: Minimum space requirement January 5, 2006
Borahan Tümer, Ph.D.
14
Algorithm for Topological Sort*
Topological Sort
Void Toposort () { Queue Q; int ctr; Vertex v,w; Q=createQueue(NumVertex); for each vertex v if (indegree[v] == 0) enqueue(v,Q); while (!IsEmpty(Q)) { v=dequeue(Q); topnum[v]=++ctr; for each w adjacent to v if (--indegree[w] == 0) enqueue(w,Q); } if (ctr != NumVertex) report error (‘graph cyclic!’) free queue; }
• A topological sort is an ordering of vertices in an acyclic digraph such that if there is a path from vi to vj, then vj appears after vi in the ordering. • Example: course prerequisite requirements.
*From [2] January 5, 2006
Borahan Tümer, Ph.D.
15
January 5, 2006
Borahan Tümer, Ph.D.
16
Breadth-First Search (BFS)
Breadth-First Search (BFS)
• Given a graph, G, and a source vertex, s, breadth-first search (BFS) checks to discover every vertex reachable from s. • BFS discovers vertices reachable from s in a breadth-first manner. • That is, vertices a distance of k away from s are systematically discovered before vertices reachable from s through a path of length k+1.
• To follow how the algorithm proceeds, BFS colors each vertex white gray or black. • Unprocessed nodes are colored white while vertices discovered (enountered during search) turn to gray. Vertices processed (i.e., vertices with all neighbors discovered) become black. • Algorithm terminates when all vertices are visited.
January 5, 2006
January 5, 2006
Borahan Tümer, Ph.D.
17
Borahan Tümer, Ph.D.
18
An example to BFS
Algorithm for Breadth-First Search* BFS(Graph G, Vertex s) { // initialize all vertices for each vertex uV[G]-{s} { color [u]=white; dist[u]=; from[u]=NULL; } color[s]=gray; dist[u]=; from[u]=NULL; Q={}; enqueue(Q,s); *From
while (!isEmpty(Q)) { u=dequeue(Q); for each v Adj[u] if (color [v]==white) { color[v]=gray; dist[v]=dist[u]+1; from[v]=u; enqueue(Q,v); } color[u]=black; } }
r
s 0
u
v
x
y Q
r 1 u 2
[1]
January 5, 2006
Borahan Tümer, Ph.D.
19
s 0
u 2
v 1
x 2
2 y Q
y
u
t 1
r 1
1 w
u 2
2 z z
s 0 v 1
x 2
2 y Q
u
1 w
u 2
1
1 w
u 2
x
January 5, 2006
t 1
1
1 w
2 y
2 z
v
Q
s 0
t 1
1
1 w
v
2 y Q
s 0
2 z z
Ӆ
Borahan Tümer, Ph.D.
21
z
1 w
u
y
z
v
t
x 2 Q
w
x Q
t 1
r 1
1
1 w
u
2 y
z y
u
1 w
y
s 0
x
1
v
w
v
t 1
v
z w
t
s 0
t 1
1
1 w
v
x 2
z
2 y Q
t
w
Borahan Tümer, Ph.D.
x
y
20
January 5, 2006
Borahan Tümer, Ph.D.
22
Depth-First Search
DFS-visit(u) DFS(Graph G, Vertex s) { { color[u]=gray; //u just discovered // initialize all vertices time++; for each vertex uV[G] { d[u]=time; color [u]=white; for each v Adj[u] //check edge (u,v) from[u]=NULL; if (color[v] == white) { } from[v]=u; time=0; DFS-visit(v); //recursive call for each vertex uV[G] } if (color [u]==white) color[u]=black; // u is done processing DFS-visit(u); f[u] = time++; } } *From [1] Borahan Tümer, Ph.D.
2 z u
1
s 0
• Unlike in BFS, depth-first search (DFS), performs a search going deeper in the graph. • The search proceeds discovering vertices that are deeper on a path and looks for any left edges of the most recently discovered vertex u. • If all edges of u are found, DFS backtracks to the vertex t which u was discovered from to find the remaining edges.
Algorithm for Depth-First Search*
January 5, 2006
y
r 1
r
Q
r 1
t 1
v
x
t 1
s 0
Depth-First Search (DFS)
x 2
2 z
x 2
January 5, 2006
r 1
z
r 1 u 2
t 1
u
s 0
Rest of Example r 1
w z
2 y Q
r 1
s
v
x 2
t
23
• The function DFS() is a “manager” function calling
the recursive function DFS-visit(u) for each vertex in the graph. • DFS-visit(u) starts by graying the vertex u just discovered. Then it recursively visits and discovers (and hence grays) all those nodes v in the adjacency set of u, Adj[u]. At the end, u is finished processing and turns to black. • time in DFS-visit(u) time-stamps each vertex u when – u is discovered using d[u] – u is done processing using f[u]. January 5, 2006
Borahan Tümer, Ph.D.
24
An example to DFS s
r
t
r
1/
u u
t 2/
v
w
v
s 1/
Example cont’d...
r u
w
s
t
1/
2/
s
t
1/
2/
r
v
w
3/
u
v
u
s
t
1/
2/
z
y
r u
v
w
3/
x
4/5
y
s
t
1/
2/7
r
v
u
w
3/6
s
t
1/
2/
r
v
u
w
3/
s
t
1/
2/
v
x
x
4/
z
z
y
January 5, 2006
4/
r
s
t
1/10
2/7
v
v
8/ w
25
s
t 2/7
v
z
s
t 2/7
u
v
8/ w
3/6
x
4/5
z
y
January 5, 2006
z
1/
r
8/9 w
3/6
x
4/5
y
Borahan Tümer, Ph.D.
u
4/5
y
1/10
r
x
z
y
8/9 w
x
z
y
4/5
z
11/
u
w
3/
x
4/5
3/6
x
t 2/7
x
z
y
y
r
s 1/
3/6
x z
y
u
w
3/6
x
r
4/5
z
y
Borahan Tümer, Ph.D.
Example cont’d...
26
End of Example
r
s
t
r
s
t
r
s
t
r
s
t
r
s
t
r
s
t
11/
1/10
2/7
11/
1/10
2/7
11/
1/10
2/7
11/
1/10
2/7
11/
1/10
2/7
11/
1/10
2/7
u 3/6
v 12/
x
8/9 w
4/5
y
u
z
u
v
3/6
8/9 w
12/
x
4/5
z
y
3/6
x
v 12/
8/9 w
4/5
13/
y
z
u
v
3/6
r r
s
t
r
s
t
r
s
t
11/
1/10
2/7
11/
1/10
2/7
11/
1/10
2/7
u
v
3/6
12/
8/9 w
x 13/
14/
4/5
y
z
u
v
3/6
12/
8/9 w
x 13/
14/
4/5
y
z
u 3/6
11/18
u
v 12/
x 13/
8/9 w
8/9 w
12/
x 13/
3/6
u
14/15
4/5
y
z
1/10
v
z
x 13/16
27
x13/16
12/
8/9 w
14/15
4/5
y
z
t 2/7
r
s
t
11/
1/10
2/7
u 8/9 w
14/15
4/5
v
3/6
12/17
8/9 w
x13/16
14/15
4/5
y
z
z Borahan Tümer, Ph.D.
28
• Dijkstra’s algorithm solves the SSSP problem on a weighted digraph G=(V,E) assuming no negative weights exist in G. • Input parameters for Dijkstra’s algorithm
• SSSP Problem: • Given a weighted digraph G (V,E), we need to efficiently find the shortest path p*=(ui, ui+1,..., uj,..., uk-1,uk) between two vertices ui and uk. • The shortest path p* is the path with the minimum weight among all paths pl=(ui,...,uk), or
– the graph G, – the weights w, – a source vertex s.
• It uses – a set VF holding vertices with final shortest paths from the source vertex s. – from[u] and dist[u] for each vertex u Ӊ V as in BFS. – A min-heap Q
min >w( p )@ l
l
Borahan Tümer, Ph.D.
z
v
3/6
Dijkstra’s Algorithm
Single-Source Shortest Paths (SSSP)
January 5, 2006
4/5
y
12/17
January 5, 2006
8/9 w
14/15
4/5
y
Borahan Tümer, Ph.D.
w( p * )
12/
x13/16
y January 5, 2006
v
3/6
s
u
29
January 5, 2006
Borahan Tümer, Ph.D.
30
Dijkstra’s Algorithm – An Example
Dijkstra’s Algorithm r
Dijkstra(Graph G, while (!IsEmpty(Q)) { Weights w, Vertex s) u=deletemin(Q); add u to VF ; { for each vertex v Ӊ Adj(u) for each vertex uV[G] { if (dist[v]>dist[u]+w(u,v)){ dist [u]=; dist[v]=dist[u]+w(u,v)); from[u]=NULL; from[v]=u; } } dist [u]=0; } // end of while VF = ø; } //end of function Q = all vertices u Ӊ V ; January 5, 2006
Borahan Tümer, Ph.D.
31
t
7
8 v
3
0
x
3
r
4
t
3
6
3
4
6 6
y
t
7
5
4
6
4 s
9
8 v
3
0
r
4
5
6
t
7
3
13 3
3
4
6 6
y
January 5, 2006
7
3
z
4
6
7
5 1
3
3 9 3
x
z
3 3
4
6 6
y
3
13
u
6
5 1
r
7
3
6
Borahan Tümer, Ph.D.
t
7
3 3
6 6
5 1
z
6
y
3
7
5 1
3
6
6 6
7
y
8
8 5 1
3
7 z
9
3 32
Resulting Shortest Paths
4
s
0
w
8
8
6
9
5
3
7
3
x
7
7
3
13
7
6
4
9
u
5
4
8 z
t
7
v
z
3
6
4 6
7
6 4
z
7 4 w
0
3
5
4
3
3
u
Borahan Tümer, Ph.D.
7
3
7
9
3
4 s
9
y
1
8
8
t
3
1
y
6
9
x
z
5
6
7
7
1
y
8 v
8 5
6 6
7
8
6 4
r
7 4 w
0
3
u
6
3
3
7
u
5
4
9 x
4
3
4 s
3
7
7
t
9
3
7 8
8
6 3
x
z
6
7 4 w
0 9
u
5
4
4 s
3
t
7 9
7
1
6 y
7
r
7 3
Note that r is not reachable from s!
z 3 33
Minimum Spanning Trees (MSTs)
January 5, 2006
• MST is
January 5, 2006
January 5, 2006
35
Borahan Tümer, Ph.D.
34
Minimum Spanning Trees (MSTs)
• Problem: • Given a connected weighted undirected graph G=(V,E), find an acyclic subset S E, such that S connects all vertices in G and the sum of the weights of the edges in S are minimum. • The solution to the problem is provided by a minimum spanning tree.
Borahan Tümer, Ph.D.
3
8 v
8
8
7 4 w 6
4
3
5
4
3
x
7
6
4
3
0
9
6
7
7
4 s
9 3
13
z
5 1
y
6
5
r
8
8
6 4
u
5
3
8 v
8
8
3
3
r
7
7 4 w 6
x
z
7 4 w
0
8 v
7
7
6
3
3
8
8
5
4
9 z
u
4 s
9
x
7 4 w 6
7
8 v
7
7
5
4 0
t
3
4 s
9
3
1
y
t
7
13
7
7
8 v
8
8
5
6 6
7 8
8
6 3
3
r
6
r
7 4 w
0
9
u
5
4
4 s
9
x
7 4 w 6
9 x
u
t
13
7
7
5
4 0
8 v
3
4 s
9
8 v
3
1
y
6
7 8
8
6 3
3
r
7 4 w
9 x
u
7
6
0 9
January 5, 2006
Dijkstra’s Algorithm – An Example r
3
u
5
4
4 s
9
t
7
8 v
7 4 w
3
3
4 0
9
3
1
4 s
9
5
6 y
r
7 4 w
8
7
8 v
x
6
6
9
u
5
4 s
9
– a tree since it connects all vertices by an acyclic subset of S E, – spanning since it spans the graph (connects all its vertices) – minimum since its weights are minimized.
Borahan Tümer, Ph.D.
36
Prim’s Algorithm
Prim’s Algorithm
• Prim’s algorithm operates similar to Dijkstra’s algorithm to find shortest paths. • Prim’s algorithm proceeds always with a single tree. • It starts with an arbitrary vertex t. • It progressively connects an isolated vertex to the existing tree by adding the edge with the minimum possible weight to the tree.
Prim(Graph G, while (!IsEmpty(Q)) { u=deletemin(Q); Weights w, Vertex t) for each vertex v Ӊ Adj(u) { if (vӉQ and for each vertex uV[G] { w(u,v)
January 5, 2006
January 5, 2006
Borahan Tümer, Ph.D.
37
Kruskal’s Algorithm
Borahan Tümer, Ph.D.
Kruskal(Graph G, Weights w) { for each vertex uV[G] { make each vertex to a single-element tree; } sort edges in ascending order by their weight w; for each edge (u,v) E if (u and v are in two different trees) { add (u,v) to the MST; combine both trees; } dist [u]=0; return;
39
References • [1] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, “Introduction to Algorithms,” 2nd Edition, 2003, MIT Press • [2] M.A. Weiss, “Data Structures and Algorithm Analysis in C,” 2nd Edition, 1997, Addison Wesley
January 5, 2006
Borahan Tümer, Ph.D.
38
Kruskal’s Algorithm
• Kruskal’s Algorithm is another greedy algorithm. • It is about finding the least weight and connecting with that two trees in the forest. • Initially, there exists a forest of many singlenode trees.
January 5, 2006
Borahan Tümer, Ph.D.
41
January 5, 2006
Borahan Tümer, Ph.D.
40