Chapter 6 : Exploring

Graphs
Syllabus:
Exploring Graphs:
-An introduction using graphs
- Undirected Graph
- Directed Graph
-Traversing graphs
- Depth First Search
- Breath First Search
-Topological Sort
- Connected Components
What’s a Graph?
A bunch of vertices connected by edges.
vertex

1 3

4
edge

Definition: A graph is a collection of two sets V and E where V is a collection of vertices and E
is a collection of edges.
OR

Graph is a data structure which is used to represent relational data.

Graphs are Everywhere
Adjacency as a Graph
Each vertex represents a state, country, etc.
There is an edge between two vertices if the corresponding areas share
a border.

WY NE

CO KS

6-Graphs
When a Graph?
Graphs are a good representation for any collection of objects and binary relation
among them:
- The relationship in space of places or objects
- The ordering in time of events or activities
- Family relationships
- Taxonomy (e.g. animal - mammal - dog)
- Precedence (x must come before y)
- Conflict (x conflicts or is incompatible with y)
- Etc.
 Graph terminology - overview
• A graph consists of
• set of vertices V = {v1, v2, ….. vn}
• set of edges that connect the vertices E ={e1, e2, …. em}
• Two vertices in a graph are adjacent if there is an edge connecting the
vertices.
• Two vertices are on a path if there is a sequences of vertices
beginning with the first one and ending with the second one
• Graphs with ordered edges are directed. For directed graphs, vertices
have in and out degrees.
• Weighted Graphs have values associated with edges.
10
Concepts: Directedness
In a directed graph, the edges are “one-way.” So an edge (u, v) means
a self-loop
you can go from u to v, but not vice versa.

In an undirected graph, there is no direction on the edges: you can go

either way. (Also, no self-loops.)
Concepts: Adjacency
Two vertices are adjacent if there is an edge between them.
For a directed graph, u is adjacent to v iff there is an edge (v, u).

v v
u w u w

u is adjacent to v. u is adjacent to v.
v is adjacent to u and w. v is adjacent to w.
w is adjacent to v.
Concepts: Degree
Undirected graph: The degree of a vertex is the number of edges
touching it. degree 4

For a directed graph, the in-degree is the number of edges entering the
vertex, and the out-degree is the number leaving it. The degree is the
in-degree + the out-degree.

in-degree 2, out-degree 1
Concepts: Path
A path is a sequence of adjacent vertices. The length of a path is
the number of edges it contains, i.e. one less than the number of
vertices.
Is there a path from 1 to 4?
2
What is its length?
1 3 What about from 4 to 1?
How many paths are there from 2
4 to 3? From 2 to 2? From 1 to 1?
We write u  v if there is path from u to v.
We say v is reachable from u.
Concepts: Cycle
A cycle is a path of length at least 1 from a vertex to itself.
A graph with no cycles is acyclic.
A path with no cycles is a simple path.

1 3

The path <2, 3, 4, 2> is a cycle. 4

Concepts: Connectedness
An undirected graph is connected iff there is a path between any two
vertices.
An unconnected graph with
three connected components.

(We say a directed graph is strongly connected iff there is a path

between any two vertices.)
Concepts: Trees
A free tree is a connected,
acyclic, undirected graph.
To get a rooted tree (the kind we’ve used up until
now), designate some vertex as the root.
If the graph is disconnected, it’s a forest.
Facts about free trees:
• |E| = |V| -1
• Any two vertices are connected by exactly one path.
• Removing an edge disconnects the graph.
• Adding an edge results in a cycle.
Graph Size
We describe the time and space complexity of graph algorithms in
terms of the number of vertices, |V|, and the number of edges, |E|.
|E| can range from 0 (a totally disconnected graph) to |V|2 (a directed
graph with every possible edge, including self-loops).
Because the vertical bars get in the way, we drop them most of the
time.
E.g. we write Q(V + E) instead of Q(|V| + |E|).
 Graph representation –
undirected
• Adjacency matrix: if there is an edge from vertex i to j, aij = 1;
else, aij = 0.
• Adjacency list: Adj[v] lists the vertices adjacent to v.

