Graphs and Graph algorithms

Prof Rajan Kumar

1
 Graphs
Graph
A data structure that consists of a set of nodes
and a set of edges that relate the nodes to each
other
Vertex
A node in a graph
Edge (arc)
A connection between
two nodes in a graph,
represented by a pair
of vertices.

2
 Graphs

Undirected graph
A graph in which the edges have no direction

Directed graph (digraph)

A graph in which each edge is directed from one
vertex to another (or the same) vertex

3
 Graphs

Formally a graph G is defined as follows

G = (V,E)
where
V(G) is a finite, nonempty set of vertices
E(G) is a set of edges (written as pairs
of vertices)

4
 Graphs

Vertex

Undirected
Graphs
have no
arrows
Edge or arc
on the
edges

5
Graphs

6
Graphs

What
other
structure
is this
?
A tree is a
acyclic
graph.

7
 Graphs

Adjacent vertices
Two vertices in a graph that are connected by an edge
Path
A sequence of vertices that connects two nodes in a graph
Complete graph
A graph in which every vertex is directly connected to every
other vertex; For a graph with N nodes,
• N*(N-1) edges in a complete directed graph
• N*(N-1)/2 edges in a complete undirected graph
Weighted graph
A graph in which each edge carries a value
8
 Graphs

How many edges in How many edges in an

a directed graph with undirected graph with
N vertices? N vertices?
9
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.

Multi Graph
If there are numerous edges between a pair of vertices in a graph G= (V, E), the
graph is referred to as a multigraph. There are no self-loops in a Multigraph.

10
 Weighted Graph
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.

Null Graph
It's a reworked version of a trivial graph. If several vertices but no edges
connect them, a graph G= (V, E) is a null graph.

11
Application of Graphs in Data Structures
Following are some applications of graphs in data structures:

•Graphs are used in computer science to depict the flow of

computation.

•Users on Facebook are referred to as vertices, and if they are

friends, there is an edge connecting them. The Friend Suggestion
system on Facebook is based on graph theory.

•Web pages are referred to as vertices on the World Wide Web.

Suppose there is a link from page A to page B that can represent
an edge. This application is an illustration of a directed graph.

•Graph transformation systems manipulate graphs in memory

using rules. Graph databases store and query graph-structured
data in a transaction-safe, permanent manner.
12
 Python code for creating a simple Graph
using NetworkX package

import networkx as nx
import matplotlib.pyplot as plt

# Creating a graph
G = nx.Graph()

# Adding nodes
nodes = ['A', 'B', 'C', 'D', 'E']
G.add_nodes_from(nodes)

# Adding edges
edges = [('A', 'B'), ('A', 'C'), ('B', 'D'), ('C', 'E'), ('D', 'E')]
G.add_edges_from(edges)

# Drawing the graph

nx.draw(G, with_labels=True, font_weight='bold')
plt.show()
13
 Classification of searching
algorithms in Graphs

Uninformed Informed or Greedy

Breadth First Search A* Algorithm

Depth First Search Dijkstra algorithm

Uniform cost First

Search

Bi-directional Search
14
 Un-Informed search
Breadth-First Search (BFS)
• Unlike trees, graphs may contain cycles, so we may come to
the same node again. To avoid processing a node more than
once, we divide the vertices into two categories:
• Visited and
• Not visited.
• A boolean visited array is used to mark the visited vertices.
For simplicity, it is assumed that all vertices are reachable
from the starting vertex. BFS uses a queue data
structure for traversal
 Implementation of BFS traversal:
• Follow the below method to implement BFS traversal.
• Declare a queue and insert the starting vertex.
• Initialize a visited array and mark the starting vertex as visited.
• Follow the below process till the queue becomes empty:
• Remove the first vertex of the queue.
• Mark that vertex as visited.
• Insert all the unvisited neighbours of the vertex into the queue.
 Un-Informed search
Uniform-Cost Search
Uniform-cost search is a searching algorithm used for
traversing a weighted tree or graph. This algorithm
comes into play when a different cost is available for
each edge. The primary goal of the uniform-cost search
is to find a path to the goal node which has the lowest
cumulative cost. Uniform-cost search expands nodes
according to their path costs form the root node.
 Un-Informed search

Depth-First Search

Depth-First Search or DFS algorithm is a recursive

algorithm that uses the backtracking principle. It
entails conducting exhaustive searches of all
nodes by moving forward if possible and
backtracking, if necessary. To visit the next node,
pop the top node from the stack and push all of its
nearby nodes into a stack.
Difference between BFS and DFS
 Bidirectional search algorithm
