Depth First Search (DFS) Technique in C
Depth First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking.
It uses a stack data structure, either explicitly or implicitly through recursion, to keep track of the vertices to be visited next.
DFS can be used to solve various problems such as finding connected components, topological sorting, and detecting cycles in graphs.
C Implementation of DFS
// Import necessary packages #include <stdio.h> #include <stdlib.h> /** * Structure to represent a node in the adjacency list */ struct Node { int vertex; struct Node* next; }; /** * Structure to represent the adjacency list */ struct List { struct Node* head; }; /** * Structure to represent the graph */ struct Graph { int numVertices; struct List* adjLists; int* visited; }; /** * Function to create a node * * @param v The vertex value * @return Node pointer */ struct Node* createNode(int v) { struct Node* newNode = malloc(sizeof(struct Node)); newNode->vertex = v; newNode->next = NULL; return newNode; } /** * Function to create a graph * * @param vertices Number of vertices * @return Graph pointer */ struct Graph* createGraph(int vertices) { struct Graph* graph = malloc(sizeof(struct Graph)); graph->numVertices = vertices; graph->adjLists = malloc(vertices * sizeof(struct List)); graph->visited = malloc(vertices * sizeof(int)); int i; for (i = 0; i < vertices; i++) { graph->adjLists[i].head = NULL; graph->visited[i] = 0; } return graph; } /** * Function to add an edge to the graph * * @param graph Graph pointer * @param src Source vertex * @param dest Destination vertex */ void addEdge(struct Graph* graph, int src, int dest) { // Add edge from src to dest struct Node* newNode = createNode(dest); newNode->next = graph->adjLists[src].head; graph->adjLists[src].head = newNode; // Add edge from dest to src (for undirected graph) newNode = createNode(src); newNode->next = graph->adjLists[dest].head; graph->adjLists[dest].head = newNode; } /** * Function to perform DFS traversal * * @param graph Graph pointer * @param vertex Starting vertex */ void DFS(struct Graph* graph, int vertex) { // Mark the current node as visited and print it graph->visited[vertex] = 1; printf("%d ", vertex); // Recur for all the vertices adjacent to this vertex struct Node* adjList = graph->adjLists[vertex].head; while (adjList != NULL) { int connectedVertex = adjList->vertex; if (graph->visited[connectedVertex] == 0) { DFS(graph, connectedVertex); } adjList = adjList->next; } } /** * Main method to test the DFS algorithm */ int main() { struct Graph* graph = createGraph(4); addEdge(graph, 0, 1); addEdge(graph, 0, 2); addEdge(graph, 1, 2); addEdge(graph, 2, 3); printf("Following is Depth First Traversal starting from vertex 2:\n"); DFS(graph, 2); return 0; }
Explanation
The above program demonstrates the Depth First Search (DFS) algorithm in C:
- Graph Structure: The
Graphstructure represents a graph using an adjacency list representation. It has methods to add edges and perform DFS. - DFS Method: This method marks the current node as visited, prints it, and then recursively visits all adjacent vertices that have not been visited yet.
- Main Method: This is the entry point of the program where a graph is created, edges are added, and the DFS traversal is initiated starting from vertex 2.
In the main method, we create a graph with 4 vertices and add edges between them. The DFS traversal starts from vertex 2 and prints the nodes in the order they are visited.
