This is the 11th day of my participation in the August More text Challenge. For details, see: August More Text Challenge

In the previous article, we simply implemented the creation of the graph, so after the creation, let’s look at the traversal of the graph.

Graph traversal

  • What can a graph traverse do:
    • Can be used to find a particular vertex or a path before two vertices;
    • Check whether the graph is connected;
    • Check whether the graph contains rings, etc.

There are two computations to traverse a graph:

  • Breadth First Search (BFS): saves verticesThe queue, the first vertex queued is explored first.
  • Depth first Search (DFS): saves verticesThe stack, vertices are explored along the path, and new adjacent vertices are accessed.

The idea of the graph traversal algorithm: you must track every node you visit for the first time, and track which nodes have not been fully explored. You must specify the first vertex to be accessed.

  • Explore a vertex completelyIt asks us to look at every edge of that vertex.
  • The unvisited vertices connected by each edge are marked as found and added to the list of vertices to be accessed.
  • To ensure the efficiency of the algorithm, it is essential that each vertex is accessed at most twice

Prepare before traversal

  • It is easy to think of a vertex as being accessed in one of three ways: unaccessed, accessed but unexplored, and accessed and explored. Therefore, we use three colors to represent each of these states:
    • White: indicates that the vertex has not been accessed.
    • Gray: indicates that the vertex has been visited but not explored.
    • Black: indicates that the vertex was visited and fully explored.

This is why each vertex must be accessed at most twice.

  • Create a COLORS object to mark vertices
const colors = {
    white: 0.gray: 1.black: 2
}
Copy the code
  • Initialize the color of each vertex (initialization must mean that none of the vertices are accessed, so they are all initialized to white)
// Initialize all vertices of the graph to white
const initializeColor = vertices= > { 
    const color = {}; 
    for (let i = 0; i < vertices.length; i++) { 
        color[vertices[i]] = colors.white; 
    } 
    return color; 
};
Copy the code

So far, our preparations have been completed! Next, let’s implement the breadth first search algorithm and the depth first search algorithm respectively.