• Bidirectional search algorithm runs two simultaneous searches, one form
initial state called as forward-search and other from goal node called as
backward-search, to find the goal node. Bidirectional search replaces one
single search graph with two small subgraphs in which one starts the
search from an initial vertex and other starts from goal vertex. The search
stops when these two graphs intersect each other.
• Bidirectional search can use search techniques such as BFS, DFS, DLS, etc.

Advantages:
• Bidirectional search is fast.
• Bidirectional search requires less memory
 Greedy algorithms
Greedy algorithms are a class of algorithms that make locally optimal choices at each
step with the hope of finding a global optimum solution. In other words, at each step
of the algorithm, the best decision is made based solely on the information available
at that particular step, without considering the consequences of that decision on
future steps. Greedy algorithms are often used for optimization problems where the
goal is to find the best possible solution from a set of choices.

Key characteristics of greedy algorithms include:

1.Greedy Choice Property: At each step, the algorithm selects the best possible
choice without considering the choices made in previous steps.
2.Optimal Substructure: The problem can be divided into smaller subproblems, and
the optimal solution to the overall problem can be constructed from the optimal
solutions of its subproblems.
3.Lack of Backtracking: Once a decision is made, it is never reconsidered or changed,
even if it leads to a suboptimal solution in the long run.

21
Informed search
The A* Search

• Difficulty: we want to still be able to generate the

path with minimum cost

• A* is an algorithm that:
• Uses heuristic to guide search
• While ensuring that it will compute a path with
minimum cost
“estimated cost”

• A* computes the function f(n) = g(n) + h(n)

“actual cost”
 A* algorithm

• f(n) = g(n) + h(n)

• g(n) = “cost from the starting node to reach n”
• h(n) = “estimate of the cost of the cheapest path
from n to the goal node”
h(n)
20
g(n)
15 n
10 5
15
18
20
25

33
Informed search
A* algorithm
 A* algorithm

Add g(n) of all nodes along the path, and add h(n) of
only destination node while calculating f(n)
 A* algorithm

• Initialization: {(S, 5)}

• Iteration1: {(S--> A, 4), (S-->G, 10)}
• Iteration2: {(S--> A-->C, 4), (S--> A-->B, 7), (S-->G, 10)}
•
Iteration3: {(S--> A-->C--->G, 6), (S--> A-->C--->D, 11), (S--
> A-->B, 7), (S-->G, 10)}
• Iteration 4 will give the final result, as S--->A--->C--->G it
provides the optimal path with cost 6.
 A* algorithm, example to
practice

Start node

End node

The text in the orange colour is heuristic cost of that node 27

Advantages:
• A* search algorithm is the best algorithm than other
search algorithms.
• A* search algorithm is optimal and complete.
• This algorithm can solve very complex problems.
Disadvantages:
• It does not always produce the shortest path as it
mostly based on heuristics and approximation.
• A* search algorithm has some complexity issues.
• The main drawback of A* is memory requirement as it
keeps all generated nodes in the memory, so it is not
practical for various large-scale problems.
 Dijkstra Algorithm

• Dijkstra Algorithm is a very famous greedy algorithm.

• It is used for solving the single source shortest path
problem.
• It computes the shortest path from one particular
source node to all other remaining nodes of the
graph.

29
 Simplified steps of Dijkstra algorithm
1. Initialize: Start at the source node and set its distance to 0. Set the distances of all
other nodes to infinity. Keep track of the shortest distance to each node from the
source.
2. Select Node: Choose the unvisited node with the smallest distance from the
source. This node will be the current node.
3. Update Distances: For the current node, consider all of its unvisited neighbors and
calculate their tentative distances through the current node. Compare the newly
calculated tentative distance to the current assigned value and update it if it's
smaller.
4. Mark as Visited: Once all of the neighbors of the current node have been
considered, mark the current node as visited.
5. Repeat: If the destination node has been marked visited or if the smallest tentative
distance among the nodes is infinity (unreachable) then stop. Otherwise, select
the unvisited node that is marked with the smallest tentative distance, set it as the
new "current node," and repeat steps 3-4.
6. Output: The shortest path distances from the source node to all other nodes have
been found. Optionally, backtrack from the destination node using the recorded
shortest path predecessors to find the shortest path itself.
30
 Simplified steps of Dijkstra algorithm

Single source shortest path algorithm

Condition to be satisfied
If d(u) + C (u,v) < d(v)
Then d(v) = d(u) + C (u,v)

7 4
2
2 1

1 1 2 6

Start node 3
4 5
5 End node
3

31
Practice example on Dijkstra algorithm

32
 Practice example on Dijkstra algorithm
45

Start node
50 10 End node
1 2 4

35
10 15
20 30

4 15 5 6
3

33
 Practice example on Dijkstra algorithm

Start node

End node

