This is the 13th day of my participation in the August More Text Challenge

Address of related articles:

  • Graphical introduction to data structures
  • Creation of graphs of data structures
  • Graph traversal of data structures
  • Breadth-first search for graphs of data structures

In the last article, we implemented basic breadth-first search, which is how BFS works. Breadth-first search can do a lot of things, so let’s see how to use BFS to find shortest paths.

Use BFS to find shortest paths

Given a graph G and source vertex v, find the shortest path distance between each vertex u and v.

  • We measure the distance by the number of edges between vertices, which means that the smaller the number of edges between two vertices, the shortest path between them. thenFinding the shortest path also translates to minimizing the number of edges between two vertices.
  • As we learned in the last article, breadth-first search is a list of adjacent vertices that are explored when a vertex is visited. That is, for a given vertex V, a breadth-first search will visit all its adjacent vertices (that is, all vertices that are 1 away from it), then go to vertices that are 2 away, and so on.

implementation

  • Based on the BFS approach that implemented breadth-first search in the previous article:
this.bfs = function (v) {
    let color = initializeColor();
    let queue = new Queue();
    
    // Create d object to store the distance d[u] from v to u
    let d = {};
    // Create a pred object to store the previous vertex of vertex V in the search. The retroactive point pred[u] is used to derive the shortest path from v to every other vertex u
    let pred = {};
       
    queue.enqueue(v);
    
    // Similarly, we iterate over the list of vertices in the graph, initializing the distance between each vertex and the other vertices to 0
    for (let i = 0; i < vertices.length; i++) {
        // Record the distance between each vertex and the other vertices
        d[vertices[i]] = 0;
        pred[vertices[i]] = null;
    }
    
    // loop the queue
    while(! .queue.isEmpty()) {If the queue is not empty, proceed with the following operations
        // Remove the first item u in the queue
        let u = queue.dequeue();
        // The adjList dictionary stores the list of vertices and their adjacent vertices, so we get the adjacency list of vertex u
        let neighbors = adjList.get(u);
        // Change the state of visited vertex u to gray
        color[u] = 'gray'
        // Then explore the adjacency list for vertex u
        for (let i = 0; i < neighbors.length; i++) {
            // Fetch each adjacent vertex
            let w = neighbors[i]
            // If the vertex is white, it has not been visited, then change its status color to gray and push it into the queue, changing the distance between the w vertex and u vertex
            if (color[w] === 'white') {
                color[w] = 'gray'
                
                d[w] = d[u] + 1;
                pred[w] = u;
                
                queue.enqueue(w)
            }
        }
        // Change the state of vertex U to black when all adjacent vertices of vertex u are completely accessed
        color[u] = 'black';
    }
    // After the vertex is accessed, an object is returned
    return {
         distances: d,
         predecessors: pred
    }
        
}
Copy the code
  • After modifying the method, we get the following result after calling:
// The starting vertex is vertex A
const shortestPathA = graph.bfs(myVertices[0]); 
console.log(shortestPathA);


{
       distances: {A: 0.B: 1.C: 1.D: 1.E: 2.F: 2.G: 2.H: 2 , I: 3}, 
       predecessors: {A: null.B: "A".C: "A".D: "A".E: "B".F: "B".G: "C".H: "D".I: "E"}}Copy the code

And you can see that we’ve got the set of distances from vertex A to all the other vertices, and the set of retroactive vertices for each vertex. So we can get the shortest path from starting vertex A to the other vertices. Look at the following code:

let fromVertex = myVertices[0]; // vertex A
// Iterate over the list of vertices in the graph
for (let i = 1; i < myVertices.length; i++) {
    // Record a vertex
    let toVertex = myVertices[i];
    // Declare the path stack to record paths
    let path = new Stack();
    // trace toVertex to fromVertex; The variable v is assigned to the value of its trailing vertices to trace back the path
    for (letv = toVertex; v ! == fromVertex; v = shortestPathA.predecessors[v]) {// Push vertex V onto the stack
        path.push(v)
    }
    // Finally push the source vertex on the stack to get the full path
    path.push(fromVertex);
    // Stack rules: first in, last out, last in, first out, so we create variable s and assign it the source vertex at the end of the stack.
    let s = path.pop();
    // Loop out the vertices in the stack and concatenate them after s
    while(! path.isEmpty()) { s +=` - ${path.pop()}`
    }
    console.log(s)
}
Copy the code

Finally, we use the code above to get the shortest path from the source vertex (starting vertex A) to the other vertices in the graph.

Write in the last

It’s not easy to understand, it needs to be thought through…