Graphs can either be represented in the form of adjacency matrix representation or adjacency

list representation. The adjacency matrix representation is achieved through arrays and the
adjacency list representation is achieved using linked lists.
Adjacency Matrix Representation
An adjacency matrix is a matrix that keeps the information of adjacent nodes of the graph. The
matrix entry shows whether the node is adjacent to the other node or not. A representation of a
directed graph with n vertices using an n × n matrix is called adjacency matrix, in which the
entry at position (i, j) is 1 if there is an edge from vertex i to vertex j, otherwise, the entry is 0.
A weighted graph is represented using the weight as the entry. An undirected graph is
represented either using the same entry in both locations (i, j) and (j, i) or using an upper
triangular matrix.

In case of non-weighted graph, if the matrix is X then

X[i][j] = 1, if there is an edge between node i to node j
= 0, if there is no edge from node i to node j

In case of a weighted graph, if the matrix is X then

X[i][j] = Weight on edge, if there is an edge between node i to node j
= 0, if there is no edge from node i to node j

Let us consider the directed graph

A
B

C
D

Directed Graph

The corresponding adjacency matrix for this graph is

A B C D

A 0 1 1 0
Adjacency Matrix X = B 0 0 0 1
C 0 0 0 0
D 1 0 1 0
Let us consider the weighted directed graph

A 4
B
5
3 7
9

C
D
8

Directed Graph with weights on the edges

The corresponding adjacency matrix for this graph is

A B C D

A 0 4 3 0
Adjacency Matrix X = B 0 0 0 9
C 5 0 0 0
D 7 0 8 0

Let us consider the undirected graph

6
A E

3 7
8
D
B
C 5
4

Undirected Weighted Graph

A B C D E

A 0 3 0 0 6
Adjacency Matrix X = B 3 0 4 0 7
C 0 4 0 5 8
D 0 0 5 0 0
E 6 7 8 0 0
Adjacency Linked List Representation
In adjacency list representation of a graph, two lists are maintained. The first list keeps the
track of all the nodes in the graph and the second list maintains the list of adjacent nodes for
each node. Suppose there are n nodes in a graph, at first the node list is created to keep
information of all the nodes, then adjacent list is created. Each list will keep the information of
all adjacent nodes of that particular node.

Structure of a header node

Each list has a header node, which is the corresponding node in the first list. The structure of a
node is defined as below:
struct node
{
char key;
struct node *next;
struct node *adj;
};
The first field keeps the key value (name) of a node. The second field keeps the address of the
next node. The third field points to the corresponding neighbour in an adjacency list.

Structure of an edge
The edge keeps the name of destination node and a pointer which points to the next adjacent
node of the header node.

struct edge
{
char destination;
struct edge *link;
};

Consider the following graph

 Node Adjacency List
A B, C, D
B D
C B, D
D A, C

Linked Representation of a graph in figure 8.8b

A spanning tree is a subset of Graph G, which has all the vertices covered with the minimum
possible number of the edges. Hence, a spanning tree does not have cycles and it cannot be a
disconnected graph.
Consider the following graph (figure 8.12)

The various spanning trees from the above graph are as below:

Following are a few properties of a spanning tree connected to the graph G:

i. A spanning tree does not have any cycle.

 ii. A connected graph G can have more than one spanning tree.
iii. All possible spanning trees of graph G, have the same number of edges and vertices.
iv. A spanning tree is minimally connected. Therefore, removing one edge from the
spanning tree will make the graph disconnected,
v. A spanning tree is maximally acyclic. Therefore, adding one edge to the spanning
tree will create a circuit or loop.

Minimum Spanning Tree

A minimum spanning tree (MST) is a subset of the edges of a connected, edge-weighted
undirected graph in which all the vertices are connected together without any cycles and with
the minimum possible total edge weight. That is, it is a spanning tree whose sum of the weights
on its edges is as small as possible.
The first Spanning tree (figure 8.13 (1)) is a minimum spanning tree as it has the minimum
total weight on its edges (4+10+5 = 19).
There are many methods to create a spanning tree from a graph. Prim’s and Kruskal’s
algorithms are widely used to create a minimum spanning tree.

Prim’s Algorithm
The process can be started from any of the vertices of a graph. Start from vertex v1. Label it
with permanent status and the remaining vertices as temporary nodes. Set its distance from the
starting node as 0 as node v1 itself is the starting node. Set distance of the remaining nodes an
infinity.
Now, find the adjacent node to v1 with minimum weight on its edge among all the adjacent
nodes. Add the edge and the node in the spanning tree. For example, if the nodes v2 and v3 are
the adjacent nodes to node v1 and the node v2 has the minimum weight on the edge connecting
v1 and v2, then node v2 and its edge connected to v1 will be added in the spanning tree.
Again, find the node having the least weight on its edge connecting v2, add it and its edge in
the spanning tree. One thing is to be considered that no cycle (loop) should be formed while
adding the edge in the spanning tree. Repeat the process until all the nodes become permanent.
Consider the following graph (figure 8.14):
Initially, label all nodes temporary.

