1
UNIT – V
Syllabus: Graph, Graph Representation, Graph Traversals, Connected Components, Basic
Searching Technique, Minimal Spanning Tree
Graph
1) A graph is a collection of vertices(nodes) connected to each other through a set of edges.
2) The study of graphs is known as Graph Theory.
3) A graph is non-linear data structure.
4) A graph is defined as ordered pair of a set of vertices and set of
edges.5) G = (V, E)
Her, V is set of vertices and E is set of edges connecting the vertices.
In this graph,
V={A,B,C,D ,E}
E = { AB , AC , BD , CD , DE }
2
3
[Type here] [Type here] [Type here]
4
Graph Terminology
1) Vertices: A Vertex, often referred to as a Node, is a fundamental unit of a graph. It represents an
entity within the graph. Every node/vertex can be labeled or unlabeled.
2) Edges: An Edge is a connection between two vertices in a graph. It can be either directed or
undirected. In a directed graph, edges have a specific direction, indicating a one-way connection
between vertices. In contrast, undirected graphs have edges that do not have a direction and
represent bidirectional connections.
3) Adjacent vertices: Two vertices are called adjacent if there is an edge between them. In the
following graph G, (A,C), (A, B) and (B, C) are adjacent vertices.
4) Order of a graph O(G): Number of vertices in a graph.
5) Size of a graph S(G): Number of edges in a graph.
6) Loop: In graph theory, a loop is an edge that connects a vertex to itself.
7) Outgoing Edges: Outgoing edges of a vertex are directed edges that the vertex is the origin.
8) Incoming Edges: Incoming edges of a vertex are directed edges that the
vertex is the destination.
9) Degree: It represents the total no of edges connected to a vertex
10) Walk: A walk is a sequence of vertices and edges of a graph i.e. if we traverse a graph then we
get a walk. Edge and Vertices both can be repeated.
11) Trail: A trail is an open walk in which no edge is repeated, though vertices may be repeated.
12) Path: A path is a trail in which neither vertices nor edges are repeated.
Graph Representation
a) A graph representation is a technique to store graph into the memory of computer.
b) There are different ways to optimally represent a graph, depending on the
density of its edges, type of operations to be performed and ease of use.
[Type here] [Type here] [Type here]
5
1) Adjacency Matrix
2) Incidence Matrix
3) Adjacency List
1. Adjacency Matrix
a) Adjacency matrix is a sequential representation.
b) It is used to represent which nodes are adjacent to each other. i.e. is there any
edge connecting nodes to a graph.
c) An adjacency matrix is a 2D array of V x V vertices. Each row and column represent a
vertex.
d) If the value of any element a[i][j] is 1, it represents that there is an edge
connecting vertex i and j.
2. Incidence Matrix
a) In Incidence matrix representation, graph can be represented using a matrix of
size: Total number of vertices by total number of edges.
b) It means if a graph has 4 vertices and 6 edges, then it can be represented using a
matrix of4X6 class.
c) In this matrix, columns represent edges and rows represent vertices.
d) This matrix is filled with either 0 or 1 or -1.
e) 0 is used to represent row edge which is not connected to column vertex.
f) 1 is used to represent row edge which is connected as outgoing edge to column vertex.
g) -1 is used to represent row edge which is connected as incoming edge to column vertex.
[Type here] [Type here] [Type here]
6
3. Adjacent List
a) Adjacency list is a linked representation.
b) In this representation, for each vertex in the graph, we maintain the list of its
neighbors. It means, every vertex of the graph contains list of its adjacent
vertices.
c) We have an array of vertices which is indexed by the vertex number and for each
vertex v, the corresponding array element points to a singly linked list of
neighbors of v.
Graph Traversal Techniques
Graph traversal is a technique used for a searching vertex in a graph.
The graph traversal is also used to decide the order of vertices is visited in the
search process.
A graph traversal finds the edges to be used in the search process without
creating loops. There are two graph traversal techniques, and they are as
follows...
1. DFS(Depth First Search)
DFS traversal of a graph produces a spanning tree as result.
Spanning Tree is a graph without loops.
We use Stack data structure with maximum size of total number of vertices in the
graph to implement DFS traversal.
We use the following steps to implement DFS traversal.
Step 1 - Define a Stack of size total number of vertices in the graph.
Step 2 - Select any vertex as starting point for traversal. Visit that vertex and push it on to
the Stack
Step 3 - Visit any one of the non-visited adjacent vertices of a vertex which is at the top of
stack and push it on to the stack.
[Type here] [Type here] [Type here]
7
Step 4 - Repeat step 3 until there is no new vertex to be visited from the vertex which is at the
top of the stack.
Step 5 - When there is no new vertex to visit then use back tracking and pop one vertex from
the stack.
Step 6 - Repeat steps 3, 4 and 5 until stack becomes Empty.
Step 7 - When stack becomes Empty, then produce final spanning tree by removing unused
edges from the graph
2. BFS (Breath First Search)
BFS traversal of a graph produces a spanning tree as result.
Spanning Tree is a graph without loops.
We use Queue data structure with maximum size of total number of vertices in the
graph to implement BFS traversal.
We use the following steps to implement BFS traversal...
Step 1 - Define a Queue of size total number of vertices in the graph.
Step 2 - Select any vertex as starting point for traversal. Visit that vertex and insert it into the
Queue.
Step 3 - Visit all the non-visited adjacent vertices of the vertex which is at front of the
Queue and insert them into the Queue.
Step 4 - When there is no new vertex to be visited from the vertex which is at front of the
Queue then delete that vertex.
Step 5 - Repeat steps 3 and 4 until queue becomes empty.
Step 6 - When queue becomes empty, then produce final spanning tree by removing unused
edges from the graph.
[Type here] [Type here] [Type here]
8
DFS
9
1
0
BFS
11
Spanning Tree:
A spanning tree is a subset of the graph, in which the vertices are covered with
minimum possible number of edges is known as spanning tree.
a spanning tree does not have cycles and it cannot be disconnected.
Properties of Spanning tree
a. A connected graph G can have more than one spanning tree.
b. If there are n vertices in the graph, then each spanning tree has n − 1 edges
(Multiplicity Property).
c. All possible spanning trees of graph G, have the same number of edges and vertices.
d. The spanning tree does not have any cycle (loops).
e. Removing one edge from the spanning tree will make the graph disconnected,
i.e. the spanning tree is minimally connected (Cut Property).
f. Adding one edge to the spanning tree will create a circuit or loop, i.e. the
spanning tree is maximally acyclic (Cyclic Property).
Applications of Spanning Tree
1)
Civil network planning
2)
Computer network routing protocol
3)
Cluster Analysis
4)
Measuring homogeneity of two-dimensional materials
5)
Comparing ecotoxicology data
6)
Circuit designing
7)
Topological observability in power systems
Weighted Graph
1) A Weighted graph is a simply graph where every edge having a weight or number.
2) It is also known as edge weighted graph.
12
Minimal Spanning Tree
A minimum spanning tree is a spanning tree in which the sum of the weight of the
edges isas minimum as possible.
There are two algorithms to find minimal spanning tree, they are
1) Prim’s Algorithm
2) Kruskal's Algorithm
1. Prim’s Algorithm
a) Prim's algorithm is used to find minimum cost spanning tree, it uses greedy approach.
b) It shares a similarity with the shortest path algorithms.
c) It treats every node as a single tree and keeps on adding new nodes to spanning trees
from the given graph.
d) To apply prim’s algorithm, the given graph must be weighted, connected and undirected.
Algorithm or Procedure
1) Remove all loops and parallel edges
2) Choose any arbitrary node as root node, that vertex connecting to the edge
having least weight
3) Check out going edges and select one with less cost
4) Keep continue this process until all vertices covered with less cost edges.
Example:
13
2. Kruskal's Algorithm
1) Kruskal’s Algorithm is a famous greedy algorithm.
2) It is used for finding the Minimum Spanning Tree (MST) of a given graph.
3) To apply Kruskal’s algorithm, the given graph must be weighted, connected and undirected.
4) The main target of the algorithm is to find the subset of edges by using
which, we can traverse every vertex of the graph
Algorithm or Procedure
1) Remove all loops and parallel edges
2) Arrange all edges in their increasing order of weight
3) Add the edge which has least weightage
4) Continue this process until all vertices should cover with min cost edges
Example:
Step 1:
Step 2:
tep 4:
S
Step 3:
14
Step 5: Step 6:
Step 7:
Weight of the MST
= Sum of all edge weights
= 10 + 25 + 22 + 12 + 16 + 14
= 99 units
Graph Applications:
1. Social Media Analysis:
Social media sites create a lot of real-time data. Using graphs, we can find trends, understand people’s
feelings, and spot important users. This helps in marketing, customer support, and managing a company’s
image.
2. Network Monitoring:
Graphs help track network traffic live. This lets network managers find slow areas, security problems, or
other issues. It’s important to keep networks running smoothly.
3. . Financial Trading:
Graphs are used to study live financial data like stock prices and market movements. This helps traders
spot patterns and make quick decisions, which is very important in fast trading.
4. IoT (Internet of Things) Management:4.
IoT devices produce a lot of data in real-time. Graphs help find patterns, improve device performance,
and detect unusual behaviour. This helps manage large numbers of devices.
5. Autonomous Vehicles:
Graphs help self-driving cars understand their surroundings using data from sensors. This helps the cars
move safely and make decisions in real-time.
6. Disease Surveillance:
Graphs can show how diseases spread. This helps health workers detect outbreaks early and take action,
especially during pandemics.
15
Real-Life Example – Facebook:
On Facebook, each user is a point (node), and connections between friends are lines (edges). For example, if A is
friends with B, and B is friends with C, then there’s a chain of connections—just like a graph.
