QUESTION 19

When should a vertex be marked visited in this BFS implementation?

2 marks

Answer

When it is enqueued. This prevents several neighbours from inserting the same vertex repeatedly.

Explain breadth-first search and its queue operations.

5 marks

Answer in brief

BFS explores vertices in increasing edge distance from a starting vertex in an unweighted graph.

Algorithm

Mark the start and enqueue it.
While the queue is non-empty, dequeue a vertex and process it.
Enumerate its neighbours. Mark and enqueue each unvisited neighbour.
For a complete disconnected traversal, repeat from other unvisited starts.

Worked example

For edges 0–1, 0–2, 1–3 and 2–4, begin at 0. Enqueue 1 and 2 after processing 0. Process 1 and discover 3, then process 2 and discover 4. With ascending neighbour order, the output is 0, 1, 2, 3, 4.

Why FIFO matters

The queue processes all earlier discovered vertices before later ones. Consequently all distance-one vertices are handled before distance-two vertices. A stack would instead promote a latest-discovered branch and give DFS-like behaviour.

Shortest paths

BFS can record a predecessor and distance at discovery to obtain shortest paths measured in number of edges in an unweighted graph. This is not a universal least-cost algorithm for arbitrary weighted graphs. The demonstration prints traversal order only and does not claim to return a full path.

Complexity

Adjacency-list BFS is O(V + E). The supplied matrix demonstration is O(V²) because each processed vertex scans V possible neighbours. Its queue and visited array need O(V) space. Marking at enqueue ensures each vertex enters the queue at most once per traversal.

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