Breath-First Search
When visualizing networks, different graph traversal algorithms are needed. Implementing the breadth-first
search algorithm is intended to review techniques that any computer science student already knows.
Description
- finds connected components
- computes a spanning tree
-
can be used to compute the shortest path between a source node and all other nodes in unweighted graphs
(path length measured by the number of edges or hops)
-
By keeping track of predecessors, the path to the source node can be reconstructed by backtracking
Characteristics
- the iterative implementation uses a queue (FIFO)
- it checks if a vertex has already been visited before enqueueing the vertex
- Idea: processes the current node and then all its neighbors first
- 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