Node Dist Predecessor Status

v1 ∞ 0 Temporary
v2 ∞ 0 Temporary
v3 ∞ 0 Temporary
v4 ∞ 0 Temporary
v5 ∞ 0 Temporary
v6 ∞ 0 Temporary
v7 ∞ 0 Temporary

Label the first node v1 permanent.

v1

[Link] >Distance (v1, v2) ∞ > 2 Relabel v2

[Link] >Distance (v1, v3) ∞ > 5 Relabel v3
Node Dist Predecessor Status
v1 0 0 Permanent
v2 2 v1 Temporary
v3 5 v1 Temporary
v4 ∞ 0 Temporary
v5 ∞ 0 Temporary
v6 ∞ 0 Temporary
v7 ∞ 0 Temporary

From all the temporary nodes, the distance of v2 has the minimum value of Dist, make it
permanent. Now, v2 is the current working node.
[Link] >Distance (v2, v4) ∞ > 3 Relabel v4
[Link] >Distance (v2, v5) ∞ > 8 Relabel v5
[Link] >Distance (v2, v6) ∞ > 7 Relabel v6

Node Dist Predecessor Status

v1 0 0 Permanent
v2 2 v1 Permanent
v3 5 v1 Temporary
v4 3 v2 Temporary
v5 8 v2 Temporary
v6 7 v2 Temporary
v7 ∞ 0 Temporary

From all the temporary nodes, node v4 has the minimum value of Dist, make it permanent.
Now, v4 is our current working node.

[Link] >Distance (v4, v3) 5 > 1 Relabel v3

Node Dist Predecessor Status

v1 0 0 Permanent
v2 2 v1 Permanent
v3 1 v4 Temporary
v4 3 v2 Permanent
v5 8 v2 Temporary
v6 7 v2 Temporary
v7 ∞ 0 Temporary
From all the temporary nodes, node v3 has the minimum value of dist. Make it permanent.
Now, node v3 becomes our current working node.

[Link] < Distance (v3, v5) 8 <12 Do not relabel v5

[Link] > Distance (v3, v7) ∞> 6 Relabel v7

Node Dist Predecessor Status

v1 0 0 Permanent
v2 2 v1 Permanent
v3 1 v4 Permanent
v4 3 v2 Permanent
v5 8 v2 Temporary
v6 7 v2 Temporary
v7 6 v3 Temporary
From all the temporary nodes, node v7 has the minimum value of Dist. Make it permanent.
Now v7 is our current working node.

[Link] > Distance (v7, v5) 8 > 3 Relabel v5

[Link] < Distance (v7, v6) 7 <10 Do not relabel v6

Node Dist Predecessor Status

v1 0 0 Permanent
 v2 2 v1 Permanent
v3 1 v4 Permanent
v4 3 v2 Permanent
v5 3 v7 Temporary
v6 7 v2 Temporary
v7 6 v3 Permanent

From all the temporary nodes, node v5 has the minimum value of Dist. Make it permanent.
Now, v5 is our current working node.

[Link] < Distance (v5, v6) 7 < 9 Do not relabel v6

Node Dist Predecessor Status

v1 0 0 Permanent
v2 2 v1 Permanent
v3 1 v4 Permanent
v4 3 v2 Permanent
v5 3 v7 Permanent
v6 7 v2 Temporary
v7 6 v3 Permanent

From all temporary nodes, node v6 has the minimum value of Dist (in fact, only one node is
temporary at this moment). Make it permanent.
 Node Dist Predecessor Status
v1 0 0 Permanent
v2 2 v1 Permanent
v3 1 v4 Permanent
v4 3 v2 Permanent
v5 3 v7 Permanent
v6 7 v2 Permanent
v7 6 v3 Permanent

As the status of all the nodes has become permanent, stop the process. Below is the resultant
minimum spanning tree (figure 8.14). The total weight on the edges of a minimum spanning
tree (figure 8.14) is 2 + 3 + 1 + 6 + 3 + 7 = 22.

