QUESTION 17

What exploration rule does DFS follow?

2 marks

Answer

It explores one unvisited branch as far as possible before returning to another pending branch. Recursion or an explicit stack can manage the pending work.

Explain depth-first search with an algorithm and example.

5 marks

Answer in brief

DFS records visited vertices and explores neighbours deeply before backtracking.

Recursive algorithm

Mark the starting vertex visited and process it.
Enumerate its neighbours in a stated order.
For each unvisited neighbour, recursively run DFS.
For a whole disconnected graph, start again at each still-unvisited vertex.

Worked example

For undirected edges 0–1, 0–2, 1–3 and 2–4, start at 0 and examine neighbour indices in ascending order. The DFS order is 0, 1, 3, 2, 4. From 1 it explores 3 before returning to 0 and considering 2.

Visited handling

Mark a vertex before exploring its outgoing neighbours. This prevents cycles from repeatedly recursing into an already discovered vertex. The same graph can have different valid DFS orders when start or neighbour order changes.

Applications

DFS supports reachability, component exploration and more specialised graph analyses. Detecting cycles or computing a topological order requires additional logic; a simple visited-only traversal should not be claimed to perform those tasks automatically.

Complexity

With adjacency lists, a full traversal processes V vertices and their stored edges, giving O(V + E) time. The supplied program uses a matrix and scans a whole row per visited vertex, giving O(V²). Visited storage and worst-case recursion depth are O(V). The fixed example graph is connected, so one starting call reaches every vertex.

Complete C example

main.c

Download main.c

/* CodeBhavya | Data Structures AR25 | Learning example */
#include <stdio.h>
#define V 5
static const int graph[V][V] = {
    {0,1,1,0,0}, {1,0,0,1,0}, {1,0,0,0,1}, {0,1,0,0,0}, {0,0,1,0,0}
};
void dfs(int vertex, int visited[V])
{
    visited[vertex] = 1; printf("%d ", vertex);
    for (int next = 0; next < V; ++next) {
        if (graph[vertex][next] && !visited[next]) { dfs(next, visited); }
    }
}
void bfs(int start)
{
    int visited[V] = {0}, queue[V], front = 0, rear = 0;
    visited[start] = 1; queue[rear++] = start;
    while (front < rear) {
        int vertex = queue[front++]; printf("%d ", vertex);
        for (int next = 0; next < V; ++next) {
            if (graph[vertex][next] && !visited[next]) { visited[next] = 1; queue[rear++] = next; }
        }
    }
}

int main(void)
{
    int visited[V] = {0};
    printf("DFS: "); dfs(0, visited); putchar('\n');
    printf("BFS: "); bfs(0); putchar('\n');
    return 0;
}

Sample input and output

The example uses values in the code.

Output

DFS: 0 1 3 2 4 
BFS: 0 1 2 3 4