Graphs

Module – 6 (A non-linear data structure)

Module No. 6 Graphs

GRAPHS Introduction, Representations of graphs, adjacency list, adjacency matrix, Sparse Matrix. Traversals: BFS
and DFS, Time complexities and Applications. Shortest-path algorithms Single source shortest path; Dijkstra’s,
Minimum spanning tree, Prim’s and Kruskal’s algorithms
Graphs are used in Diverse Industries and Fields

• GPS systems and Google Maps use graphs to find the shortest path
from one destination to another.

• Social Networks use graphs to represent connections between

users.

• The Google Search algorithm uses graphs to determine the

relevance of search results.

• Operations Research is a field that uses graphs to find the optimal

path to reduce the cost of transportation and delivery of goods
and services.

• Even Chemistry uses graphs to represent molecules!!!

Graphs
• Circles and thick lines connecting them. They are called,
respectively, Nodes and Edges.
• Nodes: they are the elements that create the network.
They could represent houses, locations, airports, ports,
bus stops, buildings, users, basically anything that you
could represent as being connected to other similar
elements in a network.

• Edges: they are connections between the nodes. They

could represent streets, flights, bus routes, a connection
between two users in a social network, or anything that
could possibly represent a connection between the nodes
in the context that you are working with.
Graph-Definition

• A graph G(V,E) is defined as set of vertices (nodes) and inter-related

edges (arcs).

• V={v1, v2, v3, v4} , E={e1, e2, e3, e4}

• Unlike trees, graphs can contain cycles

• In fact, a tree is an acyclic graph

Basic Terminologies
Types of Graphs in Data Structures
• Finite Graph
• Directed Graph
• Infinite Graph
• Undirected Graph
• Trivial Graph
• Connected Graph
• Simple Graph
• Disconnected Graph
• Multi Graph
• Cyclic Graph
• Null Graph
• Acyclic Graph
• Complete Graph
• Directed Acyclic Graph
• Pseudo Graph
• Subgraph
• Regular Graph

• Weighted Graph
 Types of Graphs in Data Structures
Directed Graph
• A directed graph also referred to as a digraph, is a set of nodes connected by edges, each with a direction.

Undirected Graph
• An undirected graph comprises a set of nodes and links connecting them. The order of the two connected vertices is
irrelevant and has no direction. You can form an undirected graph with a finite number of vertices and edges.
 Types of Graphs in Data Structures
Weighted Graph / Network
• A graph G= (V, E) is called a labeled or weighted graph because each edge has a value or weight
representing the cost of traversing that edge.

Cyclic Graph
• If a graph contains at least one graph cycle, it is considered to be cyclic. A cycle in a digraph is a path of length at
least 1 with starting and ending nodes being the same.

Length of the cycle:3

Types of Graphs in Data Structures
Acyclic Graph / DAG-Directed Acyclic Graph
When there are no cycles in a graph, it is called an acyclic graph.

Complete Graph
• If a graph G= (V, E) is also a simple graph, it is complete. Using the edges, with n number of vertices must
be connected. It's also known as a full graph because each vertex's degree must be n-1.

V1 V2

V5

V3 V4

A complete graph with n vertices will have (n(n-1))/2 edges.

Basic Terminologies
• Degree of a vertex: no. of incoming edges + no. of outgoing edges of a vertex.

• Indegree of a vertex: no. of edges entering a vertex.

• Outdegree of a vertex: no. of edges leaving a vertex. V1 V2

V5
Vertex Indegree Outdegree Degree
V1 0 4 4
V2 1 3 4 V3 V4

V3 2 2 4
V4 3 1 4
V5 4 0 4

• A node whose indegree is 0- source node (V1)

• A node whose outdegree is 0- sink node (V5)

An isolated vertex is a zero-degree vertex that is not an edge's endpoint

Graph Representation
There are at least two ways of representing graphs.

• The adjacency matrix representation

• The adjacency list representation

Adjacency Matrix

•A sequential representation is an adjacency matrix.

•It's used to show which nodes are next to one another. I.e., is there any connection between nodes in a
graph?
Adjacency Matrix
Undirected Graph Representation Directed Graph Representation
 Adjacency Matrix
Weighted Undirected Graph Representation

• Simple but takes a time complexity of O(n2)

 Adjacency List
• Each vertex has a linked list of edges

• Edge stores destination and label

• Better when the adjacency matrix is sparse

Weighted Undirected Graph Representation Using Linked-List

Uses pointers therefore requires extra memory space

 Adjacency List
Weighted Undirected Graph Representation Using an Array
Operations on Graphs in Data Structures
The operations you perform on the graphs in data structures are listed below:

• Creating graphs

• Insert vertex

• Delete vertex

• Insert edge

