(using if, if-else, nested if, switch-case)

(using for, while, do-while loops)

C Programs

Share with a Friend

HOME

Depth-First Search (DFS) using Adjacency List representation.

Graph Traversal — Depth-First Search (DFS)

Concept Overview

Depth-First Search (DFS) explores a graph deeply — visiting a vertex, then recursively exploring all its unvisited neighbors before backtracking.

It’s essentially a recursive traversal (or can use a stack) that dives deep along one path before exploring others.

How DFS Works

Start from a source vertex.
Mark it as visited.
Visit all unvisited adjacent vertices recursively.
Continue until all vertices are visited.

Example Graph

0 — 1

| |

2 — 3

Adjacency List:

0 → 1 → 2

1 → 0 → 3

2 → 0 → 3

3 → 1 → 2

DFS Traversal (starting from 0)

DFS: 0 → 1 → 3 → 2

C Program: DFS (Depth First Search) using Adjacency List

#include <stdio.h>
#include <stdlib.h>
 
// Structure for adjacency list node
struct Node {
    int vertex;
    struct Node* next;
};
 
// Structure for the graph
struct Graph {
    int vertices;
    struct Node** adjLists;
    int* visited;
};
 
// Create a new node
struct Node* createNode(int v) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}
 
// Create a graph with given vertices
struct Graph* createGraph(int vertices) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->vertices = vertices;
 
    graph->adjLists = (struct Node**)malloc(vertices * sizeof(struct Node*));
    graph->visited = (int*)malloc(vertices * sizeof(int));
 
    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
        graph->visited[i] = 0;
    }
 
    return graph;
}
 
// Add edge (undirected)
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;
}
 
// Recursive DFS function
void DFS(struct Graph* graph, int vertex) {
    struct Node* adjList = graph->adjLists[vertex];
    struct Node* temp = adjList;
 
    graph->visited[vertex] = 1;
    printf("%d ", vertex);
 
    while (temp != NULL) {
        int connectedVertex = temp->vertex;
 
        if (graph->visited[connectedVertex] == 0)
            DFS(graph, connectedVertex);
 
        temp = temp->next;
    }
}
 
int main() {
    int vertices, edges;
    printf("Enter number of vertices: ");
    scanf("%d", &vertices);
 
    struct Graph* graph = createGraph(vertices);
 
    printf("Enter number of edges: ");
    scanf("%d", &edges);
 
    printf("Enter edges (u v):\n");
    for (int i = 0; i < edges; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        addEdge(graph, u, v);
    }
 
    int start;
    printf("Enter starting vertex for DFS: ");
    scanf("%d", &start);
 
    printf("DFS Traversal starting from vertex %d: ", start);
    DFS(graph, start);
 
    printf("\n");
    return 0;
}

Output

 
INPUT :
Enter number of vertices: 4
Enter number of edges: 4
Enter edges (u v):
0 1
0 2
1 3
2 3
Enter starting vertex for DFS: 0

OUTPUT :
DFS Traversal starting from vertex 0: 0 1 3 2

Complexity Analysis

Operation	Time Complexity	Space Complexity
DFS Traversal	O(V + E)	O(V) (recursion stack)

Every vertex and edge is visited once.
Recursive stack depth = number of vertices (in worst case).

Key Takeaways

DFS explores a path deeply before backtracking.
Uses recursion (or stack) instead of a queue.
Ideal for:

Topological sorting
Cycle detection
Connected components
Path finding in mazes and puzzles
Works for directed and undirected graphs.
Be careful with infinite recursion — always mark visited nodes!

BFS vs DFS (Quick Comparison)

Feature	BFS	DFS
Data Structure	Queue	Stack / Recursion
Traversal Order	Level by level	Depth-wise
Memory Usage	O(V)	O(V) (recursive stack)
Finds Shortest Path (unweighted graph)	Yes	No
Suitable For	Shortest path, layer exploration	Path search, backtracking, cycle detection

Basics of C Programming (Introductory Programs)

Control Statements & Loops in C

Functions

Arrays

Strings

Pointers

Structures and Unions

Dynamic Memory Allocation

File Handling

Data Structures in C

Advanced C Programs

User-Defined Number Programs in C

User-Defined String Programs in C