Front end soldier, not stingy give advice

background

After seeing many predecessors’ sharing, the author would like to sort out the ergodic calculation method of graphs.

Graph traversal calculation method is divided into depth first traversal and breadth first traversal, these two algorithms from the literal understanding, can be very clear. One is to search continuously for lower nodes based on depth. If there are lower nodes, continue to search recursively. Otherwise, go back to the higher level and enter by the lower nodes that have not been traversed. The other is to look for all the children of a node in breadth, and then look for all the children down from all the children.

This is the author’s view of the shallow level of depth and breadth first traversal. Next, carry on detailed analysis and understanding.

Depth-first traversal (DFS)

The idea of depth-first traversal can be divided into the following steps:

  1. Designate a point as a vertex, mark it, and find any neighboring nodes of that node.

  2. If the adjacent node is not visited, mark it and enter the recursion to find its unmarked adjacent nodes; If the node is marked for access, it goes back to the parent node, looks for its unmarked adjacent nodes, and then recurses until all vertices connected to the starting point are marked for access.

  3. If all nodes are marked for access, end; Conversely, if there is still a node that has not been accessed, the next recursive lookup needs to take that node as the vertex until all points have been marked for access.

We will first select a node as the vertex, here we start with 0, then mark, and find any neighboring nodes of the node.

If the adjacent node is not visited, it is marked and the recursion is entered to find its unmarked adjacent nodes

Since the neighboring nodes 3 and 0 of node 4 have already been accessed, it will go back to node 0 and enter the next recursion until all vertices connected to the starting point have been marked for access

All the vertices above are visited and the traversal ends. If there are any unvisited nodes, it means that the unvisited nodes are not connected to node 0 and are independent of the path. The access order of the above undirected graph is: V0, V1, V3, V7, V4, v2, V5, V8, v6 (not unique)

Breadth-first traversal (BFS)

Breadth-first traversal, also known as “width first search” or “horizontal first search”, or BFS for short. Its realization idea is: starting from a point, find out its adjacent node into the queue and mark, and then pop out the first node from the queue, find its adjacent node has not been visited into the queue, until all the nodes have been visited the adjacent point; If there are still unaccessed points in the figure, select another unaccessed point and perform the same operation until all nodes in the figure are accessed.

From near to far access, the steps are:

  1. Create a queue and put the start node into the queue

  2. If the queue is not empty, the first node is removed from the queue and checked to see if it is the target node

    • If the target node, the search ends and the result is returned
    • If not, all of its undetected children are enqueued

  3. If the queue is empty, there is no target node in the graph and the traversal ends

In the above figure, no target node is set, so all nodes are traversed. Node 0 is accessed first, then node 1,4,2, then node 3,5, and finally node 7,8,6, so it is accessed in the following order: v0, v1, v4, v2, v3, v5, v7, v8, v6 (not unique)

Create a graph:

const vertices = []; // The vertex set of the graph
const edges = new Map(); // Graph edge set

/** * Add node **/
addVertex = (v: string) = > {
  this.vertices.push(v);
  this.edges.set(v, []);
};

/** * add edge **/
addEdge = (v: string, w: string) = > {
  const vEdge = edges.get(v);
  vEdge.push(w);
  const wEdge = edges.get(w);
  wEdge.push(v);
  edges.set(v, vEdge);
  edges.set(w, wEdge);
};

formatToString = (a)= > {
  let s = "";
  vertices.forEach(v= > {
    s += `${v}- > `;
    const neighors = edges.get(v);
    neighors.forEach(n= > (s += `${n} `));
    s += "\n";
  });
  return s;
};
Copy the code

Deep search:

graphDFS = (a)= > {
  const marked = [];
  vertices.forEach(v= > {
    if (!marked[v]) {
      dfsVisit(v);
    }
  });

  const dfsVisit = (u: string) = > {
    marked[u] = true;
    const neighbors = edges.get(u);
    neighors.forEach(n= > {
      if (!marked[n]) {
        dfsVisit(n);
      }
    });
  };
};
Copy the code

Wide search:

graphBFS = (v: string, t? :string) = > {
  const queue = [],
    marked = [];
  marked[v] = true;
  queue.push(v); // add to the end of the queue
  while (queue.length > 0) {
    const s = queue.shift(); // Remove from team head
    if (t && s === t) {
      console.log("target vertex: ", t);
      return;
    } else if (edges.has(s)) {
      console.log("visited vertex: ", s);
    }
    const neighbors = edges.get(s);
    neighors.forEach(n= > {
      if(! marked[n]) { marked[n] =true; queue.push(n); }}); }};Copy the code

conclusion

Today, I sorted out my understanding of the idea and implementation of depth-first traversal and breadth-first traversal, thank you for watching, thank you!

Standing on the shoulders of giants

Depth-first traversal and breadth-first traversal