Unit -2 (GRAPHS)

A Graph is a non-linear data structure consisting of vertices and edges. The

vertices are sometimes also referred to as nodes and the edges are lines or arcs
that connect any two nodes in the graph.More formally a Graph is composed
of a set of vertices (V) and a set of edges (E). The graph is denoted by G (V,
E). Graph data structures are a powerful tool for representing and analysing
complex relationships between objects or entities.
Components of a Graph
Vertices: Vertices are the fundamental units of the graph. Sometimes, vertices
are also known as vertex or nodes. Every node/vertex can be labelled or
unlabelled.
Edges: Edges are drawn or used to connect two nodes of the graph. It can be
ordered pair of nodes in a directed graph. Edges can connect any two nodes in
any possible way. There are no rules. Sometimes, edges are also known as
arcs. Every edge can be labelled/unlabelled.
Types Of Graphs
1. Null Graph: A graph is known as a null graph if there are no edges in the
graph.
2. Trivial Graph: Graph having only a single vertex, it is also the smallest
graph possible.
3. Undirected Graph: A graph in which edges do not have any direction. That
is the nodes are unordered pairs in the definition of every edge.
4. Directed Graph: A graph in which edge has direction. That is the nodes are
ordered pairs in the definition of every edge.
5. Connected Graph: The graph in which from one node we can visit any other
node in the graph is known as a connected graph.
6. Disconnected Graph: The graph in which at least one node is not reachable
from a node is known as a disconnected graph.
7. Regular Graph: The graph in which the degree of every vertex is equal to K
is called K regular graph.
8. Complete Graph: The graph in which from each node there is an edge to
each other node.
9. Cycle Graph: The graph in which the graph is a cycle in itself, the degree of
each vertex is 2.

10. Cyclic Graph: A graph containing at least one cycle is known as a Cyclic
graph.
11. Directed Acyclic Graph: A Directed Graph that does not contain any cycle.
12. Bipartite Graph: A graph in which vertex can be divided into two sets such
that vertex in each set does not contain any edge between them.
13. Weighted Graph: A graph in which the edges are already specified with
suitable weight is known as a weighted graph. Weighted graphs can be further
classified as directed weighted graphs and undirected weighted graphs.

Tree v/s Graph: Trees are the restricted types of graphs. Every tree will
always be acyclic graph but not all graphs will be trees. Linked List, Trees,
and Heaps all are special cases of graphs.
Representation of Graphs : There are two ways to store a graph: Adjacency
Matrix & Adjacency List
 Adjacency Matrix: In this method, the graph is stored in the form of the 2D
matrix where rows and columns denote vertices. Each entry in the matrix
represents the weight of the edge between those vertices.
 Adjacency List: This graph is represented as a collection of linked lists.
There is an array of pointer which points to the edges connected to that
vertex.
Basic Operations on Graphs
Below are the basic operations on the graph:
 Insertion of Nodes/Edges in the graph – Insert a node into the graph.
 Deletion of Nodes/Edges in the graph – Delete a node from the graph.
 Searching on Graphs – Search an entity in the graph.
 Traversal of Graphs – Traversing all the nodes in the graph.
Binary Operations on Graphs
Let G1 = (V1, E1) and G2 = (V2, E2) then
 Union of graphs- the union of two graphs (G1 U G2) is defined as the
graph (V1 ∪ V2, E1 ∪ E2).
  Intersection of graphs, G1 ∩ G2 = (V1 ∩ V2, E1 ∩ E2);
 Complement of a graph, G is a graph G’ on the same set of vertices as of
G such that there will be an edge between two vertices (v, e) in G’, if
and only if there is no edge in between (v, e) in G. (i.e. complete graph -
G=g’)
 Cartesian product of graph. (G □ H) of graphs G and H is a graph:
the vertex set of G □ H is the Cartesian product V(G) × V(H) and two
vertices (u,v) and (u' ,v' ) are adjacent in G □ H if and only if either
u = u' and v is adjacent to v' in H, or v = v' and u is adjacent to u' in G.
 Ring sum of graphs, given two graphs G1 = (V1, E1) and G2 = (V2, E2)
