# 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.

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.

## Directed graph and its adjacency matrix

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;

}

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;

}

Given below, is a 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

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

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;

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);

while (temp) {

}

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->visited[i] = 0;

}

return graph;

}

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

struct node* newNode = createNode(dest);

newNode = createNode(src);

}

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);

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;

};

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

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->visited[i] = 0;

}

return graph;

}

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

struct node* newNode = createNode(dest);

newNode = createNode(src);

}

void printGraph(struct Graph* graph) {

int v;

for (v = 0; v < graph->numVertices; 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);

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.

I am Harshit Brijwasi. I am an engineer and a Technical Content writer. I am here to share my knowledge about technical topics and help researchers with them.

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