Graph:
A graph is made up of vertices (or nodes) and edges. Vertices are used to represent
entities, while edges are used to represent the relationship between the entities. An
edge connects two vertices, meaning that there is a relationship between the two
vertices. Graphs are used to represent problems that involve objects that are related to
each other by means of relationships.
Graphs are used to show the relationship between different objects in the real world,
such as a map that shows cities as vertices and roads as edges that join the vertices
together, or a social network that shows people as vertices and edges that join the
vertices together to show friendship.
Mathematical Notation:
G=(V,E)
Where,
● V represents the set of vertices. The number of vertices in a graph is expressed
as |V|=n, which is known as the order of the graph.
● E represents the set of edges that connect the vertices of the graph. The number
of edges in a graph is expressed as |E|=m, which is known as the size of the
graph.
Types of Graph:
● Direction
○ Undirected
○ Directed
● Weighting
○ Unweighted
○ Weighted
Undirected Graph:
In an undirected graph, the edges are undirected, and this implies that the connection between
two nodes is bidirectional. If there is a connection between node A and node B, it implies that
both nodes are equally connected. In representation, an edge in an undirected graph is
represented by an unordered pair {u, v}. The symmetry property applies in undirected graphs,
and this implies that if vertex A is connected to vertex B, then vertex B is also connected to
vertex A.
Directed Graph:
In a directed graph, the edges are directed in a specific manner and are using arrows. The
connection between the vertices is from the source vertex to the target vertex. An edge is
shown as an ordered pair (u, v), which indicates that the edge is from vertex u to vertex v. Unlike
the undirected graph, the directed graph is not symmetric. If vertex A is connected to vertex B, it
doesn’t imply that vertex B is connected to vertex A.
Weighted Graph:
In a weighted graph, every edge has a weight or cost associated with it. The weight or
cost is a value that shows the distance, cost, time, or any other relevant information
based on the problem being solved. Unlike an unweighted graph, where all edges are
considered to be of equal importance, in a weighted graph, the values associated with
the edges are used to determine the importance of the edges. Weighted graphs are
used in solving shortest path problems, where the minimum cost or distance needs to
be calculated.
Unweighted Graph:
An unweighted graph is a graph where no weight or cost is assigned to the edges of the graph.
All edges are considered to be of equal weight, and this weight is usually taken as 1. In an
unweighted graph, the only thing that matters is the existence of a connection between the
vertices and not the cost or any other parameter. This type of graph is used in situations where
the connection between the nodes is binary, i.e., either there is a connection or there is no
connection.
Graph Terminologies:
Graphs have several terminologies and concepts associated with them. Here are some
key graph terminologies:
● Vertex( Node )
● Edge
● Degree of Vertex
● Cyclic and Acyclic Graph
● Connected and Disconnected Graph
● Complete Graph
Vertex (Node):
A vertex is an individual element or entity in a graph.
Edge:
An edge represents the connection or relationship between two vertices.
Degree of Vertex(Undirected Graph):
The degree of vertex in an undirected graph is the number of edges connected to the
vertices/nodes.
Degree of Vertex(Undirected Graph):
In directed graph, there are two degrees for each node:
● In Degree: the numbers of edges coming towards.
● Out Degree: The number of edges going outwards.
Cyclic Graph:
A cyclic graph contains at least one cycle which is a path that starts and ends at the
same vertex/node.
Acyclic Graph:
An acyclic graph is a graph that does not have any cycles in it. Which means that it is
not possible to begin at a vertex and travel through connected vertices to reach the
same vertex.
Connected Graph:
A connected graph is a graph in which there is a path between every pair of vertices.
Disconnected Graph:
It consists of multiple connected components, each of which is a connected subgraph
but connected as a pair of vertices.
Complete Graph:
A graph in which every pair of distinct vertices is connected by an edge. It has the
maximum possible number of edges for a given number of vertices.
Is a complete graph always cyclic?
- Yes
Graph Representation:
A graph can be represented in many ways; these two standard structures are primarily
used to represent graphs in computer memory, chosen based on graph density and
required operations.
● Adjacency Matrix
● Adjacency List
Adjacency Matrix:
A Adjacency Matrix is a square matrix (2D array of size |V| x |V| where both rows and
columns represent vertices) used to represent a graph. In an adjacency matrix, the row
and columns represent the vertices of the graph.
If there is an edge between vertex i and vertex j, the value of the matrix is usually 1 (or
the weight of the edge in a weighted graph). If there is no edge, the value is 0.
M[i][j] = 1 (or weight) if edge exists
M[i][j] = 0 (or ∞) otherwise
Space Complexity: O(V²)
Operations Efficiency: Edge Check: O(1) (Instant), Find Neighbors: O(V) (Must scan
entire row)
Adjacency List:
An adjacency list is a method of representing a graph using a list to store the neighbors
of each vertex. In this form of representation, each vertex maintains a list of all vertices
that are directly connected to it through an edge.
Adjacency Matrix VS. Adjacency List:
Graph Traversal:
● Traversing a graph means visiting all the vertices (nodes) and edges
(connections) of a graph in a systematic way to perform some operation or
gather information about the graph.
● Graph traversal is an essential operation in graph theory and various algorithms
are used to traverse graphs based on specific requirements.
● The two most common methods for graph traversal are
○ Breadth-First Search (BFS) , and
○ Depth-First Search (DFS)
Breadth-First Search (BFS):
In BFS, the traversal begins from a source vertex and visits all its neighboring vertices
before moving to the next level of vertices. It employs a queue data structure to store
the vertices that need to be visited. BFS is typically used for finding the shortest path
between vertices in an unweighted graph, determining the reachability between
vertices, and performing level order traversal of a graph.
Depth-First Search (DFS):
DFS stands for Depth-First Search. It is a graph traversal algorithm that traverses a
graph very deeply by visiting a node and then traversing as far as possible down every
branch before backing up. It keeps on traversing the unvisited nodes of the adjacent
vertices until it reaches a dead end and then goes back to explore other possibilities.
DFS is usually implemented by using recursion or a stack data structure.
Breadth-First Search (BFS) VS. Depth-First Search (DFS):
Spanning Tree:
A spanning tree is a subgraph of a connected, undirected graph that contains all the
vertices of the original graph. In other words, a spanning tree connects all the vertices of
the graph using the minimum number of edges such that there is exactly one simple
path between any two vertices. A spanning tree of a graph always has n − 1 edges if the
graph has n vertices.
If the original graph has m edges, then the maximum number of edges that can be
removed to still have the graph connected is given by:
Maximum removable edges: m-(n-1), where m is total number of edges, n is total
number of vertices
Possible number of spanning tree can be calculated by:
Max Spanning trees: n^(n−2), where n is total number of vertices
Properties of Spanning Tree:
❖Connected Graph
➢ A graph is said to be connected if there is a path between every pair of
vertices in the graph. A spanning tree preserves this connectivity property.
❖No Cycles
➢ In a spanning tree, there are no closed loops or cycles. This means you
can’t start at one vertex, follow edges, and return to the same vertex
without repeating any edges.
❖Every Vertex Included
➢ A spanning tree includes all the vertices from the original graph. It does
not leave out any vertex.
❖Minimally Connected
➢ A spanning tree is a minimally connected subgraph because it has the
fewest number of edges required to maintain connectivity between all the
vertices.
Application of Spanning Tree:
❖Network Design
➢In computer networking, spanning trees are used to prevent loops and
ensure that data packets don’t endlessly circulate in a network. The most
commonly used algorithm for this is the Spanning Tree Protocol (STP).
❖Algorithms
➢ Spanning trees are used as a crucial data structure in various algorithms,
like Kruskal’s algorithm and Prim’s algorithm for finding the minimum
spanning tree of a weighted graph.
❖Routing
➢ In computer networks, spanning trees can be used to find efficient routes
of paths for data transmission, such as in shortest path algorithms.
❖Cluster Analysis
➢ In data analysis and clustering algorithms, spanning trees can help
discover hierarchical relationships in data.
Minimum Spanning Tree (MST):
Minimum Spanning Tree (MST) is a spanning tree of a given connected weighted graph
with the minimum total weight of the edges. As a weighted graph may have more than
one spanning tree with different total weights, the minimum spanning tree is the
spanning tree with the smallest total weight of the edges among all possible spanning
trees. Like any spanning tree, it connects all vertices, has no cycles, and has exactly
n-1 edges where n is the number of vertices.
One of the most common applications of MST is in the design of networks, for example,
the installation of fiber cables connecting cities. The aim is to connect all the cities while
using the least amount of cable.
Characteristic Of Minimum Spanning Tree (MST):
Key characteristics of a minimum spanning tree:
❖Connected
➢ Like any spanning tree, a minimum spanning tree must connect all the
vertices in the graph.
❖Acyclic
➢ It is a tree, which means it does not contain any cycles or closed loops
❖Weight Minimized
➢ The total sum of edge weights in a minimum spanning tree is minimized.
This means that if you were to add up the weights of all the edges in the
MST, it would be less than or equal to the total weight of any other
spanning tree of the same graph.
Algorithms for finding Minimum Spanning Tree:
There are two commonly used algorithms for finding the minimum spanning tree of
weighted graph are:
❖Kruskal’s Algorithm
❖Prim’s Algorithm
Kruskal’s Algorithm:
Kruskal’s algorithm is a greedy algorithm that finds the Minimum Spanning Tree (MST)
for a connected weighted undirected graph. The algorithm selects edges with the lowest
weights and adds them to the spanning tree, as long as they do not form a cycle.
To begin with, each vertex is considered to be an individual tree. The algorithm sorts all
edges in order of increasing weight and then selects the edge with the lowest weight
that connects two different trees. This continues until all vertices are connected and the
spanning tree contains exactly (n-1) edges.
Kruskal’s algorithm employs a Disjoint Set (Union-Find) data structure to check for
cycles when adding edges.
Steps of Kruskal’s Algorithm:
1. Sort Edge
○ Sort all the edges of the graph in an increasing order of their weights. This
will enable the algorithm to choose the smallest weighted edges.
2. Check and Select
○ Select the smallest edge (u,v) from the list of sorted edges. Check if the
two vertices are in different groups by using the Find operation. If they are
in different groups, add the edge to the spanning tree and merge the
groups by using Union. If they are in the same group, ignore the edge
since adding it will form a cycle.
3. Union Sets
○ If the two vertices belong to different groups, then add the edge to the
MST and combine the two groups using the Union operation. Repeat the
above step until (n − 1) edges are added to the MST.
Complexity Analysis of Kruskal’s Algorithm:
Time Complexity: O(E log E) or O(E log V) where, E is the number of edges and V is
the number of vertices. Sorting takes O(E log E).
Space Complexity: O(V+E) to store the edges and the Disjoint set.
Prim’s Algorithm:
Prim’s algorithm is another greedy algorithm used to find the minimum spanning tree of
connected, weighted graphs. Unlike Kruskal’s algorithm, which starts with an empty set
of edges, Prim’s algorithm begins with a single arbitrary vertex and repeatedly grows
the spanning tree by adding the next smallest edge that connects the tree to a new
vertex. This process continues until all vertices are included in the tree.
Steps of Prim’s Algorithm:
1. Initialize
a. Choose any vertex as the initial vertex(root) and include it in the MST.
2. Find the Minimum Edge
a. Identify the minimum edge with the lowest weight that has one vertex in
the MST and the other vertex in the non-MST region.
3. Add the Edge
a. Add the minimum edge to the MST and include the new vertex in the MST.
4. Repeat
a. Continue the process until all vertices are included in the MST, which will
have (n-1) edges.
Complexity Analysis of Prim’s Algorithm:
Time Complexity: Using Binary Heap: O(E log V)
Space Complexity: O(V+E) to store the graph and the priority queue.
Dijkstra’s Algorithm:
Dijkstra’s algorithm is a greedy algorithm that solves the single-source shortest paths
problem of a weighted graph. It finds the shortest path between a single source vertex
and all other vertices in the graph.
Key Points of Dijkstra’s Algorithm:
● Single-source Shortest Path
○ It finds the shortest path from a single source vertex to all other vertices in
the graph.
● Relaxation Mechanism
○ The algorithm continuously checks the neighboring vertices and tries to
find a shorter path to them.
● No Negative Weight
○ Dijkstra’s algorithm can only be applied to graphs that have non-negative
weights. It can not be applied to graphs with negative weights.
Steps of Dijkstra’s Algorithm:
1. Initialize
a. The distance of the source vertex is set to 0 and the distance of all other
vertices is set to infinity(∞).
2. Mark Unvisited
a. All vertices are marked as unvisited, and they are added to a Priority
Queue(Min-Heap) with their current distance values.
3. Select the Minimum
a. The unvisited vertex u with the minimum current distance is selected
4. Relax the Edges
For each neighbor v of vertex u:
a. The distance from the source to v through u is calculated.
b. If the calculated distance is less than the current distance of v, the
distance of v is updated.
5. Finalize
a. Vertex u is marked as visited. After the vertex is visited, its shortest
distance is fixed and will never change.
6. Repeat
a. The process is repeated until all the vertices are visited or the target
vertex is reached.
Complexity Analysis of Dijkstra’s Algorithm:
Like Prim’s, the efficiency depends on the Priority Queue:
Time Complexity: Using Binary Heap: O((E+V) log V)
Space Complexity: O(V) to store distances and the parent pointers.