we define the ring sum G1 ⊕ G2 = (V1 ∪ V2, (E1 ∪ E2) − (E1 ∩ E2))
with isolated points dropped. So, an edge is in G1 ⊕ G2 if and only if it
is an edge of G! or an edge of G2, but not both.
// consider example of class.

Advantages and Disadvantages:

Advantages:
 Graphs are a versatile data structure that can be used to represent a wide
range of relationships and data structures.
 They can be used to model and solve a wide range of problems,
including pathfinding, data clustering, network analysis, and machine
learning.
 Graph algorithms are often very efficient and can be used to solve
complex problems quickly and effectively.
 Graphs can be used to represent complex data structures in a simple and
intuitive way, making them easier to understand and analyse.
Disadvantages:
 Graphs can be complex and difficult to understand, especially for people
who are not familiar with graph theory or related algorithms.
 Creating and manipulating graphs can be computationally expensive,
especially for very large or complex graphs.
 Graph algorithms can be difficult to design and implement correctly, and
can be prone to bugs and errors.
 Graphs can be difficult to visualize and analyze, especially for very
large or complex graphs, which can make it challenging to extract
meaningful insights from the data.
Graph Traversal : (also known as graph search) refers to the process of
visiting (checking and/or updating) each vertex in a graph. Such traversals are
classified by the order in which the vertices are visited. i.e.BFS, DFS
Breadth First Search (BFS) traversal is an algorithm, which is used to visit
all of the nodes of a given graph. In this traversal algorithm one node is
selected and then all of the adjacent nodes are visited one by one. After
completing all of the adjacent vertices, it moves further to check another
vertex and checks its adjacent vertices again.
BFS_algo(vertices, start)
Input: The list of vertices, and the start vertex.
Output: Traverse all of the nodes, if the graph is connected.
Begin
define an empty queue que
at first mark all nodes status as unvisited
add the start vertex into the que
while que is not empty, do
delete item from que and set to u
display the vertex u
for all vertices 1 adjacent with u, do
if vertices[i] is unvisited, then
mark vertices[i] as temporarily visited
add v into the queue
mark
done
mark u as completely visited
done
End
Depth First Search (DFS)is a graph traversal algorithm. In this algorithm one
starting vertex is given, and when an adjacent vertex is found, it moves to that
adjacent vertex first and try to traverse in the same manner.
DFS-ALGo(vertices, start)
Input: The list of all vertices, and the start node.
Output: Traverse all nodes in the graph.
Begin
initially make the state to unvisited for all nodes
push start into the stack
while stack is not empty, do
pop element from stack and set to u
display the node u
if u is not visited, then
mark u as visited
for all nodes i connected to u, do
if ith vertex is unvisited, then
push ith vertex into the stack
mark ith vertex as visited
done
done
End
Dijkstra’s Shortest Path Algorithm
Dijkstra’s Shortest Path Algorithm which was developed by Dutch computer
scientist Edsger W. Dijkstra in 1956. It is a popular algorithm for solving many
single-source shortest path problems having non-negative edge weight in the
graphs i.e., it is to find the shortest distance between two vertices on a graph.
The algorithm maintains a set of visited vertices and a set of unvisited vertices.
It starts at the source vertex and iteratively selects the unvisited vertex with the
smallest tentative distance from the source. It then visits the neighbours of this
vertex and updates their tentative distances if a shorter path is found. This
process continues until the destination vertex is reached, or all reachable
vertices have been visited.
Dijkstra’s algorithm can work on both directed graphs and undirected graphs as
this algorithm is designed to work on any type of graph as long as it meets the
requirements of having non-negative edge weights and being connected.
 In a directed graph, each edge has a direction, indicating the direction of
travel between the vertices connected by the edge. In this case, the
algorithm follows the direction of the edges when searching for the
shortest path.
 In an undirected graph, the edges have no direction, and the algorithm
