BFS&DFS

Posted on 2022-05-13 Edited on 2022-05-18 In algorithm Views:

图结构：

Map<String, String[]> graph = new HashMap<String, String[]>(){{
    put("A", new String[]{"B", "C"});
    put("B", new String[]{"A", "C", "D"});
    put("C", new String[]{"A", "B", "D", "E"});
    put("D", new String[]{"B", "C", "E", "F"});
    put("E", new String[]{"C", "D"});
    put("F", new String[]{"D"});
}};

BFS

思路

广度优先搜索算法的基本思想是：优先在当前层进行搜索，搜索完全后，再进入与当前层关联的下一层进行搜索；直到搜索完所有节点进而终止。

依据广度优先的思路，对于我们的问题进行一次展开：

步骤1：假定选择顶点 A 做为起点，首先搜索 A；

步骤2：进入下一层，

步骤2.1：顶点 A 的邻接点 B 、 C ，搜索 B 、 C ；

步骤3：进入下一层，

步骤3.1：顶点 B 的邻接点 A 、 C 、 D ， A 、 C 已经搜索过了，搜索 D ；

步骤3.2：顶点 C 的邻接点有 A 、 B 、 D 、 E ， A 、 B 、 C 、 D 已经搜索过了，搜索 E ；

步骤4：进入下一层，

步骤4.1：3.1中 D 的邻接点只有 F 没有搜索，搜索 F ；

步骤4.2：3.2中 E 的邻接点都搜索过了，终止；

最后，一个可能的解是：A->B->C->D->E->F

代码

BFS实现：

public void BFS(Map<String, String[]> graph, String start) {
    Queue<String> queue = new ArrayDeque();
    queue.offer(start);

    Set<String> visited = new HashSet<>();
    visited.add(start);

    while (!queue.isEmpty()) {
        String vertex = queue.poll();

        for(String adVertex : graph.get(vertex)) {
            if(!visited.contains(adVertex)) { // 存在有环图，入队前判断是否已经访问过
                queue.offer(adVertex);
                visited.add(adVertex);
            }
        }

        System.out.print(vertex + " ");
    }
}

求解的问题

可以用于求解图中两点间的最短路径；

DFS

思路

代码

DFS实现：

public void DFS(Map<String, String[]> graph, String start) {
    Deque<String> stack = new ArrayDeque();
    stack.push(start);

    Set<String> visited = new HashSet<>();
    visited.add(start);

    while (!stack.isEmpty()) {
        String vertex = stack.pop();

        for(String adVertex : graph.get(vertex)) {
            if(!visited.contains(adVertex)) { // 存在有环图，入队前判断是否已经访问过
                stack.push(adVertex);
                visited.add(adVertex);
            }
        }

        System.out.print(vertex + " ");
    }
}

jtLiBrain

BFS&DFS

BFS

思路

代码

求解的问题

DFS

思路

代码

Dijkstra

参考