Week -7-8
Topic - Graph Algorithms
CSE – 5311
Prepared by:-
Sushruth Puttaswamy
Lekhendro Lisham
Contents
Different Parts of Vertices used in Graph Algorithms
Analysis of DFS
Analysis of BFS
Minimum Spanning Tree
Kruskal’s Algorithm
Shortest Path’s
Dijkshitra’s Algorithm
Different Parts of Vertices
(used in Graph Algorithms)
Vertices of the Graph are kept in 3
Visited parts as below:
Visited : Vertices already selected.
Fringe
Fringe : Vertices to be considered for
Unvisited
next selection.
Unvisited: Vertices yet to consider as a
possible candidate.
For DFS, the Fringe Part is kept in a STACK while for BFS
QUEUE is used.
Brief Description of DFS
Explores a graph using greedy method.
Vertices are divided into 3 parts as it proceeds i.e. into
Visited, Fringe & Unvisited
Fringe part is maintained in a Stack.
The path is traced from last visited node.
Element pointed by TOS is the next vertex to be considered
by DFS algorithm to select for Visited Part.
Data Structures use in DFS
a b e
b d c
V a d
Graph with 5 Vertices
F b a c e
U c d b e
F d a e c TOS
b
U e b d c d
(U/V/F) Adjacency list Fringe
1-D Array
(Stack)
Analysis of DFS
For a Graph G=(V, E) and n = |V| & m=|E|
When Adjacency List is used
Complexity is O(m+n)
When Adjacency Matrix is used
This again requires a stack to maintain the fringe & an
array for maintaining the state2 of a node.
Scanning each row for checking the connectivity of a
Vertex is in order O(n).
So, Complexity is O(n2).
Applications of DFS
To check if a graph is connected. The algorithm ends when the
Stack becomes empty.
• Graph is CONNECTED if all the vertices are visited.
• Graph is DISCONNECTED if one or more vertices
remained unvisited.
Finding the connected components of a disconnected graph.
Repeat 1 until all the vertices become visited. Next vertex can also be
taken randomly.
Check if a graph is bi-connected (i.e. if 2 distinct paths exist between
any 2 nodes.).
Detecting if a given directed graph is strongly connected
( path exists between a-b & b-a).
Hence DFS is the champion algorithm for all connectivity problems
Analysis of BFS
Fringe part is maintained in a Queue.
The trees developed are more branched &
wider.
When Adjacency List is used
Complexity is O(m+n)
When Adjacency Matrix is used
This requires a Queue to maintain the fringe & an array for
maintaining the state of a node.
Scanning each row for checking the connectivity of a Vertex is in
order O(n).
So, Complexity is O(n2).
Minimum Spanning Tree (MST)
A spanning tree of a connected Graph G is a
sub-graph of G which covers all the vertices of G.
A minimum-cost spanning tree is one whose edge
weights add up to the least among all the spanning
trees.
A given graph may have more than one spanning
tree.
DFS & BFS give rise to spanning trees, but they
don’t consider weights.
Properties MST
The least weight edge of the graph is
always present in the MST.
w3
Proof by contradiction: w2
c
Let this be a MST. Also let us assume d h
that the shortest edge is not part of w1
this tree. Consider node g & h.
All edges on the path between these
g CONTRADICTION
nodes are longer.(w1,w2,w3)
Let us take any edge (ex-w1) & delete
it. We will then connect g & h directly.
But this edge has a lighter weight then
already existing edges which is a
contradiction.
…. Properties of MST
For any pair of vertices a & b, the edges
along the path from a to b have to be
greater than the weight of (a,b).
Kruskal’s Algorithm
An algorithm to find the minimum spanning tree of
connected graph.
It makes use of the previously mentioned
properties.
Step 1: Initially all the edges of the graph are sorted
based on their weights.
Step2: Select the edge with minimum weight from the
sorted list in step 1.Selected edge shouldn’t form a
cycle. Selected edge is added into the tree or
forest.
Step 3: Repeat step 2 till the tree contains all nodes of
the graph.
…. Kruskal’s Algorithm
This algorithm works because when any edge is
rejected it will be longer than the already existing
edge(s).
The Union-Find data structure is tailor made to
implement this algorithm.
Cycle formation between any 2 vertices a & b is
checked if Find(a)=Find(b).
Applet Demo Link.
Analysis of Kruskal’s Alg.
If an adjacency list is used.
We have n vertices & m edges the following steps are
followed.
Sort the edges – mlogm
Find operation – 2m= O(m)
Union
2 - n-1= O(n)
O(mlogm)= O(mlogn )= O(mlog n).
If we use path compression then find & union become
m times inverse Ackerman’s function.
But sorting always takes mlogm time.
Shortest Paths
The problem is to find shortest paths among
nodes.
There are 3 different versions of this problem as
shown below:
1. Single source single destination shortest path (SSSP)
2. Single source all destinations shortest path (SSAP).
3. All pairs shortest path.
For un-weighted graphs:
BFS can be used for 1.
BFS can used to for 2.
Running BFS from all nodes is presently the best algorithm
for 3.
Dijkshitra’s Algorithm
This is an algorithm for finding the shortest path in
a weighted graph.
It finds the shortest path from a single source node
to all other nodes.
The shortest path from a single node to all
destinations is a tree.
The following applet gives a very good
demonstration of the Dijkshitra’s Algorithm. It finds
the shortest distances from 1 city to all the
remaining cities to which it has a path.
Applet
…. Dijkshitra’s Algorithm
DIJKSTRA (G, w, s)
1. INITIALIZE-SINGLE-SOURCE(G, s)
2. S ← ø
3. Q ← V[G]
4. while Q ≠ ø
5. do u ← EXTRACT-MIN(Q)
6. S ← S U {u }
7. for each vertex v Є Adj[u] do
8. if d[v] > d[u] + w (u, v)
9. then d[v] ← d[u] + w (u, v)
10. π [v] ← u
The algorithm repeatedly selects the vertex u with the minimum
shortest-path estimate, adds u to S, and relaxes all edges leaving
u.
…. Analysis of Dijkshitra’s Alg.
For a Graph G=(V, E) and n = |V| & m=|
E|
When Binary Heap is used
Complexity is O((m+n) log n)
When Fibonacci Heap is used
Complexity is O( m + n log n)
Thank you.
