</>EmbeddedInterview

How do BFS and DFS work, and where are graphs used in embedded software?

MediumData Structures & Algorithms

Short answer: Breadth-first search (BFS) visits nodes level by level using a queue, and finds the shortest path in an unweighted graph. Depth-first search (DFS) goes as deep as possible along each branch before backtracking, using a stack or recursion, and is used for cycle detection, topological ordering and connectivity. Both are O(V + E). Embedded uses include dependency ordering (initialising drivers after their dependencies), deadlock detection (cycles in a lock or wait-for graph), routing in mesh networks, and state machines.

#include <stdio.h>
#include <stdbool.h>

#define V 6
/* adjacency matrix: small, static; use adjacency lists for sparse/large graphs */
static const bool adj[V][V] = {
    /* 0 */ {0,1,1,0,0,0},
    /* 1 */ {0,0,0,1,0,0},
    /* 2 */ {0,0,0,1,1,0},
    /* 3 */ {0,0,0,0,0,1},
    /* 4 */ {0,0,0,0,0,1},
    /* 5 */ {0,0,0,0,0,0},
};

void bfs(int start, int dist[V])
{
    int q[V], head = 0, tail = 0;
    for (int i = 0; i < V; i++) dist[i] = -1;
    dist[start] = 0; q[tail++] = start;
    while (head < tail) {
        int u = q[head++];
        for (int v = 0; v < V; v++)
            if (adj[u][v] && dist[v] < 0) { dist[v] = dist[u] + 1; q[tail++] = v; }
    }
}

int main(void)
{
    int d[V];
    bfs(0, d);
    for (int i = 0; i < V; i++) printf("%d ", d[i]);   /* 0 1 1 2 2 3 */
    printf("\n");
    return 0;
}

DFS notes: use three colours (unvisited, in progress, done) to detect cycles in a directed graph: reaching an "in progress" node means a cycle. Post-order DFS gives a reverse topological order. Kahn's algorithm (repeatedly remove nodes with no incoming edges) gives a topological order without recursion — see the systems coding topic.

Weighted shortest paths: Dijkstra's algorithm with a priority queue (non-negative weights), Bellman-Ford with negative weights; used in routing protocols (OSPF, RPL in 6LoWPAN meshes).

Memory: an adjacency matrix needs V² bits/bytes (fine for small V, e.g. a bitmap of 32×32); adjacency lists need O(V + E).