can traverse both forward and backward along the edges when searching
for the shortest path.
Algorithm for Dijkstra’s Algorithm:
1. Mark the source node with a current distance of 0 and the rest with infinity.
2. Set the non-visited node with the smallest current distance as the current
node.
3. For each neighbour, N of the current node adds the current distance of the
adjacent node with the weight of the edge connecting 0->1. If it is smaller
than the current distance of Node, set it as the new current distance of N.
4. Mark the current node 1 as visited.
5. Go to step 2 if there are any nodes are unvisited.
How does Dijkstra’s Algorithm works?
Dijkstra’s Algorithm will generate the shortest path from Node 0 to all other
Nodes in the graph.
Consider the below graph:
Dijkstra’s Algorithm
The algorithm will generate the shortest path from node 0 to all the other nodes
in the graph.
For this graph, we will assume that the weight of the edges represents the
distance between two nodes.
As, we can see we have the shortest path from,
Node 0 to Node 1, from
Node 0 to Node 2, from
Node 0 to Node 3, from
Node 0 to Node 4, from
Node 0 to Node 6.
Initially we have a set of resources given below:
The Distance from the source node to itself is 0. In this example the source node
is 0.The distance from the source node to all other node is unknown so we mark
all of them as infinity.
Example: 0 -> 0, 1-> ∞,2-> ∞,3-> ∞,4-> ∞,5-> ∞,6-> ∞.
we’ll also have an array of unvisited elements that will keep track of unvisited
or unmarked Nodes.
Algorithm will complete when all the nodes marked as visited and the distance
between them added to the path. Unvisited Nodes: - 0 1 2 3 4 5 6.
Step 1: Start from Node 0 and mark Node as visited as you can check in below
image visited Node is marked red.

Dijkstra’s Algorithm
Step 2: Check for adjacent Nodes, now we have to choices (Either choose
Node1 with distance 2 or either choose Node 2 with distance 6) and choose
Node with minimum distance. In this step Node 1 is Minimum distance
adjacent Node, so marked it as visited and add up the distance.
Distance: Node 0 -> Node 1 = 2
Dijkstra’s Algorithm
Step 3: Then Move Forward and check for adjacent Node which is Node 3, so
marked it as visited and add up the distance, Now the distance will be:
Distance: Node 0 -> Node 1 -> Node 3 = 2 + 5 = 7

Dijkstra’s Algorithm
Step 4: Again, we have two choices for adjacent Nodes (Either we can choose
Node 4 with distance 10 or either we can choose Node 5 with distance 15) so
choose Node with minimum distance. In this step Node 4 is Minimum distance
adjacent Node, so marked it as visited and add up the distance.
Distance: Node 0 -> Node 1 -> Node 3 -> Node 4 = 2 + 5 + 10 = 17
Dijkstra’s Algorithm
Step 5: Again, Move Forward and check for adjacent Node which is Node 6,
so marked it as visited and add up the distance, Now the distance will be:
Distance: Node 0 -> Node 1 -> Node 3 -> Node 4 -> Node 6 = 2 + 5 + 10 + 2
= 19

Dijkstra’s Algorithm
So, the Shortest Distance from the Source Vertex is 19 which is optimal one
Complexity Analysis:
Time complexity: O((V + E) log V), where V is the number of vertices and E is
the number of edges.
Auxiliary Space: O(V), where V is the number of vertices and E is the number
of edges in the graph.

Floyd-Warshall algorithm
The Floyd-Warshall algorithm, named after its creators Robert Floyd and
Stephen Warshall, is a fundamental algorithm in computer science and graph
theory. It is used to find the shortest paths between all pairs of nodes in a
weighted graph. This algorithm is highly efficient and can handle graphs with
both positive and negative edge weights, making it a versatile tool for solving
a wide range of network and connectivity problems.
NEGATIVE CYCLE: A negative cycle is one in which the overall sum of the
cycle comes negative.

Negative weights are found in various applications of graphs. For example,

instead of paying cost for a path, we may get some advantage if we follow the
path.

Floyd-Warshall Algorithm: is a multi-source shortest path algorithm that