graph Adjacency list Adjacency matrix

ref. Introduction to Algorithms by Thomas Cormen

Graph representation –
directed

graph Adjacency list Adjacency matrix

ref. Introduction to Algorithms by Thomas Cormen

• Dense Graph
• The graph which contains maximum number of edges for connecting vertices
of a graph is called the dense graph.
• Sparse Graph
• The spare graph is a kind of graph having minimum number of edges within it.
Properties of Graph
1. Complete Graph: A graph is said to complete or fully connected if
there is path from every vertex to every other vertex.
• If an undirected graph of n vertices consists of n(n-1)/2 number of edges then
it is called as complete graph.
2. Subgraph
• A subgraph G’ of graph G is a graph such that the set of vertices and set of
edges of G’ are proper subset of the set of edges of G.
3. Connected Graph
• An undirected graph is said to be connected if for every pair of distinct
vertices Vi and Vj in V(G) there is a path from Vi to Vj in G.
Some notes
• Adjacency list representation is usually preferred since it is more
efficient in representing sparse graphs.
• Graphs for which |E| is much less than |V|2
• Adjacency list requires memory of the order of θ(V+E)

• Searching a graph means systematically following the edges of the

graph so as to visit the vertices.
BFS and DFS
• Two techniques are used to perform a traversal on a graph
• It is also called as a searching on a graph.

1. Breadth First Search

2. Depth First Search
Directed Graph:
Undirected Graph
Graph
BFS
DFS
Graph
BFS
DFS
Breadth-First Search
• “Explore” a graph, turning it into a tree
• One vertex at a time
• Expand frontier of explored vertices across the breadth of the frontier
• Builds a tree over the graph
• Pick a source vertex to be the root
• Find (“discover”) its children, then their children, etc.
Breadth-First Search
• Again will associate vertex “colors” to guide the algorithm
• White vertices have not been discovered
• All vertices start out white
• Grey vertices are discovered but not fully explored
• They may be adjacent to white vertices
• Black vertices are discovered and fully explored
• They are adjacent only to black and gray vertices
• Explore vertices by scanning adjacency list of grey vertices
BFS(G, s) // G is the graph and s is the starting node
1 for each vertex u ∈ V [G] - {s}
2 do color[u] ← WHITE // color of vertex u
3 d[u] ← ∞ // distance from source s to vertex u
4 π[u] ← NIL // predecessor of u
5 color[s] ← GRAY
6 d[s] ← 0
7 π[s] ← NIL
8 Q←Ø // Q is a FIFO - queue
9 ENQUEUE(Q, s)
10 while Q ≠ Ø // iterates as long as there are gray vertices. Lines 10-18
11 do u ← DEQUEUE(Q)
12 for each v ∈ Adj[u]
13 do if color[v] = WHITE // discover the undiscovered adjacent vertices
14 then color[v] ← GRAY // enqueued whenever painted gray
15 d[v] ← d[u] + 1
16 π[v] ← u // predecessor of v
17 ENQUEUE(Q, v)
18 color[u] ← BLACK // painted black whenever dequeued
Breadth-First Search: Example
r s t u

   

   
v w x y
Breadth-First Search: Example
r s t u

 0  

   
v w x y

Q: s
Breadth-First Search: Example
r s t u

1 0  

 1  
v w x y

Q: w r
Breadth-First Search: Example
r s t u

1 0 2 

 1 2 
v w x y

Q: r t x
Breadth-First Search: Example
r s t u

1 0 2 

2 1 2 
v w x y

Q: t x v
Breadth-First Search: Example
r s t u

1 0 2 3

2 1 2 
v w x y

Q: x v u
Breadth-First Search: Example
r s t u

1 0 2 3

2 1 2 3
v w x y

Q: v u y
Breadth-First Search: Example
r s t u

1 0 2 3

2 1 2 3
v w x y

Q: u y
Breadth-First Search: Example
r s t u

1 0 2 3

2 1 2 3
v w x y

Q: y
Breadth-First Search: Example
r s t u

1 0 2 3

2 1 2 3
v w x y