34
 Practical uses of Dijkstra algorithm
1. GPS Navigation Systems: Dijkstra's algorithm is extensively used in GPS navigation
systems to find the shortest path between two locations. In this context, nodes
represent intersections or waypoints, and edges represent roads or paths between
them, with weights representing distances or travel times. By applying Dijkstra's
algorithm, GPS devices can compute the shortest route from the user's current
location to their desired destination.
2. Network Routing Protocols: Dijkstra's algorithm is employed in various network
routing protocols, such as OSPF (Open Shortest Path First) and IS-IS (Intermediate
System to Intermediate System), to determine the shortest paths in computer
networks. In these protocols, nodes represent routers or network devices, and edges
represent network links with associated costs (e.g., link bandwidth or latency).
Dijkstra's algorithm ensures efficient data routing by finding the shortest paths
between network nodes.
3. Traffic Management Systems: Dijkstra's algorithm is utilized in traffic management
systems to optimize traffic flow and minimize congestion. Nodes in this context
represent intersections or traffic junctions, and edges represent road segments with
associated travel times or congestion levels. By applying Dijkstra's algorithm, traffic
management systems can identify the most efficient routes for vehicles, thereby
reducing travel times and alleviating congestion.
35
 Minimum Spanning Tree

• A spanning tree of an undirected graph G is a

subgraph of G that is a tree containing all the
vertices of G.
• In a weighted graph, the weight of a subgraph is
the sum of the weights of the edges in the
subgraph.
• A minimum spanning tree (MST) for a weighted
undirected graph is a spanning tree with
minimum weight.
 Prim’s algorithm
• Prim's algorithm is a popular method for finding the minimum spanning tree
of a weighted undirected graph. Here are the steps to perform Prim's
algorithm:
1. Initialize: Start with an empty set of vertices in the minimum spanning tree
(MST), let's call it MSTSet, and select any arbitrary vertex to begin with.
2. Choose Initial Vertex: Add the chosen vertex to the MSTSet.
3. Find Minimum Edge: Repeat the following steps until MSTSet includes all
vertices:
1. For each vertex in MSTSet, find the minimum-weight edge that connects it
to a vertex not in MSTSet.
2. Choose the edge with the minimum weight among all those found in the
previous step.
4. Add Vertex and Edge: Add the selected edge to the MST and the
corresponding vertex to the MSTSet.
5. Repeat: Repeat steps 3 and 4 until all vertices are included in the MSTSet.
6. Termination: When all vertices are included in the MSTSet, the algorithm
terminates, and the resulting set of edges forms the minimum spanning tree.
37
 Prim’s algorithm steps simplified
The spinning tree should have

1.Assume a root node, identify the nodes

connected to root node and select the path
with min cost or weight and continue similar
steps
2.It should have all vertices of original tree
3.All vertices are connected
4.There are no cycles in the newly
generated spanning tree
38
Minimum Spanning Tree using Prim’s
algorithm

An undirected graph and its minimum spanning tree.

Practice graph for Prim’s algorithm for
minimum spinning tree

40
Practice graph for Prim’s algorithm for
minimum spinning tree

41
Practice graph for Prim’s algorithm for
minimum spinning tree (solution)

42
 Kruskal algorithm
Kruskal's algorithm is used to find the minimum spanning tree (MST) of a connected,
undirected graph. Here are the simple steps of Kruskal's algorithm:
1. Sort Edges: Sort all the edges in non-decreasing order of their weights.

2. Initialize MST: Create an empty set to represent the minimum spanning tree (MST).

3. Iterate Through Edges: Iterate through each edge in the sorted order.

4. Check for Cycles: For each edge, check if adding it to the MST would create a cycle.
This can be done by checking if the two vertices of the edge are already in the same
connected component. If adding the edge does not create a cycle, include it in the
MST.

5. Union Operation: If the edge is included in the MST, perform a union operation to
merge the connected co mponents of the two vertices of the edge.

6. Repeat: Repeat steps 3-5 until all vertices are included in the MST or until there are
(V-1) edges in the MST, where V is the number of vertices in the graph.

7. Output MST: The final set of edges forms the minimum spanning tree (MST) of the
graph. 43
 Kruskal algorithm steps simplified
The spinning tree should have

1.Draw the vertices of given graph

2.Take a look on the given weights or costs
3. Start connecting the vertices with lowest cost
4.Make sure that you are not forming a loop while
focusing on the lowest costs
5.Make sure that all vertices are connected with one
edge (line)
6.Calculate the weight, finish
7. No cycles in the spanning tree

44
Example on minimum spinning tree
using Kruskal’s algorithm

45
Practice example on minimum spinning
tree using Kruskal’s algorithm

46