# Depth First Search Algorithm

Share

A recursive approach called depth-first search or depth-first traversal is used to search every vertex in a graph or tree data structure. A graph’s nodes are visited during traversal.

Consider a graph:

C Program:

``````#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) {
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); // recursive call
}
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);
}
int main() {
struct Graph* graph = createGraph(7);
DFS(graph, 0);
return 0;
}``````

Here we have implemented the DFS algorithm using a linked list. Also, we can do it using the 2D array approach.

OUTPUT

Share Healing