Q: Ø
Breadth-First Search: Properties
• BFS calculates the shortest-path distance to the source node
• Shortest-path distance (s,v) = minimum number of edges from s to v, or  if
v not reachable from s

• BFS builds breadth-first tree, in which paths to root represent shortest

paths in G
• Thus can use BFS to calculate shortest path from one vertex to another in
O(V+E) time
 Depth first search
• It searches ‘deeper’ the graph when possible.
• Starts at the selected node and explores as far as possible along each
branch before backtracking.
• Vertices go through white, gray and black stages of color.
• White – initially
• Gray – when discovered first
• Black – when finished i.e. the adjacency list of the vertex is completely examined.
• Also records timestamps for each vertex
• d[v] when the vertex is first discovered
• f[v] when the vertex is finished
Edge Classification
• When vertex u is being explored, edge e = (u,v) is classified based
on the color of v when the edge is first explored:
• e is a tree edge if v is WHITE [for DFS and BFS]
• e is a back edge if v is GRAY [for DFS only]
• for DFS this means v is an ancestor of u in the DFS tree
• e is a forward edge if v is BLACK and [for DFS only] v is a descendent of
u in the DFS tree
• e is a cross edge if v is BLACK and [for DFS only] there is no ancestor or
descendent relationship between u and v in the DFS tree
• Note that:
• For BFS we’ll only consider tree edges.
• For DFS we consider all 4 edge types.
• In DFS of an undirected graph, every edge is either a tree edge or a back
edge.
Depth first search - algorithm
Depth first search –
example
Depth first search - analysis
• Lines 1-3, initialization take time Θ(V).
• Lines 5-7 take time Θ(V), excluding the time
to call the DFS-VISIT.
• DFS-VISIT is called only once for each node
(since it’s called only for white nodes and
the first step in it is to paint the node gray).
• Loop on line 4-7 is executed |Adj(v)| times.
Since, ∑vєV |Adj(v)| = Ө (E), the total cost of
DFS-VISIT it θ(E)

The total cost of DFS is θ(V+E)

BFS and DFS - comparison
• Space complexity of DFS is lower than that of BFS.
• Time complexity of both is same – O(|V|+|E|).
• The behavior differs for graphs where not all the vertices can be reached
from the given vertex s.
• Predecessor subgraphs produced by DFS may be different than those
produced by BFS. The BFS product is just one tree whereas the DFS
product may be multiple trees.
Real-world applications of BFS and DFS
• Social network analysis
• Finds shortest paths between users to identify connections (LinkedIn)
• Identifies clusters or communities based on user interactions (Facebook
groups)
• Recommends friends or connections based on shared interests (Twitter
suggestions)
• Web crawling and indexing
• Discovers and indexes web pages for search engines (Google)
• Identifies broken links or dead ends to maintain website integrity
• Analyzes website structure and connectivity for SEO optimization
• Pathfinding in navigation systems
• Finds shortest routes between locations for GPS navigation (Google Maps)
• Explores all possible paths in a maze or grid for game AI (Pac-Man)
• Generates directions or navigation instructions for users (Waze)
• Resource allocation and scheduling
• Assigns tasks or resources to minimize conflicts in project management (Trello)
• Optimizes resource utilization and efficiency in supply chain management
• Detects and resolves resource deadlocks in operating systems
 Biconnected
Components
and
Articulation Point
Biconnected Components
• A node V of a connected graph is an articulation point if the sub
graph obtained by deleting V and all edges incident to V is no
longer connected.
OR
• A node V in a connected graph is an articulation point if and only
if deletion of vertex V with all edges incident to V divides the
graph into two or more nonempty components.
• A given graph G is biconnected only when it contain no articulation
point.

1 2

5 3

4
Articulation Point in Graph
• In a graph G(V,E) , v is an articulation point if
1. Removal of v in G result in a disconnected graph.
2. If v is an articulation point, then there exist distinct vertices w and x
such that v is in every path from w to x.
Articulation Point
Articulation Point
Algorithm to find A.P.
1. Do depth first search on graph from any node.
• Let T be the tree generated by DFS and for each node v of the graph.
• Let dfn [depth first numbers/Prenum](Discovery time) of v be the number
assigned
by search.
 The number correspond to outside of each vertex is called dfns or prenum.
 These numbers correspond to the order in which a depth first search visits these
