UNIT - 5 GRAPH
Unit – V GRAPH
GRAPH:
Definition:A graph G is a set of vertices (V) and set of edges (E).
The set V is finite, nonempty set of vertices. The set E is a set of pairs of vertices
representing edges. G = (V, E).
The set representation for each of these graphs are given by
V(G1) = {A, B, C, D, E, F}
V(G2) = {A, B, C, D, E, F}
V(G3) = {A, B,C}
E(G1) = {(A,B), (A,C), (B,C), (B,D), (D,E), (D,F), (E,F)}
E(G2) = {(A,B), (A,C), (B,D), (C,E), (C,F)}
E(G3) = {(A,B), (A,C), (C,B)}
Applications
Graphs have many important applications as shown below:
Analysis of electrical circuit
Finding shortest routes
Project planning
To represent highway structures
Communication lines
Railway lines
BASIC TERMINOLOGIES:
1. Directed Graph (or) Digraph:
A graph containing ordered pair of vertices is called a directed graph.
Page 1
UNIT - 5 GRAPH
Directed graph is a graph which consists of directed edges, where each edge in E is
unidirectional. It is also referred as Digraph.
The set of vertices V = {1, 2, 3, 4, 5}
The set of Edges E = {(1,3), (1,5), (2,1), (2,4), (3,4), (4,5)}
2. Undirected Graph:
An undirected graph is a graph, which consists of undirected edges.
A graph containing unordered pair of vertices is called an undirected graph.
The set of Vertices V = {1, 2, 3, 4, 5}
The set of Edges E = {(1,2), (1,3), (1,5), (2,4), (3,4), (4,5)}
3. Complete Graph:
A complete graph is a graph in which there is an edge between every pair of vertices.
A complete graph with N vertices has N(N-1)/2 edges.
4. Weighted Graph:
A graph is said to be weighted graph if every edge in the graph is assigned a weight or
value. It can be directed or undirected graph.
Page 2
UNIT - 5 GRAPH
5. Degree of a Vertex:
The total number of edges linked to a vertex is called its degree.
Indegree: The indegree of a vertex is the total number of edges coming to that node.
Outdgree: The outdgree of a node is the total number of edged going out from that node.
Source: A vertex, which has only outgoing edges and no incoming edges, is called a source.
Sink: A vertex having only incoming edges and no outgoing edges is called sink.
Pendant: When indegree of a vertex is one and outdegree is zero then such a vertex is called
Pendant vertex.
Isolated: When the degree of a vertex is zero, it is an isolated vertex.
6. Connected Graph
A graph is said to be connected if there exists a path between every pair of vertices Vi and Vj.
7. Subgraph:
A subgraph of G is a graph G1 such that V (G1) is a subset of V (G) and E (G1) is a subset of
E (G).
Page 3
UNIT - 5 GRAPH
8. Path:
A path from vertices V0 to V1 is a sequence of vertices V0, V1, V2….Vn-1, Vn.
Here V0 is adjacent to V1 and Vn-1 is adjacent to Vn.
The length of a path is the number of edges on the path.
A path with n vertices has a length of n-1.
9. Loops
An edge of the form (V, V) is known as self edge or self loop.
10. Spanning Tree:
A spanning tree of a graph G = (V, E) is a connected subgraph of G having all
vertices of G and no cycles in it.
If the graph G is not connected then there is no spanning tee of G.
A graph may have multiple spanning trees.
Page 4
UNIT - 5 GRAPH
11. Minimal Spanning Tree:
The cost of a graph is the sum of the costs of the edges in the weighted graph.
A spanning tree of a group G = (V, E) is called a minimal cost spanning tree or simply
the minimal spanning tree of G if its cost is minimum.
G → A sample weighted graph
T1 → A spanning tree of G with cost 5 + 9 = 14
T2 → A spanning tree of G with cost 10 + 9 = 19
T3 → A spanning tree of G with cost 5 + 10 = 15
Therefore T1 with cost 14 is the minimal cost spanning tree of the graph G.
12. Cycle:
A cycle in a graph is a path in which first and last vertex are same. A graph which has
cycle is referred to as cyclic graph.
Graph Representation:
Graph can be represented by Adjacency Matrix and Adjacency list.
Page 5
UNIT - 5 GRAPH
Adjacency Matrix
One simple way to represents a graph is Adjacency Matrix.
The adjacency Matrix A for a graph G = (V, E) with n vertices is an n x n matrix, such that
A[i][j] = 1, if there is an edge Vi to Vj
A[i][j] = 0, if there is no edge.
Adjacency Matrix for Undirected Graph
Adjacency Matrix for Directed Graph
Adjacency Matrix for Weighted Graph:
For weighted graph, the matrix adj[ ][ ] is represented as:
If there is an edge between vertices i and j then adj[i][j] = weight of the edge (i, j) otherwise
adj[i][j] = 0.
An example of representation of weighted graph is given below:
Page 6
UNIT - 5 GRAPH
Adjacency List Representation:
A graph can also be represented using a linked list. For each vertex, a list of adjacent
vertices is maintained using a linked list.
It creates a separate linked list for each vertex Vi in the graph G = (V, E).
Adjacency list of a graph with n nodes can be represented by an array of pointers.
Each pointer points to a linked list of the corresponding vertex.
Graph Traversal:
Most of graph problems involve traversal of a graph. Traversal of a graph means
visiting each node and visiting exactly once.
There are two types of traversal in graphs i.e. Depth First Search (DFS) and Breadth
First Search (BFS).
Page 7
UNIT - 5 GRAPH
DEPTH FIRST SEARCH:
Depth First Search (DFS) algorithm traverses a graph in a depthward motion and uses a stack
to remember to get the next vertex to start a search, when a dead end occurs in any iteration.
1.
It is like tree. Traversal can start from any vertex, say Vi.
2.
Vi is visited and then all vertices adjacent to Vi are traversed recursively using DFS.
3.
Since, a graph can have cycles. We must avoid revisiting a node.
4.
To do this, when we visit a vertex V, we mark it visited.
5.
A node that has already been marked as visited should not be selected for traversal.
Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Push it in
a stack.
Rule 2 − If no adjacent vertex is found, pop up a vertex from the stack. (It will pop
up all the vertices from the stack, which do not have adjacent vertices.)
Rule 3 − Repeat Rule 1 and Rule 2 until the stack is empty.
Step Traversal Description
Initialize the stack.
Page 8
UNIT - 5 GRAPH
2 Mark S as visited and put it onto the
stack.
Explore any unvisited adjacent node
from S.
We have three nodes and we can pick
any of them.
For this example, we shall take the
node in an alphabetical order.
3
Mark A as visited and put it onto the
stack.
Explore any unvisited adjacent node
from A.
Both S and D are adjacent to A but we
are concerned for unvisited nodes
only.
4
Visit D and mark it as visited and put
onto the stack.
Here, we have B and C nodes, which
are adjacent to D and both are
unvisited.
However, we shall again choose in an
alphabetical order.
Page 9
UNIT - 5 GRAPH
We choose B, mark it as visited and
put onto the stack.
Here B does not have any unvisited
adjacent node.
So, we pop B from the stack.
We check the stack top for return to
the previous node and check if it has
any unvisited nodes.
Here, we find D to be on the top of the
stack.
Only unvisited adjacent node is
from D is C now.
So we visit C, mark it as visited and put
it onto the stack.
Page 10
UNIT - 5 GRAPH
#include<stdio.h>
#include<conio.h>
void DFS(int);
int G[10][10],visited[10], n; //n is no of vertices and graph is sorted in array G[10][10]
void main()
{
int i,j;
printf("Enter number of vertices:");
scanf("%d",&n);
printf("\nEnter adjecency matrix of the graph:");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&G[i][j]);
for(i=0;i<n;i++)
visited[i]=0;
DFS(0);
}
void DFS(int i)
{
int j;
printf("\n%d",i);
visited[i]=1;
for(j=0;j<n;j++)
if(!visited[j]&&G[i][j]==1)
DFS(j);
}
BREADTH FIRST TRAVERSAL:
Breadth First Search (BFS) algorithm traverses a graph in a breadthward motion and uses a
queue to remember to get the next vertex to start a search, when a dead end occurs in any
iteration.
Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Insert it in a
queue.
Rule 2 − If no adjacent vertex is found, remove the first vertex from the queue.
Page 11
UNIT - 5 GRAPH
Rule 3 − Repeat Rule 1 and Rule 2 until the queue is empty.
Step Traversal Description
Initialize the queue.
We start from visiting S (starting
node), and mark it as visited.
We then see an unvisited adjacent
node from S. In this example, we have
three nodes but alphabetically we
choose A, mark it as visited and
enqueue it.
Page 12
UNIT - 5 GRAPH
Next, the unvisited adjacent node
from S is B. We mark it as visited and
enqueue it.
Next, the unvisited adjacent node
from S is C. We mark it as visited and
enqueue it.
Now, S is left with no unvisited
adjacent nodes. So, we dequeue and
find A.
From A we have D as unvisited
adjacent node. We mark it as visited
and enqueue it.
Page 13
UNIT - 5 GRAPH
At this stage, we are left with no unmarked (unvisited) nodes. But as per the algorithm we
keep on dequeuing in order to get all unvisited nodes. When the queue gets emptied, the
program is over.
Minimum Spanning Tree
Prim’s Algorithm
Page 14
UNIT - 5 GRAPH
Page 15
UNIT - 5 GRAPH
Page 16
UNIT - 5 GRAPH
Page 17
UNIT - 5 GRAPH
Page 18
UNIT - 5 GRAPH
Page 19
UNIT - 5 GRAPH
Page 20
UNIT - 5 GRAPH
Kruskal’s algorithm
In Kruskal’s algorithm, sort all edges of the given graph in increasing order. Then it
keeps on adding new edges and nodes in the MST if the newly added edge does not
form a cycle.
Below are the steps for finding MST using Kruskal’s algorithm:
1. Sort all the edges in non-decreasing order of their weight.
2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so
far. If the cycle is not formed, include this edge. Else, discard it.
3. Repeat step#2 until there are (V-1) edges in the spanning tree.
The graph contains 9 vertices and 14 edges. So, the minimum spanning tree
formed will be having (9 – 1) = 8 edges.
After sorting:
Weight Source Destination
1 7 6
2 8 2
2 6 5
4 0 1
4 2 5
6 8 6
7 2 3
7 7 8
Page 21
UNIT - 5 GRAPH
8 0 7
8 1 2
9 3 4
10 5 4
11 1 7
14 3 5
Now pick all edges one by one from the sorted list of edges
Step 1: Pick edge 7-6. No cycle is formed, include it.
Add edge 7-6 in the MST
Step 2: Pick edge 8-2. No cycle is formed, include it.
Page 22
UNIT - 5 GRAPH
Add edge 8-2 in the MST
Step 3: Pick edge 6-5. No cycle is formed, include it.
Add edge 6-5 in the MST
Step 4: Pick edge 0-1. No cycle is formed, include it.
Add edge 0-1 in the MST
Step 5: Pick edge 2-5. No cycle is formed, include it.
Page 23
UNIT - 5 GRAPH
Add edge 2-5 in the MST
Step 6: Pick edge 8-6. Since including this edge results in the cycle, discard it. Pick
edge 2-3: No cycle is formed, include it.
Add edge 2-3 in the MST
Step 7: Pick edge 7-8. Since including this edge results in the cycle, discard it. Pick
edge 0-7. No cycle is formed, include it.
Page 24
UNIT - 5 GRAPH
Add edge 0-7 in MST
Step 8: Pick edge 1-2. Since including this edge results in the cycle, discard it. Pick
edge 3-4. No cycle is formed, include it.
Add edge 3-4 in the MST
Since the number of edges included in the MST equals to (V – 1), so the algorithm
stops here
Page 25
UNIT - 5 GRAPH
The Shortest Path - Dijkstra’s Algorithm
Dijkstra’s algorithm finds the shortest path from a source node to all other
nodes in a weighted graph by iteratively selecting the node with the smallest
tentative distance and updating the distances to its neighbours. It ensures the
shortest path is progressively discovered and is based on the principle of
greedy optimization.
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 neighbor, 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.
Working of Dijkstra’s Algorithm
Let’s see how Dijkstra’s Algorithm works with an example given below:
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.
Page 26
UNIT - 5 GRAPH
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
Page 27
UNIT - 5 GRAPH
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
Page 28
UNIT - 5 GRAPH
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.
Page 29
