Depth-First Search
When visualizing networks, different graph traversal algorithms are needed. Implementing the
depth-first search algorithm is intended to review techniques that any computer science student
already knows.
Description
- finds connected components
- computes a spanning tree
-
does not find the shortest path in general for an unweighted graph
-
by keeping track of predecessors, the path to the source node can be reconstructed by backtracking
-
Idea: processes the current node and continues with its successors as far as possible
Characteristics
- the iterative implementation uses a stack (LIFO)
- delays checking if the vertex has already been visited until the vertex is popped from the stack
- time complexity: \(\mathcal{O}(|V|+|E|)\)
Note:
Select and click a node to start traversal. Click the background to reset. Depth is measured in the
number of edges (edge weight is 1) and visualized using colors. The computed spanning tree is
visualized. Nodes of the same color are at the same distance from the selected source node.
The JavaScript Code