works by computing the shortest path between all pairs of vertices in the graph
using dynamic programming. It is an all pair shortest path algorithm
unlike Dijkstra and Bellman Ford which are single source shortest path
algorithms. This algorithm works for both the directed and undirected
weighted graphs. But it does not work for the graphs with negative cycles. It
follows Dynamic Programming approach to check every possible path going
via every possible node in order to calculate shortest distance between every
pair of nodes.
Idea Behind Floyd Warshall Algorithm:
Suppose we have a graph G[][] with V vertices from 1 to N. Now we have to
evaluate a shortest_Path_Matrix[][] where shortestPathMatrix[i][j] represents
the shortest path between vertices i and j. Obviously the shortest path
between i to j will have some k number of intermediate nodes. The idea
behind Floyd warshall algorithm is to treat each and every vertex
from 1 to N as an intermediate node one by one.
The following figure shows the above optimal substructure property in Floyd
warshall algorithm:
Floyd Warshall Algorithm Algorithm:
 Initialize the solution matrix same as the input graph matrix as a first
step.
 Then update the solution matrix by considering all vertices as an
intermediate vertex.
 The idea is to pick all vertices one by one and updates all shortest paths
which include the picked vertex as an intermediate vertex in the shortest
path.
 When we pick vertex number k as an intermediate vertex, we already
have considered vertices {0, 1, 2, ... k-1} as intermediate vertices.
 For every pair (i, j) of the source and destination vertices respectively,
there are two possible cases.
 k is not an intermediate vertex in shortest path from i to j. We keep the
value of dist[i][j] as it is.
 k is an intermediate vertex in shortest path from i to j. We update the
value of dist[i][j] as dist[i][k] + dist[k][j], if dist[i][j] > dist[i][k] +
dist[k][j]
Pseudo-Code of Floyd Warshall Algorithm :
For k = 0 to n – 1
For i = 0 to n – 1
For j = 0 to n – 1
Distance[i, j] = min(Distance[i, j], Distance[i, k] + Distance[k, j])
where i = source Node, j = Destination Node, k = Intermediate Node
Illustration of Floyd Warshall Algorithm:
Suppose we have a graph as shown in the image:
Step 1: Initialize the Distance[][] matrix using the input graph such that
Distance[i][j]= weight of edge from i to j, also Distance[i][j] = Infinity if there
is no edge from i to j.
Step 2: Treat node A as an intermediate node and calculate the Distance[][] for
every {i,j} node pair using the formula:
=Distance[i][j]=minimum(Distance[i][j],(Distance from i to A)+(Distance
from A to j ))
= Distance[i][j] = minimum (Distance[i][j], Distance[i][A] + Distance[A][j])

Step 3: Treat node B as an intermediate node and calculate the Distance[][] for
every {i,j} node pair using the formula:
= Distance[i][j] = minimum (Distance[i][j], (Distance from i to B) + (Distance
from B to j ))
= Distance[i][j] = minimum (Distance[i][j], Distance[i][B] + Distance[B][j])

Step 4: Treat node C as an intermediate node and calculate the Distance[][] for
every {i,j} node pair using the formula:
= Distance[i][j] = minimum (Distance[i][j], (Distance from i to C) + (Distance
from C to j ))
= Distance[i][j] = minimum (Distance[i][j], Distance[i][C] + Distance[C][j])

Step 5: Treat node D as an intermediate node and calculate the Distance[][] for
every {i,j} node pair using the formula:
= Distance[i][j] = minimum (Distance[i][j], (Distance from i to D) + (Distance
from D to j ))
= Distance[i][j] = minimum (Distance[i][j], Distance[i][D] + Distance[D][j])

Step 6: Treat node E as an intermediate node and calculate the Distance[][] for
every {i,j} node pair using the formula:
= Distance[i][j] = minimum (Distance[i][j], (Distance from i to E) + (Distance
from E to j ))
= Distance[i][j] = minimum (Distance[i][j], Distance[i][E] + Distance[E][j])

Step 7: Since all the nodes have been treated as an intermediate node, we can
now return the updated Distance[][] matrix as our answer matrix.
Why Floyd-Warshall Algorithm better for Dense Graphs and not for Sparse
Graphs?
Dense Graph: A graph in which the number of edges is significantly much
higher than the number of vertices.
Sparse Graph: A graph in which the number of edges is very much low.
No matter how many edges are there in the graph the Floyd Warshall
Algorithm runs for O(V3) times therefore it is best suited for Dense graphs.

