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

Depth-first search

  • The depth-first search algorithm willFrom the first vertex specifiedSo let’s go through the graph,Along the pathUntil thisThe last vertex of a path is accessed, thenGo back and explore the next path.
  • That is, it accesses vertices in depth and then breadth.
  • Note: Depth-first search does not require a source vertex. (Because it is explored along the path)
  • The depth-first search steps are recursive. This means that the depth first search algorithm is usedThe stackTo store the function call (the stack created by the recursive call).
  • Similar to the previous breadth-first search, we also use colors to mark vertex access exploration:
    • Found vertices are gray;
    • Vertices that have been explored are marked black;

implementation

  • The preparatory work
// Initialize all vertices of the graph to white
const colors = {
    white: 0.gray: 1.black: 2
}
const initializeColor = vertices= > { 
    const color = {}; 
    for (let i = 0; i < vertices.length; i++) { 
        color[vertices[i]] = colors.white; 
    } 
    return color; 
};
Copy the code
  • Began to work
this.dfs = function(callback) {
    // Get the set of all initialized vertices and their colors
    let color = initializeColor()
    // Define the recursive function
    let dfsVisit = function(u, color, callback) {
        // Mark the unvisited vertex u in gray, indicating that it has been accessed
        color[u] = 'gray';
        if (callback) {
            callback(u)
        }
        // The adjList dictionary stores the list of vertices and their adjacencies, so we get the adjacencies list of vertex U
        let neighbors = adjList.get(u);
        // Loop the list of adjacent vertices to vertex U
        for (let i = 0; i < neighbors.length; i++) {
            // Fetch each adjacent vertex
            let w = neighbors[i]
            // If the adjacent vertex is unvisited, that is, white, then call the dfsVisit method and explore again
            if (color[w] === 'white') {
                dfsVisit(w, color, callback)
            }
        }
        // Finally, after the vertex and adjacent vertices have been visited in depth, the vertex falls back to indicate that it has been fully explored and is marked black
        color[u] = 'black';
    }
    // Iterates over all vertices, calling a private recursive function for each unvisited vertex
    for (let i = 0; i < vertices.length; i++) {
        if(color[vertices[i]] === 'white') { dfsVisit(vertices[i], color, callback); }}}Copy the code
  • Attach a process diagram:

Resolution:

  • In the previous article, we created the Vertices array to store all the vertices in the graph. And what we’re doing in creating that array is going to beA B C D E F G H IVertices are pushed into the array in turn, so in a depth-first search, we will see that the first gray vertex in the figure above isA.
  • After greying A, the list of adjacent vertices of A is traversed['B', 'C', 'D']The first time the loop reaches its peakB, and found thatBIt’s white;
  • Then call the dfsVisit method, which willBMarked in gray; And now I have the list of adjacent vertices to B['E', 'F'], traversing the list, and getting the vertex for the first timeEAnd found it was white;
  • The dfsVisit method is then called, which willEMarked in gray; So I have a list of E’s adjacent vertices['I'], iterates through the list and gets to the vertexIAnd found it was white;
  • The dfsVisit method is then called, which willIMarked in gray; And it turns out that the adjacencies list for I is gone, which means that we’ve completely explored this path, and now we’re going toVertex I is marked black.
  • then['E', 'F']I got it the second timeFAnd found it was white;
  • The dfsVisit method is then called, which willFMarked in gray; The adjacency list of F is['B'], and find that B is gray, thenFWith the adjacencies list explored,Mark F black.
  • The rollback starts.
  • And so on.
  • Send a drawing to help you understand.