• Delete edge
Creating graphs
Adjacency Matrix - The adjacency matrix of a simple labeled graph, also known as the connection matrix, is
a matrix with rows and columns labeled by graph vertices and a 1 or 0 in position depending on whether they
are adjacent or not.

Adjacency List - A finite graph is represented by an adjacency list, which is a collection of unordered lists.
Each unordered list describes the set of neighbors of a particular vertex in the graph within an adjacency
list.
Operations on Graphs in Data Structures
Insert Vertex

Delete Vertex
Operations on Graphs in Data Structures
Insert Edge
• Connecting two provided vertices can be used to add an edge to a graph.

Delete Edge
Graph Traversals
Graph Traversals
• Graph traversal means visiting every vertex and edge exactly once in a
well-defined order.

• Graph Traversals
• Depth First Search (DFS)

• Breadth First Search (BFS)

Depth First Search (DFS)
• Depth first search is a recursive technique to traverse all the nodes of a graph. It makes use of
the stack data structure for traversing and remembering the nodes.

• DFS follows the backtracking approach i.e. whenever there are no more nodes in the current
path, it goes back to the initial node and starts traversing the next available path.

• While using the stack, we first choose the initial node and push all its adjacent nodes into the
stack. To visit a node, we pop a node from the stack and push all its adjacent nodes to the stack.

• This goes on until all the nodes are popped out i.e. the stack is empty. In the whole process, we
need to make sure that we don’t visit the same node more than once, especially if the cycle
exists. The output of DFS is always in the form of a spanning tree.
Depth First Search (DFS)
• Let G = (V, E) is a graph which is represented by an adjacency matrix Adj. Assume that nodes in a
graph record visited/unvisited information.

• Each vertex of a graph in a standard DFS implementation is divided into either of two
categories:
1. Not Visited
2. Visited
The algorithm is used to pinpoint each vertex and mark them as visited and at the same time avoid cycles.

This is how the DFS algorithm works: DFS(G, u)

[Link] = true
1. Put any particular vertex of the graph on a stack. for each v ∈ [Link][u]
if [Link] == false
2. The item on top of the stack should be added to the visited list. DFS(G,v)

3. Make a list of adjoining nodes of that vertex and add those not in the visited init() {
For each u ∈ G
list on the top of the stack. [Link] = false
For each u ∈ G
4. Keep repeating the previous steps till the stack empties. DFS(G, u)
}
Depth First Search (DFS)
Iterative Pseudocode

DFS(G, u):
let St be stack
Push u in the stack
Mark u as visited.
while ( St is not empty)
v = Node at the top of stack
Remove the node from the stack
for all neighbors adj_node of v in Graph G:
if adj_node is not visited :
mark adj_node as visited
push adj_node in stack
Depth First Search (DFS) Example -II

A
Initialize all unvisited node Visited List
B
D A B D

A A
Visited List B Visited List
D
A A B D H
H
H

A A
B B
Visited List Visited List
D F
A B A B D H F
H
Depth First Search (DFS) Example -II

A A Visited List
B C Visited List
B C
D F A B D H F C D F G A B D H F C G
H H

A A
Visited List B C Visited List
B C
D F G D F G
A B D H F C G A B D H F C G
H H

A A
Visited List Visited List
B C B C
D F G A B D H F C G D E F G A B D H F C G E
H H
Depth First Search (DFS) Example -II
Visited List
A
A Visited List
B C A B D H F C G E
B C
A B D H F C G E D E F G
D E F G
H
H

A
B C Visited List
A Visited List
B C D E F G
A B D H F C G E
D E F G A B D H F C G E H
H

A
B Visited List
C
D E F G A B D H F C G E
H
Depth First Search (DFS) Example
Depth First Search (DFS) Example
DFS on a Directed Graph
When you run DFS on a graph, the set of edges the algorithm actually uses to visit every node forms a
tree-like structure.

•Spanning Tree: If the original graph is connected (meaning you can reach every node from the starting
node), the DFS output will be a Spanning Tree. This tree includes all the nodes of the original graph but
only the edges necessary for the traversal.

•Spanning Forest: If the original graph is disconnected (meaning it has multiple separate components),
the DFS output will be a Spanning Forest. This is a collection of two or more spanning trees, one for
each disconnected component.
DFS on a Directed Graph
• The output of the DFS algorithm will be either a spanning tree or a spanning forest depending upon
whether the graph is connected or disconnected.

The possible spanning trees will be

• In the first spanning tree, we have followed A→B→C→D

whereas in the second spanning tree we have followed
A→D→C→B.
Different Types of Edges in DFS
• Tree edge: An edge that is present in the DFS tree after
applying DFS on the graph.

• Forward edge: An edge that is not present in the DFS

tree after applying DFS, and it connects a node “u” to
one of its successors.

• Back edge: An edge that is not present in the DFS tree