Complexity Analysis:
Time Complexity: O(V3), where V is the number of vertices in the graph and
we run three nested loops each of size V
Auxiliary Space: O(V2), to create a 2-D matrix in order to store the shortest
distance for each pair of nodes.

Complete Comparison of Dijkstra’s and Floyd–Warshall algorithms

Comparison
Basis Dijkstra Algorithm Floyd Warshall Algorithm

Introduction Dijkstra’s algorithm is a The Floyd-Warshall

Comparison
Basis Dijkstra Algorithm Floyd Warshall Algorithm

single-source shortest path

algorithm is an all-pairs
algorithm used to find the
shortest path algorithm used
shortest paths from a single
to find the shortest paths
source vertex to all other
between all pairs of vertices
vertices in a weighted
in a weighted graph.
graph.

Greedy approach, as it It uses Dynamic

selects the vertex with the programming, to compute all
Algorithm shortest distance pair shortest paths.

Data It Typically uses a priority It uses a two-dimensional

Structure queue or min-heap. array.

Dijkstra’s algorithm does The Floyd-Warshall

not work correctly with algorithm can handle graphs
Negative graphs that have negative with both positive and
Edges edge weights. negative edge weights.

With a priority queue or The time complexity of the

Time min-heap, time complexity Floyd-Warshall algorithm is
Complexity is O(E + V*log(V)). O(V^3).

The auxiliary space

O(V) with priority queue or
Auxiliary complexity is O(V^2)
min-heap.
Space because of 2D array used.

It is efficient for finding It is suitable for finding

shortest paths from a single shortest paths between all
Use Case source. pairs of vertices
Topological Sorting
Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of
vertices such that for every directed edge u-v, vertex u comes before v in the
ordering.
 DAGs are a special type of graphs in which each edge is directed such that no
cycle exists in the graph.
 Why Topological Sort is not possible for graphs with undirected edges?
o This is due to the fact that undirected edge between two vertices u and
v means, there is an edge from u to v as well as from v to u. Because of
this both the nodes u and v depend upon each other and none of them
can appear before the other in the topological ordering without creating
a contradiction.
 Why Topological Sort is not possible for graphs having cycles?
o Imagine a graph with 3 vertices and edges = {1 to 2 , 2 to 3, 3 to 1}
forming a cycle. Now if we try to topologically sort this graph starting
from any vertex, it will always create a contradiction to our definition.
All the vertices in a cycle are indirectly dependent on each other hence
topological sorting fails.
 Topological sorting is a dependency problem in which completion of one task
depends upon the completion of several other tasks whose order can vary, so
topological sorting is not unique.
 Time Complexity: O(V+E). The above algorithm is simply DFS with an
extra stack. So, time complexity is the same as DFS
Auxiliary space: O(V). The extra space is needed for the stack

The Algorithm
the first node in the topological ordering is selected that node which can't have any incoming
directed edges; it must have an indegree of zero. Because if it had incoming directed edges, then
the nodes pointing to it would have to come first.
So, we'll find a node with an indegree of zero and add it to the topological ordering. Once a node
is added to the topological ordering, we can take the node, and its outgoing edges, out of the
graph. Then, we can repeat our earlier approach: look for any node with an indegree of zero and
add it to the ordering. We’ll keep looping until there aren't any more nodes with indegree zero.
This could happen for two reasons:

 There are no nodes left. We've taken all of them out of the graph and added them to the
topological ordering.
 There are some nodes left, but they all have incoming edges. This means the graph has a
cycle, and no topological ordering exists.

// note: example solved in the class.

Advantages of Topological Sort:

 Helps in scheduling tasks or events based on dependencies.
 Detects cycles in a directed graph.
 Efficient for solving problems with precedence constraints.
Disadvantages of Topological Sort:
 Only applicable to directed acyclic graphs (DAGs), not suitable for cyclic
graphs.
 May not be unique, multiple valid topological orderings can exist.
 Inefficient for large graphs with many nodes and edges.
Applications of Topological Sort:
 Task scheduling and project management.
 Dependency resolution in package management systems.
 Determining the order of compilation in software build systems.
 Deadlock detection in operating systems.
 Course scheduling in universities.