Kruskal’s Algorithm
Kruskal's algorithm is a greedy algorithm that finds a minimum spanning tree for a connected
weighted graph. The algorithm finds a subset of the edges that forms a tree that includes all the
vertices with the condition that the total weight of all the edges is the least in a minimum
spanning tree.
Assume that each vertex is a separate tree and has no father. Examine the edges of a graph and
choose an edge with the minimum weight assigned to it. Insert it in a tree. Choose the second
least weighted edge and insert it only if it is not creating a loop. Repeat the process, until n-1
edges are included in a tree, where n is the total number of vertices in a graph.

Consider the graph (figure 8.15) given below:

Initially, all the vertices are considered to be trees and the root of every vertex is the vertex
itself.

Vertex v1 v2 v3 v4 v5 v6 v7 v8 v9
Father 0 0 0 0 0 0 0 0 0

Step 1:
An edge with the minimum weight on it is to be selected. Edge Selected is v2-v5.
vertex1 = v2, Root of vertex1 = v2
vertex2 = v5, Root of vertex2 = v5
As the roots of both vertices are different, insert edge v2-v5 in a spanning tree.
Label the father of v5 as v2.

Vertex v1 V2 v3 v4 v5 v6 v7 v8 v9
Father 0 0 0 0 v2 0 0 0 0
Step 2:
Edge selected is v3-v6.
vertex1 = v3, Root of vertex1 = v3
vertex2 = v6, Root of vertex2 = v6
As the roots of both vertices are different, insert edge v3-v6 in a spanning tree.
Label the father of v6 as v3.

Vertex v1 v2 v3 v4 v5 v6 v7 v8 v9
Father 0 0 0 0 v2 v3 0 0 0

Step 3:
Edge selected is v1-v4.
vertex1 = v1, Root of vertex1 = v1
vertex2 = v4, Root of vertex2 = v4
As the roots of both vertices are different, insert edge v1-v4 in a spanning tree.
Label the father of v4 as v1.

Vertex v1 v2 v3 v4 v5 v6 v7 v8 v9
Father 0 0 0 v1 v2 v3 0 0 0
Step 4:
Edge selected is v5-v8.
vertex1 = v5, Root of vertex1 = v2
vertex2 = v8, Root of vertex2 = v8
As the roots of both vertices are different, insert edge v5-v8 in a spanning tree.
Label the father of v8 as v5.

Vertex v1 v2 v3 v4 v5 v6 v7 v8 v9
Father 0 0 0 v1 v2 v3 0 v5 0

Step 5:
Edge selected is v1-v2.
vertex1 = v1, Root of vertex1 = v1
vertex2 = v2, Root of vertex2 = v2
As the roots of both vertices are different, insert edge v1-v2 in a spanning tree.
Label the father of v2 as v1.

Vertex v1 v2 v3 v4 v5 v6 v7 v8 v9
Father 0 v1 0 v1 v2 v3 0 v5 0
Step 6:
Edge selected is v4-v7.
vertex1 = v4, Root of vertex1 = v1
vertex2 = v7, Root of vertex2 = v7
As the roots of both vertices are different, insert edge v4-v7 in a spanning tree.
Label the father of v7 as v4.

Vertex v1 v2 v3 v4 v5 v6 v7 v8 v9
Father 0 v1 0 v1 v2 v3 v4 v5 0

Step 7:
Edge selected is v2-v3.
vertex1 = v2, Root of vertex1 = v1
vertex2 = v3, Root of vertex2 = v3
As the roots of both vertices are different, insert edge v2-v3 in a spanning tree.
Label the father of v3 as v2.

Vertex v1 v2 v3 v4 v5 v6 v7 v8 v9
Father 0 v1 v2 v1 v2 v3 v4 v5 0

Step 8:
Edge selected is v5-v6.
vertex1 = v5, Root of vertex1 = v1
vertex2 = v6, Root of vertex2 = v1
As the roots of both vertices are the same, inserting edge v5-v6 will create a loop, which is not
desirable in a tree. Therefore, do not insert edge v5-v6.
Step 9:
Edge selected is v6-v9.
vertex1 = v6, Root of vertex1 = v1
vertex2 = v9, Root of vertex2 = v9
As the roots of both vertices are different, insert edge v6-v9 in a spanning tree.
Label the father of v9 as v6.

Vertex v1 v2 v3 v4 v5 v6 v7 v8 v9
Father 0 v1 v2 v1 v2 v3 v4 v5 v6
A minimum spanning tree should contain n-1 edges, where n is the number of vertices. The
given graph contains 9 vertices; therefore the minimum spanning tree created from this graph
should have 8 edges. Total 8 edges are included after the completion of step 9; therefore we do
not examine the remaining edges and stop the process.
The minimum spanning tree (figure 8.16) has a total weight on its edges =
(5+7+3+1+2+6+4+9) = 37