Graphs Pseudocode

Classic traversal and shortest path algorithms.

Breadth-First Search (BFS)

Pseudocode

1procedure BFS(G, start)
2  create empty queue Q
3  mark start as visited
4  enqueue(Q, start)
5  while Q not empty do
6    v ← dequeue(Q)
7    visit v
8    for each neighbor u of v do
9      if u not visited then
10        mark u as visited
11        enqueue(Q, u)
12      end if
13    end for
14  end while
15end procedure

Depth-First Search (DFS)

Pseudocode

1procedure DFS(G, v)
2  mark v as visited
3  visit v
4  for each neighbor u of v do
5    if u not visited then
6      DFS(G, u)
7    end if
8  end for
9end procedure

Dijkstra's Algorithm

Pseudocode

1procedure DIJKSTRA(G, source)
2  for each vertex v in G do
3    dist[v] ← ∞
4    prev[v] ← NULL
5  end for
6  dist[source] ← 0
7  S ← empty set
8  Q ← all vertices of G (min-priority by dist)
9  while Q not empty do
10    u ← extractMin(Q)
11    add u to S
12    for each (u, v) with weight w do
13      if dist[u] + w < dist[v] then
14        dist[v] ← dist[u] + w
15        prev[v] ← u
16        decreaseKey(Q, v, dist[v])
17      end if
18    end for
19  end while
20  return dist, prev
21end procedure

See theory and interactive practice from the Graphs page.