Given a graph, C program to implement depth-first search (DFS) traversal using adjacency matrix

Introduction

Graph theory allows us to study and visualize relationships between objects or entities. In current computer science technology, graph traversal plays a crucial role in exploring and analyzing different types of data structures. One of the key operations performed on a graph is traversal - following a specific path to visit all vertices or nodes. DFS traversal based on a depth-first approach allows us to explore the depth of the graph before backtracking and exploring other branches. In this article, we will implement DFS traversal using the adjacency matrix representation in C.

Use adjacency matrix for DFS traversal

A graph consists of two main components, namely vertices or nodes that represent entities or elements, and edges that connect these vertices, describing the relationships between them.

The only way to represent the relationship between vertices in a weighted or unweighted graph is through an adjacency matrix. It usually takes the form of a square matrix, where rows represent source vertices and columns represent target vertices, and each cell contains information about the existence or weight of an edge between corresponding pairs.

Example

The input is given through a specific set of elements using the four vertices of the graph. The input is:

1 0 0 1
0 1 1 0
0 1 1 0
1 0 0 1

Suppose the starting vertex of the graph is 2. The graph will be traversed starting from vertex "2". The adjacent vertices of vertex "2" are obviously 1 and 3. Since the starting vertex is 2, it cannot be accessed again during the traversal. Vertex 3 is visited after vertex 2, then we need to check the adjacent vertices 1 and 2 of vertex 3. Vertex 1 and vertex 2 have been visited and the traversal stops.

Method 1: C program involving DFS traversal using adjacency matrix as input in given graph

The input is defined with some numbers and using a for loop it will iterate the adjacency matrix and return the DFS traversal.

algorithm

Step 1: The program first defines a constant "MAX" to represent the maximum number of nodes in the given graph, and initializes an array named "visited" to track whether a specific node exists during the traversal has been visited.

Step 2: The "dfs()" function takes a square adjacency matrix as a parameter, "adjMatrix" represents our graph, the total number of vertices is "vCount", and the starting vertex is `start`. This function performs a recursive depth-first search traversal of the given graph.

Step 3: In the "dfs()" function, we mark each currently processed vertex as "visited" using the index in the boolean-based "visited[]" array , and print its value accordingly.

Step 4: The loop inside "dfs()" recursively iterates all unvisited neighbors of the current node until it is impossible to obtain a vertex connected to it.

Step 5: In main(), we use a nested loop to read the user's input, such as the number of vertices of "vCount" and their corresponding connections into the adjacency matrix.

Step 6: We then prompt the user for the desired starting vertex and then initialize each element of the "visited[]" array to zero (since no nodes have been visited yet).

Step 7: Finally, the program calls the "dfs()" function with the appropriate parameters to start the depth-first search traversal and prints out the DFS traversal path.

Example

//Including the required header files
#include<stdio.h>
#define MAX 100

int visited[MAX];
//dfs function is defined with three arguments
void dfs(int adjMatrix[][MAX], int vCount, int start) {
   visited[start] = 1;
   printf("%d ", start);

   for(int i=0; i<vCount; i++) {
      if(adjMatrix[start][i] && !visited[i]) {
         dfs(adjMatrix,vCount,i);
      }
   }
}
//main function is used to implement the above functions
int main() {
   int adjMatrix[MAX][MAX];
   int vCount;

   // Assigning the variable with value of 4
   vCount = 4;

   // Assigning the adjacency matrix directly same the example given above
   adjMatrix[0][0] = 1;
   adjMatrix[0][1] = 0;
   adjMatrix[0][2] = 0;
   adjMatrix[0][3] = 1;
   adjMatrix[1][0] = 0;
   adjMatrix[1][1] = 1;
   adjMatrix[1][2] = 1;
   adjMatrix[1][3] = 0;
   adjMatrix[2][0] = 0;
   adjMatrix[2][1] = 1;
   adjMatrix[2][2] = 1;
   adjMatrix[2][3] = 0;
   adjMatrix[3][0] = 1;
   adjMatrix[3][1] = 0;
   adjMatrix[3][2] = 0;
   adjMatrix[3][3] = 1;
//Declaring the start variable as integer data type and later assigned with a value of 2
   int start;
   
   // Assigning the starting vertex directly
   start = 2;
   
   for(int i = 0; i < MAX; ++i) {
      visited[i] = 0;
   }

   printf("\nDFS Traversal: ");
   dfs(adjMatrix, vCount, start);
   

   return 0;
}

Output

DFS Traversal: 2 1

in conclusion

By using the adjacency matrix as the representation of the graph, we can perform DFS efficiently on large or complex data sets. In this paper, we explain this in detail and propose a C program that implements a depth-first search traversal using an adjacency matrix-based representation. Depth-first search is a powerful algorithm for exploring and analyzing graph structures.

The above is the detailed content of Given a graph, C program to implement depth-first search (DFS) traversal using adjacency matrix. For more information, please follow other related articles on the PHP Chinese website!