How do BFS and DFS work, and where are graphs used in embedded software?
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).