vertices. And it referred to as the depth number(dfns).
2. Traverse the tree T in post order for each visited node v calculate
lowest of v as minimum of
a. dfns/Prenum of v
b. dfn/Prenum of w for each node w such that their exists an edge
<v,w> ϵ G that has no corresponding edge in T.
c. Lowest[x] for every child x and v in T.

Lowest[u] = min( dfn[u], min {Low[w] / w is a child of u},

min { dfn[w] / [u,w] is a back edge}
• Articulation is determined as follows:
1. Root[T] is an articulation point if and only if it has more than one
child.
2. A node v other than Root[T] is an articulation point of G if and only
if v has a child x such that
Lowest x (child) >= dfn/Prenum v (parent)

if yes than parent is an articulation point.

Find an Articulation Point(s) from the
below graph.
• Node 1 and 4
Apply the algorithm to find strongly connected
components from the given graph. (Winter 2022
Marks-7)
Graph
Graph and DFS Tree
Graph, DFS tree and Missing edges
Apply Post order
Traversal

6 5 2 3 4 1
 U =6 w=3

Lowest[u] = min( dfn[u], min {Low[w] / w is a child of u},

min { dfn[w] / [u,w] is a back edge}

Lowest[6] = Min{dfn[6],dfn[3]}
= Min{5,3}
=3
 U=5, w=6

3
Lowest[u] = min( dfn[u], min {Low[w] / w is a child of u},
min { dfn[w] / [u,w] is a back edge}

Lowest[5] = Min{dfn[5],lowest[6]}
= Min{4,3}
=3
 3 1

3
Lowest[2] = Min{dfn[2],dfn[1]}
= Min{6,1}
=1
 U=3, w= 5 ,2

Back w= 6

3 1

3
Lowest[u] = min( dfn[u], min {Low[w] / w is a child of u},
min { dfn[w] / [u,w] is a back edge}

Lowest[3] = Min{dfn[3], min{lowest[5],Lowest[2]}, dfn[6]}

= min{ 3, min{3,1},5}
=min{3, 1,5} = 1
 1

3 1

3
Lowest[4] = Min{dfn[4],lowest[3]}
= Min{2,1}
=1
 1

3 1

3
Lowest[1] =
Min{dfn[1],dfn[2],lowest[4]}
= Min{1,6,1}
=1
 1

3 1

3
 1

3 1

3
Topological Sort
Definition: Topological Sort
• A topological sort of a DAG(Directed Acyclic Graph) G = (V, E) is
a linear ordering of all its vertices such that if G contains an
edge (u, v), then u appears before v in the ordering.
• If the graph is not acyclic, then no linear ordering is possible.
¨ A topological sort of a graph can be viewed as an ordering of its
vertices along a horizontal line so that all directed edges go from
left to right.
¨ Topological sorting is thus different from the usual kind of
"sorting" .
• Techniques for Topological sort
1. DFS – based Algorithm
2. Source Removal Algorithm
Topological Sort – DFS based
Algorithm
• The following algorithm topologically sorts a DAG:
• TOPOLOGICAL-SORT(G)
• call DFS(G) to compute finishing times f[v] for each vertex v
(this is equal to the order in which vertices change color from
gray to black)
• as each vertex is finished (turns black), insert it onto the front
of a linked list
• return the linked list of vertices
Assume that Starting Node is B.
 1) 1st apply DFS & Find its finishing time.

2/9 4/7

5/6

1/10
3/8
2) Arrange the vertices from left to right in order of decreasing finishing time.
All the directed edges go from left to right

BADCE

B A D C E
Topological Sort –Source Removal
Algorithm
1. From a given graph find a vertex with no incoming edges. Delete it
along with all the edges outgoing from it. If there are more than
one such vertices then break the tie randomly.
2. Note the vertices that are deleted.
3. All these recorded vertices given topological sorted list.
GTU 2022 Marks 7