C Programming Data Structures Dfs Bfs Traversals Complete Guide

Top 10 Questions and Answers on C Programming Data Structures: DFS and BFS Traversals

1. What are Depth First Search (DFS) and Breadth First Search (BFS) in the context of graph traversal?

• DFS starts at a root node (or an arbitrary node in case of a graph) and explores as far as possible along each branch before backtracking.

• BFS also begins at a root node but explores all neighbors at the present depth prior to moving on to the nodes at the next depth level, effectively traversing the graph level by level.

2. How can DFS be implemented in C?

Answer: DFS can be implemented using either recursion or explicit stacks. Here is a recursive approach:

#include <stdio.h>
#include <stdlib.h>

// Adjacency list node
struct AdjListNode {
    int dest;
    struct AdjListNode *next;
};

// Adjacency list
struct AdjList {
    struct AdjListNode *head;
};

// Graph
struct Graph {
    int V;
    struct AdjList *array;
};

struct AdjListNode* newAdjListNode(int dest) {
    struct AdjListNode *newNode = (struct AdjListNode *)malloc(sizeof(struct AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

struct Graph* createGraph(int V) {
    struct Graph *graph = (struct Graph *)malloc(sizeof(struct Graph));
    graph->V = V;
    graph->array = (struct AdjList *)malloc(V * sizeof(struct AdjList));

    for (int i = 0; i < V; i++)
        graph->array[i].head = NULL;

    return graph;
}

void addEdge(struct Graph *graph, int src, int dest) {
    struct AdjListNode *newNode = newAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

    newNode = newAdjListNode(src);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}

void DFSUtil(struct Graph *graph, int v, int visited[]) {
    printf("%d ", v);
    visited[v] = 1;

    struct AdjListNode *adjNode = graph->array[v].head;
    while (adjNode) {
        if (!visited[adjNode->dest])
            DFSUtil(graph, adjNode->dest, visited);
        adjNode = adjNode->next;
    }
}

void DFS(struct Graph *graph, int v) {
    int *visited = (int *)malloc(graph->V * sizeof(int));
    for (int i = 0; i < graph->V; i++)
        visited[i] = 0;

    DFSUtil(graph, v, visited);
}

int main() {
    int V = 5;
    struct Graph *graph = createGraph(V);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);

    printf("Depth First Traversal starting from vertex 0: \n");
    DFS(graph, 0);

    return 0;
}

3. How does the BFS algorithm work in C?

Answer: BFS can be implemented using a queue data structure:

#include <stdio.h>
#include <stdlib.h>
#define MAX 5

struct Queue {
    int items[MAX];
    int front;
    int rear;
};

struct Queue* createQueue() {
    struct Queue *queue = (struct Queue *)malloc(sizeof(struct Queue));
    queue->front = -1;
    queue->rear = -1;
    return queue;
}

int isEmpty(struct Queue *queue) {
    return queue->rear == -1;
}

void enqueue(struct Queue *queue, int value) {
    if (queue->rear == MAX - 1)
        printf("\nQueue is Full!!\n");
    else {
        if (queue->front == -1)
            queue->front = 0;
        queue->rear++;
        queue->items[queue->rear] = value;
    }
}

int dequeue(struct Queue *queue) {
    int item;
    if (isEmpty(queue)) {
        printf("Queue is empty");
        item = -1;
    } else {
        item = queue->items[queue->front];
        queue->front++;
        if (queue->front > queue->rear) {
            queue->front = queue->rear = -1;
        }
    }
    return item;
}

struct Node {
    int vertex;
    struct Node *next;
};

struct Node* createNode(int v) {
    struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

struct Graph {
    int numVertices;
    int *visited;
    struct Node **adjLists;
};

struct Graph* createGraph(int vertices) {
    struct Graph *graph = (struct Graph *)malloc(sizeof(struct Graph));
    graph->numVertices = 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;
}

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;
}

void bfs(struct Graph *graph, int startVertex) {
    struct Queue *queue = createQueue();

    graph->visited[startVertex] = 1;
    enqueue(queue, startVertex);

    int currentVertex;
    struct Node *temp;

    while (!isEmpty(queue)) {
        currentVertex = dequeue(queue);
        printf("%d ", currentVertex);

        temp = graph->adjLists[currentVertex];

        while (temp != NULL) {
            int adjVertex = temp->vertex;

            if (graph->visited[adjVertex] == 0) {
                graph->visited[adjVertex] = 1;
                enqueue(queue, adjVertex);
            }
            temp = temp->next;
        }
    }
}

int main() {
    struct Graph *graph = createGraph(6);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 4);
    addEdge(graph, 1, 3);
    addEdge(graph, 2, 4);
    addEdge(graph, 3, 4);

    bfs(graph, 0);

    return 0;
}

4. Explain the difference between stack-based DFS and recursive DFS.

Answer: Both approaches are valid for implementing DFS, but they have slight differences:

• Recursive DFS uses the call stack of the program to keep track of the vertices to be explored. It is simpler to implement and understand but can suffer from stack overflow for large graphs due to deep recursion.

• Stack-based DFS explicitly utilizes a stack data structure to manage the vertices. This approach avoids the risk of stack overflow and is more memory-efficient for deep searches but can be more complex to implement.

5. How does the implementation of BFS differ from DFS in terms of data structures?

Answer: BFS uses a queue to remember which nodes are next to explore, whereas DFS uses a stack (implicitly through recursion or explicitly through a stack data structure).

• The queue operates on a FIFO (First In First Out) principle, which is essential for exploring the neighbors level by level.

• The stack operates on a LIFO (Last In First Out) principle, useful for exploring as deep as possible into branches of a graph.

6. When should you use DFS over BFS?

Answer:

• Use DFS when you want to visit a single path deeply, such as in finding paths in a maze (backtracking), determining connectivity, or for topological sorting.

• Use BFS when you need the shortest path in an unweighted graph, checking if a graph is bipartite, detecting cycles, or performing level-wise tasks.

7. Can DFS and BFS be used with both directed and undirected graphs?

Answer: Yes, both DFS and BFS can be used to traverse directed and undirected graphs. The algorithms themselves do not differentiate between them, but care must be taken in the adjacency list to correctly represent edges.

8. What is time and space complexity of DFS and BFS?

Answer: For both DFS and BFS:

• Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges.

• Space Complexity: O(V) because in the worst case, we need to store all vertices in the visited array or auxiliary data structure (stack/queue).

9. Can a graph contain multiple DFS and BFS traversals?

Answer: Yes, a graph can have different DFS and BFS traversals depending on the starting vertex and the order in which neighbors are visited. The result of these traversals will indeed vary based on these factors.

10. Which traversal method, DFS or BFS, is better for detecting cycles in undirected graphs?

Answer: Both DFS and BFS can detect cycles in undirected graphs, but each has its own approach:

• DFS Approach: A cycle is detected if a node is visited again that is already in the recursion stack.

• BFS Approach: A cycle is found if two nodes at the same level point to each other, excluding the parent node.