Graph representation and Graph traversal in Data structure

In the previous article, we learned about the Graph in Data Structures, In this article, we will learn about Graph representation and Graph traversal in Data Structures.

33

The graph can either be represented in the form of an adjacency matrix representation or an adjacency list representation in Data Structure. 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 an 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 using the same entry in both locations (i,j) and (j, i) or using an upper triangular matrix.

Graph Representations in data structure
Graph Representations in data structure

Directed graph and its adjacency matrix

Adjacency List Representation

In the 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, and then the 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 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 the destination node and a pointer which points to the next adjacent node of the header node.

struct edge{

          char destination;

          struct edge* link;      

}

Given below, is a linked list representation of a Graph –

linked list representation of a graph
linked list representation of a graph

Traversal operations on Graphs

Now, we will learn about traversal operations on Graphs –

A graph can be traversed in two different manners which are –

  • BFS
  • DFS

Breadth First Search (BFS) 

In the BFS type of traversal, first all the neighbouring nodes of a given node are visited. Then, after completing all of the adjacent vertices, it moves further to check other vertices and checks its adjacent vertices again.

Algorithm for BFS traversal

Given below is the algorithm for BFS traversal which needs to be followed  –

bfs(vertices, start)

Input: The list of vertices, and the start vertex.

Output: Traverse all of the nodes, if the graph is connected.

Begin

define an empty queue que

at first mark all nodes status as unvisited

add the start vertex into the que

while que is not empty, do

delete item from que and set to u

display the vertex u

for all vertices 1 adjacent with u, do

if vertices[i] is unvisited, then

mark vertices[i] as temporarily visited

add v into the queue

mark

done

mark u as completely visited

done

End

Code for the BFS traversal of a given Graph

Given below, is the code for the BFS traversal of a given Graph –

#include <stdio.h>

#include <stdlib.h>

#define SIZE 40 

struct queue {

  int items[SIZE];

  int front;

  int rear;

};

 
struct queue* createQueue();

void enqueue(struct queue* q, int);

int dequeue(struct queue* q);

void display(struct queue* q);

int isEmpty(struct queue* q);

void printQueue(struct queue* q);


struct node {

  int vertex;

  struct node* next;

};
 

struct node* createNode(int); 

struct Graph {

  int numVertices;

  struct node** adjLists;

  int* visited;

};

 

void bfs(struct Graph* graph, int startVertex) {

  struct queue* q = createQueue();


  graph->visited[startVertex] = 1;

  enqueue(q, startVertex);


  while (!isEmpty(q)) {

    printQueue(q);

    int currentVertex = dequeue(q);

    printf("Visited %d\n", currentVertex);


    struct node* temp = graph->adjLists[currentVertex]; 

    while (temp) {

      int adjVertex = temp->vertex;

      if (graph->visited[adjVertex] == 0) {

        graph->visited[adjVertex] = 1;

        enqueue(q, adjVertex);

      }

      temp = temp->next;

    }

  }

}
 

struct node* createNode(int v) {

  struct node* newNode = malloc(sizeof(struct node));

  newNode->vertex = v;

  newNode->next = NULL;

  return newNode;

}
 

struct Graph* createGraph(int vertices) {

  struct Graph* graph = malloc(sizeof(struct Graph));

  graph->numVertices = vertices;

  graph->adjLists = malloc(vertices * sizeof(struct node*));

  graph->visited = malloc(vertices * sizeof(int));

  int i;

  for (i = 0; i < vertices; i++) {

    graph->adjLists[i] = NULL;

    graph->visited[i] = 0;

  } 

  return graph;

}



void addEdge(struct Graph* graph, int src, int dest) {

  struct node* newNode = createNode(dest);

  newNode->next = graph->adjLists[src];

  graph->adjLists[src] = newNode; 

  newNode = createNode(src);

  newNode->next = graph->adjLists[dest];

  graph->adjLists[dest] = newNode;

}

 

struct queue* createQueue() {

  struct queue* q = malloc(sizeof(struct queue));

  q->front = -1;

  q->rear = -1;

  return q;

}

 

int isEmpty(struct queue* q) {

  if (q->rear == -1)

    return 1;

  else

    return 0;

}

 

void enqueue(struct queue* q, int value) {

  if (q->rear == SIZE - 1)

    printf("\nQueue is Full!!");

  else {

    if (q->front == -1)

      q->front = 0;

    q->rear++;

    q->items[q->rear] = value;

  }

}

