Representation of Graphs: Adjacency Matrix

Representation of Graphs

• There are several representations of graphs, but we will discuss the two commonly used representations called

■ Adjacency Matrix

■ Adjacency Lists

Let us see each one by one.

 

Adjacency Matrix

• Consider a graph G of n vertices and the matrix M. If there is an edge present between vertices V_i and V_j then M[i][j] = 1 else M[i][j] = 0. Note that for an undirected graph if M[i][j] = 1 then for M[j][i] is also 1. Here are some graphs shown by adjacency matrix.

1. Creating a Graph using Adjacency Matrix

• Creation of graph using adjacency matrix is quite simple task. The adjacency matrix is nothing but a two dimensional array. The algorithm for creation of graph using adjacency matix will be as follows:

1) Declare an array of M[size] [size] which will store the graph.

2) Enter how many nodes you want in a graph.

3) Enter the edges of the graph by two vertices each, say V_i, V_j indicates some edge.

4) If the graph is directed set M[i][j] = 1. If graph is undirected set M[i][j] = 1 and M[j][i] = 1 as well.

5) When all the edges for the desired graph is entered print the graph M[i][j].

 

2. Breadth First Traversal of a Graph

• Basic concept : Breadth First Search (BFS) is a graph traversal technique that visits all the vertices level by level, starting from a given source node.

• It explores all immediate neighbors first before moving to the next level.

• For BFS traversal we generally use Queue data structure.

• For the graph to traverse it by BFS we will follow the following logic ‒ Say a vertex V₁ in the graph will be visited first, then all the vertices adjacent to V₁ will be traversed suppose adjacent to V₁ are (V_2, V₃, V_4,...V_n). So V₂, V₃...V_n will be printed first. Then again from V₂ the adjacent vertices will be printed. This process will be continued for all the vertices to get encounterd. To keep track of all the vertices and their adjacent vertices we will make use of Queue data structure. Also we will make use of an array for visited nodes. The nodes which are get visited are set to 1. Thus we can keep track of visited nodes.

• In short in BFS traversal we follow the path in breadthwise fashion. Let us see the algorithm for breadth first search.

Algorithm :

1. Create a graph. Depending on the type of graph i.e. directed or undirected set the value of the flag as either 0 or 1 respectively.

2. Read the vertex from which you want to traverse the graph say V_i

3. Initialise the visited array to 1 at the index of V_i.

4. Insert the visited vertex V_i in the queue.

5. Visit the vertex which is at the front of the queue. Delete it from the queue and place its adjacent nodes in the queue.

6. Repeat the step 5, till the queue is not empty.

7. Stop.

Pseudo code

void Gbfs::bfs(int v₁)

{

int v2;

visit[v1] = TRUE;

front rear = ‒1;

Q[++rear] = v1;

while (front != rear)

{

   v1 = Q[++front];

   cout<<"\n"<<v1;

   for (v2 = 0; v2 < n; v2++)

   {

      if (g[v1][v2] = = TRUE && visit [v2] = = FALSE)

      {

         Q[++rear] = v2;

         visit[v2] = TRUE;

        }

   }

}

}

Explanation of logic of BFS

• In BFS the queue is maintained for storing the adjacent nodes and an array 'visited' is maintained for keeping the track of visited nodes. i.e. once a particular node is visited it should not be revisited again. Let us see how our program works:

Step 1 : Start with vertex 1

Step 2 :

Step 3 :

Find adjacent vertices of vertex 1 and mark them as visited, insert those in Queue

Step 4 : Find adjacent to '2' and insert those nodes in Queue as well as mark them as visited.

Step 5 : Increment front and delete the node print it.

Step 6 : Find adjacent to '3' i.e. 4 check whether it is marked as visited. If it is marked as visited do not insert in the queue.

Increment front, delete the node from queue and print it.

So output will be ‒ BFS for above graph as

1      2      3       4

 

3. Depth First Search Traversal of a Graph (DFS)

• Basic concept : Depth First Search (DFS) is a graph traversal technique that explores as deep as possible along each branch before backtracking.

• It goes down one path fully, then returns to explore other paths.

• For DFS traversal we generally use stack data structure.

• When there is no adjacent vertex present we traverse back and search for unvisited vertex. We will maintain a visited array to mark all the visited vertices. In case of DFS the depth of a graph should be known. Let see one example of a graph to traverse it by DFS.

Algorithm

1. Select an unvisited node v, visit it and treat it as current node.

2. Find an unvisited neighbour of the current node, visit it and make it as new current node.

3. If current node has no unvisited neighbours back track to its parent and make it a new current node.

4. Repeat the steps 2 and 3 until no more nodes can be visited.

5. Repeat from step 1 for the remaining nodes.

Pseudo code

void Gdfs::Dfs (int v1)

{

   int v2;

   cout<<endl<<v1;

   v[v1] = TRUE;

   for ( v2 = 0; v2 < n; v2++)

         if (g[v1][v2] = = TRUE && v[v2] = = FALSE)

             Dfs(v2);

}

Explanation of logic for depth first traversal

• In DFS the basic data structure for storing the adjacent nodes is stack. In our program we have used a recursive call to DFS function. When a recursive call is invoked actually push operation gets performed. When we exit from the loop pop operation will be performed. Let us see how our program works.

Step 1 : Start with vertex 1, print it so '1' gets printed. Mark 1 as visited.

Step 2 :

Find adjacent vertex to 1, say i.e. 2 if it is not visited, call DFS(2) i.e. 2 will get inserted in the stack, mark is as visited.

Step 3 :

Find adjacent to '2' i.e. vertex 4 if it is not visited call DFS(4) i.e., 4 will get pushed on to the stack mark it as visited.

Step 4 :

Find adjacent to '4' i.e. vertex 3 if it is not visited call DFS(3) i.e. 3 will be pushed onto the stack mark it visited.

Since all the nodes are covered stop the procedure.

So output of DFS is

1       2         4          3

 

Review Questions

1. Explain BFS and DFS in detail. Write the algorithm.

2. Explain breadth first search algorithm for traversal of any graph with suitable examples. Define time complexity of the algorithm.

3. What is graph? Explain the depth first search tree.

4. Explain DFS and BFS with suitable example.

5. Illustrate the depth first search algorithm with a graph and explain.

6. Describe in detail about breadth‒first search and depth‒first search in a graph.

7. Discuss types of graph traversal and explain each with suitable examples.