Design and Analysis of Algorithm
Unit 6: Graph Algorithms
An introduction using graphs and games, Traversing Trees–
Preconditioning, Depth First Search (DFS), Undirected Graph,
Directed Graph, Breath First Search (BFS),
Applications of BFS and DFS
COMPILED BY
PROF. DHARMESH R. TANK
CE\IT DEPARTMENT, LDRP-ITR
Outline
An introduction using graphs and games,
Traversing Trees– Preconditioning,
▪ Undirected Graph,
▪ Directed Graph,
▪ Depth First Search (DFS),
▪ Breath First Search (BFS),
Applications of BFS and DFS
Intuitive about Graph
Non Liner Data Structure
A graph is a data structure that consists of a set of nodes and a set of
edges that relates to each other
The set of edges describes relationships among the vertices
A graph is a set of nodes (also called vertices) and a set of arcs (also
called edges)
Representation of Graph
A graph G is defined as follows:
G=(V,E)
V(G): a finite, nonempty set of vertices
E(G): a set of edges (pairs of vertices)
In a graph, if number of elements (n) than there possible no of
edges is n * (n -1) / 2 possible edges,
therefore the number of graphs will be 2n(n -1)/2
Types of Graph
1) Undirected Graphs
In an undirected graph the order of pair is unimportant. Hence the
pairs (v1,v2)and (v2,v1) represent same edge.
2) Directed Graphs
In this the order of the vertices is important. This pair is
represented as (v1,v2) where v1 is the tail and v2 is head. Thus
<v1,v2> and <v2,v1> represents different edges.
Terminology of Graphs
A null graph is a graph which contains no members.
A cycle graph is a graph consisting of a single cycle.
A path graph is a graph consisting of a single path.
A weighted graph if it’s edges have been assigned some non-negative
value as weight.
The indegree of node is the number of edges coming to that node.
Continue…
The outdegree of node is the number of edges going outside that node.
Isolated node, If any node has no edges connected with any other node then its
degree will be zero (0).
Adjacent nodes, two nodes are adjacent if they are connected by an edge.
Path, a sequence of vertices that connect two nodes in a graph.
Complete graph, a graph in which every vertex is directly connected to every
other vertex.
Representation of Graph
1) Adjacency Matrix
2) Adjacency List
Adjacency Matrix
Graphs are relations on their vertex sets, can adopt the concept to
represent graphs, we call the representation an Adjacency Matrix.
Adjacency Matrix for undirected graph is always symmetric.
Adjacency Matrix is also used to represent weighted graphs.
Good for dense graphs --|E|~ O(|V|2)
Memory requirements -- O(|V| + |E| ) = O(|V|2 )
Connectivity between two vertices can be tested quickly
Adjacency List
An array of linked lists is used. Size of the array is equal to number of
vertices.
An entry array[i] represents the linked list of vertices adjacent to the ith
vertex.
This representation can also be used to represent a weighted graph,
the weights of edges can be stored in nodes of linked lists.
Good for sparse graphs -- |E|~ O(|V|)
Memory requirements -- O(|V| + |E|)=O(|V|)
Vertices adjacent to another vertex can be found quickly
Example
Adjacency Matrix Adjacency List
Types of Edges
Tree edges are edges in the depth-first forest G. Edge (u,v) is a tree
edge if it was first discovered by exploring edge (u,v).
Back edges are those edges (4,2) connecting a vertex 4 to an ancestor
node 2 in a DFT. We consider self-loops, which may occur in directed
graphs, to be back edges.
Forward edges are those nontree edges (1,8) connecting a vertex
node 1 to node 8 descendant in a DFT.
Cross edges They can go between vertices in the same DFT, as long as
one vertex is not an ancestor of the other, or they can go between
vertices in different depth-first trees.
Example
Graph Traversal
1) DFS (Depth first Search)
2) BFS(Breadth first Search)
DFS (Depth First Search)
Depth-first search (DFS) is an algorithm for traversing or searching a tree,
structure, or graph. One starts at the root (selecting some node as the root in
the graph case) and explores as far as possible along each branch before
backtracking.
DFS can be implemented efficiently using a Stack, in LIFO manner
Back & Tree edges are generate during implementation of DFS
DFS Procedure
Broadly it is divided into 3 steps:
Take a vertex that is not visited yet and mark it visited
Go to its first adjacent non-visited (successor) vertex and mark it
visited
If all the adjacent vertices (successors) of the considered vertex
are already visited or it doesn’t have any more adjacent vertex
(successor) – go back to its parent vertex.(Backtrack)
Pseudocode for DFS (1)
DFS(G) Time Complexity
for each v in V, // for loop V+1 times
- Each node visited
color[v]=white;
once = O(V) time
p[v]=NULL;
time=0; // constant time O(1) - Each edge considered
for each u in V, // for loop V+1 times once = O(E) time
if (color[u]==white)
- Total Time Complexity
DFSVISIT(u) // at most V times O(V)
O(V+E)
Continue…
DFSVISIT(u)
color[u]=gray; // constant time
t[u] = ++time;
for each v in Adj(u) // for loop
if (color[v] == white)
p[v] = u;
DFSVISIT(v); // call to DFSVISIT(v)
color[u] = black; // constant time
f[u]=++time; // constant time
Pseudocode for DFS (2)
Set found to false
stack.Push(startVertex)
do
stack.Pop(vertex)
if vertex == endVertex
Set found to true
else
Push all adjacent vertices onto stack
while !stack.IsEmpty() AND !found
if(!found)
Write "Path does not exist"
Time complexity with Adjacency List &
Adjacency Matrix
For DFS algorithm complexity is as follows:
▪ Adjacency Matrix : O(V2)
▪ Adjacency List : O(V+E)
DFS Example
Continue…
Continue…
BFS(Breadth First Search)
Breadth-first search (BFS) is a graph search algorithm that begins at
the root node and explores all the neighboring nodes. Then for each
of those nearest nodes, it explores their unexplored neighbor nodes,
and so on, until it finds the goal.
BFS can be implemented efficiently using a Queue, in FIFO manner
Only Tree edges are generate during implementation of BFS
BFS Procedure
Basic steps towards exploring a graph using breadth-first search:
Mark all vertices as "unvisited"
Start with first vertex v
Find an unvisited vertex that are adjacent to v , mark them visited
Next consider all recently visited vertices and visit unvisited
vertices adjacent to them
Continue this process till all vertices in the graph are explored
/visited
Pseudocode for BFS(1)
Time Complexity
BFS (G, s)
For all i ≠ s, d[i]=∞; d[s]=0 // at most O(V) times - Each node enqueued
Enqueue (Q,s) and dequeued
// at most O(V) times
while Q ≠ once = O(V)+O(V)
do u Dequeue(Q) time
// at most O(E) times
for each v adjacent to u
do if color[v] = white - Each edge considered
then color[v] gray once = O(E) time
d[v] d[u] + 1
Enqueue(Q,v) // at most O(V) times - Total Time Complexity
color[u] black O(V+E)
Pseudocode for BFS(2)
Set found to false
queue.Enqueue(startVertex)
do
queue.Dequeue(vertex)
if vertex == endVertex
Set found to true
else
Enqueue all adjacent vertices onto queue
while !queue.IsEmpty() and !found
if(!found)
Write "Path does not exist"
Time complexity with Adjacency List &
Adjacency Matrix
For BFS algorithm complexity is as follows:
▪ Adjacency Matrix : O(V2)
▪ Adjacency List : O(V+E)
BFS Example
Continue…
Applications of DFS
Depth First Search :-
Cycle detection
Connectivity testing
Finding a path between v & w in a graph
Finding spanning trees / forest
Applications of BFS
Breath First Search :-
Shortest path
Single Source shortest paths
All Pairs shortest path
Spanning tree
Connectivity
DFS v/s BFS
Parameter DFS BFS
DFS is more risk & aggressive
Traveling Concept BFS is simple & care approach
approach
Storage & Memory Queue (FIFO) & extra memory
Stack(LIFO) & less memory require
requirement require
Edges Back & Tree edges Only Tree edges
Whether it doesn’t follow the path
Path Its follow the traveling path blindly
blindly
Solution Approximation Optimal
Reference
Introduction of Algorithm by Thomas H. Cormen
Thank You