int dequeue(struct queue* q) {

  int item;

  if (isEmpty(q)) {

    printf("Queue is empty");

    item = -1;

  } else {

    item = q->items[q->front];

    q->front++;

    if (q->front > q->rear) {

      printf("Resetting queue ");

      q->front = q->rear = -1;

    }

  }

  return item;

}

 

void printQueue(struct queue* q) {

  int i = q->front;


  if (isEmpty(q)) {

    printf("Queue is empty");

  } else {

    printf("\nQueue contains \n");

    for (i = q->front; i < q->rear + 1; i++) {

      printf("%d ", q->items[i]);

    }

  }

}

 

int main() {

  struct Graph* graph = createGraph(6);

  addEdge(graph, 0, 1);

  addEdge(graph, 0, 2);

  addEdge(graph, 1, 2);

  addEdge(graph, 1, 4);

  addEdge(graph, 1, 3);

  addEdge(graph, 2, 4);

  addEdge(graph, 3, 4);

  bfs(graph, 0);

  return 0;

}

DFS Traversal

DFS is a traversal technique in a Graph where all the nodes are visited in a depth-wise manner. The DFS algorithm is a recursive algorithm that uses the idea of backtracking. It involves exhaustive searches of all the nodes by going ahead, if possible, else by backtracking.

Here, the word backtrack means that when you are moving forward and there are no more nodes along the current path, you move backward on the same path to find nodes to traverse. All the nodes will be visited on the current path till all the unvisited nodes have been traversed after which the next path will be selected.

Algorithm for implementing DFS in a Graph

Given below is the algorithm for implementing DFS in a Graph –

  • Start by putting any one of the graph’s vertices on top of a stack.
  • Take the top item of the stack and add it to the visited list.
  • Create a list of that vertex’s adjacent nodes. Add the ones which aren’t in the visited list to the top of the stack.
  • Keep repeating steps 2 and 3 until the stack is empty.

Code for implementing DFS traversal in a Graph

Now, we will understand the code for implementing DFS traversal in a Graph –

#include <stdio.h>

#include <stdlib.h>

struct node {

  int vertex;

  struct node* next;

};

struct node* createNode(int v); 

struct Graph {

  int numVertices;

  int* visited;

  struct node** adjLists;

};
 

void DFS(struct Graph* graph, int vertex) {

  struct node* adjList = graph->adjLists[vertex];

  struct node* temp = adjList;
 

  graph->visited[vertex] = 1;

  printf("Visited %d \n", vertex);

 
  while (temp != NULL) {

    int connectedVertex = temp->vertex;
 

    if (graph->visited[connectedVertex] == 0) {

      DFS(graph, connectedVertex);

    }

    temp = temp->next;

  }

} 

struct node* createNode(int v) {

  struct node* newNode = malloc(sizeof(struct node));

  newNode->vertex = v;

  newNode->next = NULL;

  return newNode;

}
 

struct Graph* createGraph(int vertices) {

  struct Graph* graph = malloc(sizeof(struct Graph));

  graph->numVertices = vertices;

  graph->adjLists = malloc(vertices * sizeof(struct node*));

  graph->visited = malloc(vertices * sizeof(int));

 

  int i;

  for (i = 0; i < vertices; i++) {

    graph->adjLists[i] = NULL;

    graph->visited[i] = 0;

  }

  return graph;

}


void addEdge(struct Graph* graph, int src, int dest) {

  struct node* newNode = createNode(dest);

  newNode->next = graph->adjLists[src];

  graph->adjLists[src] = newNode;

 

  newNode = createNode(src);

  newNode->next = graph->adjLists[dest];

  graph->adjLists[dest] = newNode;

}

 

void printGraph(struct Graph* graph) {

  int v;

  for (v = 0; v < graph->numVertices; v++) {

    struct node* temp = graph->adjLists[v];

    printf("\n Adjacency list of vertex %d\n ", v);

    while (temp) {

      printf("%d -> ", temp->vertex);

      temp = temp->next;

    }

    printf("\n");

  }

}

 

int main() {

  struct Graph* graph = createGraph(4);

  addEdge(graph, 0, 1);

  addEdge(graph, 0, 2);

  addEdge(graph, 1, 2);

  addEdge(graph, 2, 3); 

  printGraph(graph);

  DFS(graph, 2);


  return 0;

}

So, in this article, we learned about Graph representations and various traversal techniques that can be applied to Graphs.

Attempt free Data Structures Practice Test

LEAVE A REPLY

Please enter your comment!
Please enter your name here

This site uses Akismet to reduce spam. Learn how your comment data is processed.