Lost a few hairs, and finally learned - graph traversal -dfs and BFS

One 、 review

Graph search algorithm is the process of traversing each node in the graph . We classify them according to the order in which their nodes are accessed . Now we will introduce Breadth first traversal (Breadth-first Search abbreviation bfs)、 Depth-first traversal (Depth-first Search abbreviation dfs) . These two algorithms are the basis of graph traversal , It is also commonly used in the preliminary exploration of data and many subsequent graph routing algorithms (Pathfinding Algorithm) Are based on this foundation .

Two 、 Breadth first traversal

3.1 brief introduction

Ergodic graph algorithm BFS Is the most commonly used method .

BFS Is a traversal algorithm , Select a node （ Source or starting node ） Start traversing and traverse the graph layer by layer , To explore neighbor nodes （ Nodes directly connected to the source node ）. then , You must move to the next neighbor node .

just as BFS As your name implies , You need to traverse the graph as follows ：

1. First move horizontally , Access all nodes of the current layer
2. Move to the next level

The following picture shows the sequence of traversal :

BFS Of Time complexity by O(V + E), among V It's the number of nodes ,E It's the number of sides .

3.2 Code

public void compute(int startId) {
        System.out.println("=========== BFS ===========");
        boolean[] visited = new boolean[graphApi.getVertexSize()];
        //visited[startId] = true;

        List<Integer> currentIds = new ArrayList<>();
        currentIds.add(startId);

        int depth = 1;
        while (currentIds.size() != 0) {
            Set<Integer> nextId = new HashSet<Integer>();
            System.out.println("depth is " + (depth++) + " neighbors is " + currentIds);
            for (Integer id : currentIds) {
                if(visited[id]) {
                    continue;
                }
                visited[id] = true;

                int[] edge = graphApi.getEdge(id);
                if (edge != null) {
                    for (int eId : edge) {
                        nextId.add(eId);
                    }
                }
            }
            currentIds.clear();
            currentIds.addAll(nextId);
        }

        System.out.println("");
    }

3、 ... and 、 Depth-first traversal

3.1. brief introduction

DFS The algorithm is a recursive algorithm that uses the idea of backtracking . If possible , It involves a detailed search of all nodes , If possible , By backtracking .

ad locum , word backtrack It means that when you move forward and there are no more nodes along the current path , You move backward on the same path to find the node to traverse . All nodes will be accessed on the current path , Until all unreached nodes are traversed , Then choose the next path .

DFS This recursive feature of can be implemented using stack . The basic idea is as follows ：

Select a starting node and push all its adjacent nodes onto the stack .

Pop a node from the stack to select the next node to access and push all its adjacent nodes onto the stack . Repeat the process , Until the stack is empty . however , Make sure that the accessed node is marked . This will prevent you from accessing the same node multiple times . If you do not mark the visited node and you visit the same node multiple times , You may fall into an infinite loop .

The following picture shows the sequence of traversal :

DFS Of Time complexity by O(V + E), among V It's the number of nodes ,E It's the number of sides .

3.2. Code implementation

1. Recursive implementation

public void dfs(int i, boolean[] visited, GraphApi graphApi) {
        System.out.print(i);
        visited[i] = true;
        int[] edgeIds = graphApi.getEdge(i);

        if (edgeIds == null) {
            System.out.print(" -> ");
            return;
        } else {
            System.out.print(" -> ");
        }

        for (int edgeId : edgeIds) {
            if(!visited[edgeId]) {
                dfs(edgeId, visited, graphApi);
            }
        }
    }

2. Simulate stack implementation

 public void compute(int i, boolean[] visited) {
        Stack<Integer> stack = new Stack<>();
        //  Root node stack 
        stack.push(i);
        visited[i] = true;

        while (!stack.isEmpty()) {
            Integer id = stack.pop();
            System.out.print(id + " -> ");
            //  Logical processing 
            int[] edge = graphApi.getEdge(id);
            if(edge != null) {
                for (int item : edge) {
                    if(!visited[item]) {
                        stack.push(item);
                        visited[item] = true;
                    }
                }
            }
        }
    }

Detailed source code address :
https://github.com/RoadTLife/TGraph