So far, we have only demonstrated how the DFS algorithm works. We can use it for other functionalities than just outputting the order of vertices visited.
Given a graph G, the DFS algorithm traverses all the vertices of G and constructs a forest (a collection of rooted trees) together with a set of source vertices (roots) and outputs two arrays: the discovery time and finish explorer time. We can modify the depthFirstSearch function to return some information for us, such as the following:
- The discovery time d[u] of u
- The finish time f[u] when u is marked black
- The predecessors p[u] of u
Let's take a look at the implementation of the BFS method:
export const DFS = graph => { const vertices = graph.getVertices(); ...
