Algorithmics
CE00333-3
Graph Algorithms
Topics and Lesson Structure
Introduction to graphs Terminologies Types of graphs Graph representation Graph traversal and search techniques
CE00333-3 Algorithmics
Graph Algorithms
Slide 2 (of 44)
Learning outcomes
By the end of this lesson you should be able to:
Define what is a graph Identify the different type of graphs Create the adjacency matrix and adjacency list for a given graph Traverse a graph using depth and breadth first traversal methods Find a given vertex using depth and breadth first search methods
CE00333-3 Algorithmics
Graph Algorithms
Slide 3 (of 44)
Keywords
Graph Directed and undirected graphs Complete graph Cyclic and acyclic graphs Depth and breadth first traversals Depth and breadth first searches
CE00333-3 Algorithmics
Graph Algorithms
Slide 4 (of 44)
Graphs
A graph is defined as follows: G = (V, E) where V(G) is a finite, non-empty set of vertices E(G) is a set (possibly empty) of edges (pair of vertices)
CE00333-3 Algorithmics
Graph Algorithms
Slide 5 (of 44)
Undirected Graphs
An example of an undirected graph: Vertices: C, Y, B, A, M, R and G Edges: {C,Y}, {Y,R}, {R.G}, {B,Y}, {B,A} and {M,A}
A
C
CE00333-3 Algorithmics
Y
Graph Algorithms
G
Slide 6 (of 44)
Directed Graphs
A directed graph is defined as follows: G = (V, E) where V(G) is a finite, non-empty set of vertices E(G) is a set (possibly empty) of directed edges (also called arcs)
CE00333-3 Algorithmics
Graph Algorithms
Slide 7 (of 44)
Directed Graphs
An example of a directed graph:
Vertices: C, Y, B, A, M, R and G Edges: {C,Y}, {Y,R}, {R.G}, {B,Y}, {A,B} and {A,M}
A B
CE00333-3 Algorithmics
Graph Algorithms
Slide 8 (of 44)
Path
A path from vertex Vi to vertex Vj is a
sequence of vertices that connects Vi to Vj . For a path to exist from Vi to Vj, there must be edges (Vi , Vk1),(Vk1, Vk2), ..
(Vkn , Vj). That is, there must be an uninterrupted sequence of lines from Vi through any number of nodes to Vj.
CE00333-3 Algorithmics Graph Algorithms Slide 9 (of 44)
Undirected Path - Example
In the following graph there is a path from vertex A to vertex G (A, B, Y, R, G), and a path from vertex G to vertex A (G, R, Y, B, A).
A B
CE00333-3 Algorithmics
Graph Algorithms
Slide 10 (of 44)
Directed Path - Example
In the following graph there is a path from vertex A to vertex G (A, B, Y, R, G), but not from vertex G to vertex A.
A B
CE00333-3 Algorithmics
Graph Algorithms
Slide 11 (of 44)
Path Length
For a path of k vertices, the length of the path is k-1 or the length of the path is the number of edges in the path.
CE00333-3 Algorithmics
Graph Algorithms
Slide 12 (of 44)
Complete Graphs
A complete graph is one in which every node is connected to every other node. J For example:
A B K N
Complete directed graph
Complete undirected graph
CE00333-3 Algorithmics
Graph Algorithms
Slide 13 (of 44)
Weighted Graphs
A weighted graph is a graph in which each edge carries a value. Weighted graphs are sometimes called networks. Note: Weighted graphs can be used to represent situations in which the value of the connection between the vertices is important, not just the existence of a connection
CE00333-3 Algorithmics
Graph Algorithms
Slide 14 (of 44)
Weighted Graphs
For example:
10 B 20
A 18 30
CE00333-3 Algorithmics
Graph Algorithms
Slide 15 (of 44)
Cyclic and Acyclic Graphs
A path from a node to itself is called a cycle. If a graph contains a cycle, it is cyclic; otherwise it is acyclic. A directed acyclic graph is called a DAG from its acronym.
CE00333-3 Algorithmics Graph Algorithms Slide 16 (of 44)
Cyclic Graphs - Example
An example of a cyclic graph:
B
CE00333-3 Algorithmics
Graph Algorithms
Slide 17 (of 44)
Acyclic Graphs - Example
An example of an acyclic graph:
B
CE00333-3 Algorithmics
Graph Algorithms
Slide 18 (of 44)
Exercise
1. 2. 3. 4. List all vertices in the graph below? How many edges are there in the graph? Is there a path between A and H? What is its length? Is the graph cyclic or acyclic? Why?
H
E
CE00333-3 Algorithmics
A
Graph Algorithms
D
Slide 19 (of 44)
Representation of Graphs
Example of graph: G = (V,E) V = {v1,v2,v3..} E = {(v1,v2),(v2,v3),(v3,v1)..}
Directed graph
1 2 3
Standard representation methods:
1. Adjacency-matrix
2. Adjacency-list
a 1 2 3 4 5 6
1 0 0 0 0 0 0
2 10 0 0 10 0 0
3 0 0 0 0 0 0
41,2=1 means a 5 6 an 0 connects 10 edge0 v to 01 10v2 0 0 10 10 0 0 0 10 0 0 0 0 10
1 2 3 4 5 6
2 5 6 2 4 6
4 / / 5 / / / /
Undirected graph 1 4 2 5 3 6 Quick to find edges Usually used for dense graphs Compact size Usually used for sparse graphs (|E| << |V|2)
(v1,v2) = (v2,v1)
CE00333-3 Algorithmics Graph Algorithms
Representation of Graphs
1. Adjacency-matrix
Memory requirement: (|V|2), or (V2) Directed graph 1 4 2 5 3 6
1 0 1 0 0 1 0 0 0 2 1 0 0 0 1 0 1 0 0 3 0 0 0 0 1 0 1 0
2. Adjacency-list Memory requirement: (|V|+|E|), or (V+E)
1 2 3 4 5 6
1 2 3 4 5 6 4 0 1 1 0 0 0 1 0 0
1 0 0 0 0 0 0
5 0 1 0 1 0 0 1 0 0
2 0 1 0 0 1 0 0 0
6 0 0 1 0 0 0 0
3 0 0 0 0 0 0
1 2 3 4 5 6
4 0 1 0 0 0 0 1 0
5 0 1 0 1 0 0 0 0
1 0 1 0 0 1 0 0 0 2 1 0 0 0 1 1 0 1 0 0
6 0 0 1 0 0 0 1 0
3 4 5 0 1 0 0 Dont 1 0 0 0 1 Care 0 0 1 0 0 0 1 0 1 0 0 1 0 0 0 0 6 0 0 1 0 0 0 0
1 2 3 4 5 6
1 2 3 4 5 6 2 5 6 5 4 3 /
2 5 6 2 4 6
4 / / 5 / / / / 4 1 5 1 2 / / / / /
Undirected graph 1 4 2 5 3 6
4 / 2 / 3 /
CE00333-3 Algorithmics
Graph Algorithms
Representation of Graphs
Adjacency Lists Vertices in adjacency lists are stored in any arbitrary order For a directed graph sum of lengths of all the adjacency list is E For undirected graphs ,the sum of lengths of all the adjacency list is 2E Not a quicker way to determine if a given edge (u,v) is present in a graph
CE00333-3 Algorithmics Graph Algorithms
Graph Traversals
Graph traversal is an algorithm that accesses each vertex in the graph exactly one. 2 graph traversal methods (order):
Depth first traversal Breadth first traversal
CE00333-3 Algorithmics
Graph Algorithms
Slide 27 (of 44)
Breadth-First Search
Breadth-First Search (BFS)
Explores the edges of a graph to reach every vertex from a vertex s, with shortest paths
r s t u v w x y
For r, we do the same to its white color neighbors:
r s t u v w x y
For w, we do the same to its white color neighbors:
s
r v u w
x y
The algorithm: Start by inspecting the source vertex S: So we connect them:
r s t u v w x y
For s, its 2 neighbors are not yet searched
CE00333-3 Algorithmics
r s t u v w x y
Now r and w join our solution
r s t u v w x y
Now v joins our solution
r s t u v w x y
Now t and x join our solution
Graph Algorithms
Breadth-First Search
Using 3 colors: white / gray / black Start by inspecting the source vertex S: So we connect them: For r, we do the same to its white color neighbors: For w, we do the same to its white color neighbors:
r s t u v w x y
For s, its 2 neighbors are not yet searched
r s t u v w x y
Now r and w join our solution
r s t u v w x y
Now v joins our solution No more need to check r, so mark it black. v joins our solution, we need to check it later on, so mark it gray.
r s t u v w x y
Now t and x join our solution No more need to check w, so mark it black. t and x join our solution, we need to check them later on, so mark them gray.
No more need to check Since s is in our s, so mark it black. solution, and it is to be r and w join our inspected, we mark it solution, we need to gray check them later on, so mark them gray.
CE00333-3 Algorithmics
Graph Algorithms
Breadth-First Search
For each vertex u, we keep the data: u.color: black/white/gray u.distance: distance from s to u. u.pred: predecessor of u Q : a First-in-First-out queue to keep those vertices that we need to check them later on Start by putting s into Q, So remove s from Q and check its white neighbors So remove r from Q and check its white neighbors So remove w from Q and check its white neighbors So remove v from Q and check its white neighbors
Qs
r s t u 0 v w x y Looking at Q: the first node to check is s:
CE00333-3 Algorithmics
Q r w
r s t u 1 0 1 v w x y Looking at Q: the first node to check is r
Qw v
r s t u 1 0 2 1 v w x y Looking at Q: the first node to check is w
Graph Algorithms
Qv t x
r s t u 1 0 2 2 1 2 v w x y Looking at Q: the first node to check is v
Q t x
r s t u 1 0 2 2 1 2 v w x y
Looking at Q: the first node to check is t
Breadth-First Search
For each vertex u, we keep the data: u.color: black/white/gray u.distance: distance from s to u. u.pred: predecessor of u Q : a First-in-First-out queue to keep those vertices that we need to check them later on So remove v from Q and check its white neighbors So remove t from Q and check its white neighbors So remove x from Q and check its white neighbors So remove u from Q and check its white neighbors So remove y from Q and check its white neighbors
Q t x
r s t u 1 0 2 2 1 2 v w x y
Looking at Q: the first node to check is t
CE00333-3 Algorithmics
Qx u
r s t u 1 0 2 3 2 1 2 v w x y
Looking at Q: the first node to check is x
Qu y
r s t u 1 0 2 3 2 1 2 3 v w x y
Looking at Q: the first node to check is u
Graph Algorithms
Qy
r s t u 1 0 2 3 2 1 2 3 v w x y
Looking at Q: the first node to check is y
Q
r s t u 1 0 2 3 2 1 2 3 v w x y
Looking at Q: no more nodes to check=> End
BFS(G,s) /*G=(V,E)*/ 1 For each vertex u in V - {s} 2 u.color = white 3 u.distance = (V) 4 u.pred = NIL 5 s.color = gray 6 s.distance = 0 7 s.pred = NIL 8 Q= 9 ENQUEUE(Q,s) 10 while Q 11 u = DEQUEUE(Q) 12 for each v adjacent to u 13 if v.color = white 14 v.color = gray 15 v.distance = u.distance + 1 16 v.pred = u 17 ENQUEUE(Q,v) 18 u.color = black
Breadth-First Search
The running time of BFS is: O(V+E)
Total number of edges kept by the adjacency list is (E) Total time spent in the adjacency list is O(E)
CE00333-3 Algorithmics
Graph Algorithms
Breadth-First Search
PRINT-PATH(G,s,v) /* print the shortest path from s to v */ 1 if v = s 2 print s 3 else 4 if v.pred = NIL 5 print no path from s to v exists 6 else 7 PRINT-PATH(G, s, v.pred) 8 print v
Result of BFS may vary depending on the order in which the vertices are explored .BFS tree may vary ,but the distances computed by the algorithm will not. It computes the smallest distance from s to each reachable vertex Algo. discovers all vertices at distance k from s before discovering any vertices at distance k+1. Gray vertices may have some adjacent white vertices. All vertices adjacent to black vertex will be either gray or black
CE00333-3 Algorithmics Graph Algorithms
Depth-First Search
Depth-First Search (DFS) Explores the edges of a graph by searching deeper whenever possible. DFS(G) /*G = (V,E) */ 1 for each vertex u in V 2 u.color = white 3 u.pred = NIL 4 for each vertex u in V 5 if u.color = white 6 DFS-VISIT(u) DFS-VISIT(u) 1 u.color = gray 2 for each v adjacent to u 3 if v.color = white 4 v.pred = u 5 DFS-VISIT(v) 6 u.color = black
(V) (V) + Time to execute calls to
DFS-VISIT
The running time of DFS is: (V+E)
u x u
v y v
w z w
Total number of edges kept by the adjacency list is (E). Total time spent in the adjacency list is (E).
CE00333-3 Algorithmics
Graph Algorithms
Depth-First Search
DFS(G) /*G = (V,E) */ 1 for each vertex u in V 2 u.color = white 3 u.pred = NIL 4 time = 0 5 for each vertex u in V 6 if u.color = white 7 DFS-VISIT(u) DFS-VISIT(u) 1 u.color = gray 2 time = time + 1 3 u.discover = time 4 for each v adjacent to u 5 if v.color = white 6 v.pred = u 7 DFS-VISIT(v) 8 u.color = black 9 time = time + 1 10 u.finish = time
In many occasions it is useful to keep track of the discovery time and the finishing time while checking each
node.
u 1/8
4/5
v 2/7
3/6
w 9/12
10/11
CE00333-3 Algorithmics
Graph Algorithms
Exercise
Draw an adjacency matrix for the graph shown below.
H
CE00333-3 Algorithmics
Graph Algorithms
Slide 22 (of 44)
Exercise
Draw adjacency lists for the graph shown below.
H
CE00333-3 Algorithmics
Graph Algorithms
Slide 25 (of 44)
Depth First Traversal - Example
The depth first traversal of the following graph, starting at C would result in visiting the following (possible) order of nodes: C, Y, B, A, M, R and G
A
C
CE00333-3 Algorithmics
Y
Graph Algorithms
G
Slide 29 (of 44)
Exercise 1
Apply the depth first traversal algorithm to traverse the graph below, starting at vertex A.
H
E
CE00333-3 Algorithmics
F
Graph Algorithms
D
Slide 31 (of 44)
Exercise 2
Apply the depth first traversal algorithm to traverse the graphs below, starting at vertex a.
CE00333-3 Algorithmics
Graph Algorithms
Slide 32 (of 44)
Breadth First Traversal - Example
The breadth first traversal of the following graph, starting at C would result in visiting the following (possible) order of nodes: C, Y, R, B, G, A, M
A
C
CE00333-3 Algorithmics
Y
Graph Algorithms
G
Slide 34 (of 44)
Exercise 3
Apply the breadth first traversal algorithm to traverse the graph below, starting at vertex A.
H
E
CE00333-3 Algorithmics
F
Graph Algorithms
D
Slide 36 (of 44)
Exercise 4
Apply the breadth first traversal algorithm to traverse the graphs below, starting at vertex a.
CE00333-3 Algorithmics
Graph Algorithms
Slide 37 (of 44)
Graph Search Methods
The depth first traversal method can be applied in depth first search method The breadth first traversal method can be applied in breadth first search method These search techniques are used in problem solving applications
CE00333-3 Algorithmics
Graph Algorithms
Slide 38 (of 44)
Graph Search Methods
The depth first traversal method can be applied in depth first search method The breadth first traversal method can be applied in breadth first search method These search techniques are used in problem solving applications
CE00333-3 Algorithmics
Graph Algorithms
Slide 38 (of 44)
Exercise 5
Apply the depth first search algorithm to determine if there is a path between vertices A and H.
H
E
CE00333-3 Algorithmics
F
Graph Algorithms
D
Slide 40 (of 44)
Summary
What are graphs Types of graphs Graph representation Adjacency matrix Adjacency lists Depth and breadth first graph traversals Depth and breadth first search
CE00333-3 Algorithmics
Graph Algorithms
Slide 43 (of 44)
Next Lesson
Graph Algorithms (Cont.)
Greedy Algorithms
Introduction to Greedy Algorithms and its underpinning concepts
CE00333-3 Algorithmics
Graph Algorithms
Slide 44 (of 44)