after applying DFS, and it connects a node “u” to one of
its ancestors. Its presence indicates a cycle in directed
graphs.

• Cross edge: An edge that is not present in the DFS tree

after applying DFS, and it connects a node “u” to another
node, where there is no parent-child relationship
between the two nodes.
Complexity Analysis for DFS
Time complexity: We need to traverse the whole graph while
implementing DFS. therefore, its time complexity is O(V + E).

Space complexity: The algorithm makes use of an extra array.

Therefore, in the worst case, the space complexity is O(V).
Applications of DFS
• Finding whether two nodes present in a graph belong to the same component

• Checking if the graph is bipartite

• Finding the topological ordering of the vertices of a graph

• Finding the strongly connected components of a graph

• Finding the spanning tree of an unweighted graph

• Finding bridges in graphs

• Finding articulation points in graphs

• Finding a path in a maze and similar puzzles

• Analyzing networks and mapping source-destination route

Breadth First Search Algorithm
• The BFS algorithm starts from a given source vertex and explores the
graph layer by layer, examining all the vertices at the same level before
descending further.

• It uses a queue data structure to maintain the order of exploration,

ensuring that vertices are visited in a breadth-first manner.
Breadth First Search Algorithm
Algorithm for BFS Pseudo-code for BFS:
procedure BFS(Graph, root) is
Step 1: Choose any one node randomly, to start traversing. Let root = explored
Step 2: Visit its adjacent unvisited node. [Link](root)
Step 3: Mark it as visited in the boolean array and display it. while(Queue is not empty):
Step 4: Insert the visited node into the queue. v := [Link]()
if v == goal:
Step 5: If there is no adjacent node, remove the first node
return v
from the queue.
for all edges from v to w in
Step 6: Repeat the above steps until the queue is empty. [Link](v):
if w is not labeled as explored:
label w as explored
[Link](w)
END for
END while
END BFS
Breadth First Search Algorithm - Example
• The next step is to traverse its adjacent
Initially, the queue will be empty
nodes i.e. B and C and place them inside
the queue. When we place the adjacent
node of A in the queue, we will remove A
from the queue and display it.
Breadth First Search Algorithm - Example
Breadth First Search Algorithm – Example II
Complexity of BFS
• Time complexity: Since we are visiting all the nodes exactly once,
therefore, the time complexity is O(V+E).

• Space complexity: The space complexity of the BFS algorithm

is O(V) where V denotes vertices/nodes of the graph.
Applications of Breadth First Search(BFS)
• To find the shortest path between two edges when the path length is equivalent to the number of edges.

• To check whether a graph is bipartite or not

• Used in unweighted graphs to find the minimum cost spanning tree

• To form peer-to-peer network connections

• To find neighboring locations in the GPS navigation system

• To detect cycle in an undirected graph

• To broadcast packets in a network

• To find all the nodes within one connected component in an otherwise disconnected graph
Difference Between BFS and DFS
[Link] BFS DFS
The difference in • BFS constructs a tree level per level. • DFS constructs the tree subtree
Concepts by subtree.
Utilised strategy • It is based on the FIFO principle • It operates on the LIFO
(First in, First Out). principle (Last in First Out).
Appropriate for • BFS is more suited for finding • If there are alternatives away
vertices that are near the provided from the source, DFS is more
source. appropriate.
Traversed Node • Nodes that have been traversed • The seen sites are added to a
Removal multiple times are removed from the stack whenever no more sites
queue. are visited and subsequently
deleted.
Speed • When compared to DFS, BFS is • DFS is faster
slower.
Properties of BFS and DFS
1. Both BFS and DFS when originating from node v in a digraph G create a tree, whose nodes are just those visited by the
algorithm and whose arcs are those traversed. The algorithms BFS and DFS create a forest of trees that spans G.

2. Both the BFS and DFS algorithms run in time O(V+E) when using adjacency list representations of the graphs. When
adjacency matrix format is used, they run in time O(V 2).

3. The call to DFS (v) does not terminate until all nodes reachable from v have been visited.

4. If w is reachable from v and v is visited before w by DFS, then w is a descendant of v in the DFS forest.

5. Suppose that BFS or DFS is run on a digraph G and let (u, v) Є E(G) be an arc of G. This arc is called a tree arc if it
belongs to one of the trees of the forest formed by the search algorithm. There are 3 types of non-tree arcs. The arc is
a forward arc if u is an ancestor of v in the forest (note that they must belong to the same tree). A back arc is the same,
but with “ancestor” replaced by “descendant”. Finally, the arc is a cross arc if neither u nor v is an ancestor of the other
(they may or may not belong to the same tree).

For BFS, forward arcs do not exist. All four types of arcs can arise with DFS.

Note: Tree arc is a forward arc but forward arc is not a tree arc.