Fringe & spanning tree in all graph algorithm exercises: design

[atilante]

Generic idea: how bring the concepts of "fringe" and "spanning" tree into all graph algorithm exercises?

[atilante]

BFS

First whiteboard sketch of Breadth-first search with fringe.

 1 BFS-VISIT(G, s)
 2     Initialize empty queue Q
 3     for each u ∈ V[G] do
 4         visited[u] ← false
 5         finished[u] ← false
 6     visited[s] ← true
 7     ENQUEUE(Q, s)
 8     while Q not empty do
 9         u ← DEQUEUE(Q)
10         for each v ∈ Adj[u] do
11             if visited[v] = false then
12                 visited[v] ← true
13                 ENQUEUE(Q, v)
14         finished[u] = true

        State of vertex

Line      visited    finished    queue     color
-------------------------------------------
6, 12     F->T
7, 13                            enqueue   unvisited -> fringe
9                                dequeue   fringe -> spanning tree
14                    F->T

Atomic operations in visualization:

• Op1. Visited: false->true. Enqueue. Color unvisited->fringe.
• Op2. Finished: false->true. Dequeue. Color fringe->spanning tree.

Possible points of confusion

• Edges are also colored, even though the status of edges is not relevant for BFS.
• Double terminology: (visited & finished) versus (unvisited, fringe, spanning tree)

DFS

[atilante]

Archie needed: a comment on Artturi's sketches.

[atilante]

Konsensus: visited BFS:ssä: tummempi vihreä solmulle.