Java中的图形：广度优先搜索（BFS）

实作

我们将使用通过邻接表实现的图，就像用于DFS一样。另外，我们需要visited在visit()和univisit()方法旁边添加属性到我们的Node类中：

public class Node {
    int n;
    String name;
    boolean visited;

    Node(int n, String name) {
        this.n = n;
        this.name = name;
        visited = false;
    }

    void visit() {
        visited = true;
    }

    void unvisit() {
        visited = false;
    }
}

现在，让我们定义一个Graph：

public class Graph {

    // Each node maps to a list of all his neighbors
    private HashMap<Node, LinkedList<Node>> adjacencyMap;
    private boolean directed;

    public Graph(boolean directed) {
        this.directed = directed;
        adjacencyMap = new HashMap<>();
    }

    // ...
}

现在，让我们添加方法addEdge()。我们将使用两种方法，辅助方法和实际方法。

在辅助方法中，我们还将检查可能的重复边缘。在A和之间添加边之前B，我们先将其删除，然后再添加。如果存在（我们要添加重复的边），则将其删除，然后再次添加，只有一个。

但是，如果它不存在，那么删除不存在的边将导致，NullPointerException因此我们引入了列表的临时副本：

public void addEdgeHelper(Node a, Node b) {
    LinkedList<Node> tmp = adjacencyMap.get(a);

    if (tmp != null) {
        tmp.remove(b);
    }
    else tmp = new LinkedList<>();
    tmp.add(b);
    adjacencyMap.put(a,tmp);
}

public void addEdge(Node source, Node destination) {

    // We make sure that every used node shows up in our .keySet()
    if (!adjacencyMap.keySet().contains(source))
        adjacencyMap.put(source, null);

    if (!adjacencyMap.keySet().contains(destination))
        adjacencyMap.put(destination, null);

    addEdgeHelper(source, destination);

    // If a graph is undirected, we want to add an edge from destination to source as well
    if (!directed) {
        addEdgeHelper(destination, source);
    }
}

最后，我们将有printEdges()，hasEdge()和resetNodesVisited()辅助方法，这是非常简单的：

public void printEdges() {
    for (Node node : adjacencyMap.keySet()) {
        System.out.print("The " + node.name + " has an edge towards: ");
        for (Node neighbor : adjacencyMap.get(node)) {
            System.out.print(neighbor.name + " ");
        }
        System.out.println();
    }
}

public boolean hasEdge(Node source, Node destination) {
    return adjacencyMap.containsKey(source) && adjacencyMap.get(source).contains(destination);
}

public void resetNodesVisited(){
    for(Node node : adjacencyMap.keySet()){
        node.unvisit();
    }
}

让我们在以下无向图上检查BFS算法：

Node 0 has neighbors: 1, 3, 2
Node 1 has neighbors: 0
Node 2 has neighbors: 3, 0
Node 3 has neighbors: 2, 0

我们可以选择任何节点作为起点，所以从1开始。我们重复从队列中添加和删除节点的过程，直到队列为空。

队列是FIFO（先进先出）数据结构。它的工作方式就像现实中的队列一样，因此，按添加顺序逐个处理条目（从队列中删除）。

对于BFS来说，这是一种非常方便的数据结构，因为我们希望按照访问它们的顺序来处理节点，并确保首先处理与起始节点“更近”的节点。

由于将它们添加到队列中，然后再将离起始节点“更远”的任何节点添加到队列中，因此我们知道将首先处理较近的节点。

我们从一个仅包含节点1的队列开始

订阅我们的新闻
在收件箱中获取临时教程，指南和作业。从来没有垃圾邮件。随时退订。

订阅电子报
订阅

我们的节点按1-0-3-2顺序访问。显然，步骤2-3、4-5、6-7和8-9的设置相同，并且步骤10是我们的循环终止条件。这样看来，为我们的breadthFirstSearch(Node node)方法编写代码应该很容易。

QueueJava有几种类型的实现，但是我们将使用aLinkedList代替，因为它提供了所有必需的方法。

我们在类中添加以下方法Graph：

void breadthFirstSearch(Node node) {

    // Just so we handle receiving an uninitialized Node, otherwise an
    // exception will be thrown when we try to add it to queue
    if (node == null)
        return;

    // Creating the queue, and adding the first node (step 1)
    LinkedList<Node> queue = new LinkedList<>();
    queue.add(node);

    while (!queue.isEmpty()) {
        Node currentFirst = queue.removeFirst();

        // In some cases we might have added a particular node more than once before
        // actually visiting that node, so we make sure to check and skip that node if we have
        // encountered it before
        if (currentFirst.isVisited())
            continue;

        // Mark the node as visited
        currentFirst.visit();
        System.out.print(currentFirst.name + " ");

        LinkedList<Node> allNeighbors = adjacencyMap.get(currentFirst);

        // We have to check whether the list of neighbors is null before proceeding, otherwise
        // the for-each loop will throw an exception
        if (allNeighbors == null)
            continue;

        for (Node neighbor : allNeighbors) {
            // We only add unvisited neighbors
            if (!neighbor.isVisited()) {
                queue.add(neighbor);
            }
        }
    }
    System.out.println();
}

现在，我们在代码中创建示例图，并检查我们的方法是否按预期工作：

public class GraphShow {
    public static void main(String[] args) {

        Graph graph = new Graph(false);
        Node a = new Node(0, "0");
        Node b = new Node(1, "1");
        Node c = new Node(2, "2");
        Node d = new Node(3, "3");
        Node e = new Node(4, "4");

        graph.addEdge(a,d);
        graph.addEdge(a,b);
        graph.addEdge(a,c);
        graph.addEdge(c,d);

        graph.breadthFirstSearch(b);
    }
}

输出：

1 0 3 2

如果您阅读了DFS文章，那么您可能还记得我们曾经遇到过这样的情况：在未连接的图中，并非所有节点都将被打印出来，因为该算法将遍历所有可能的节点，然后停止。

BFS也会发生同样的事情，并且在定向图时也会发生这种情况，有时我们无法到达所有节点。有时，这是我们要寻找的行为，但有时，我们希望访问所有节点。

我们将执行与DFS中相同的操作，即，只要有任何未访问的节点，我们就将继续调用BFS。我们将创建一个新breadthFirstSearchModified(Node node)方法为我们完成此任务：

void breadthFirstSearchModified(Node node) {
    breadthFirstSearch(node);

    for (Node n : adjacencyMap.keySet()) {
        if (!n.isVisited()) {
            breadthFirstSearch(n);
        }
    }
}

public class GraphShow {
    public static void main(String[] args) {

        Graph graph = new Graph(false);
        Node a = new Node(0, "0");
        Node b = new Node(1, "1");
        Node c = new Node(2, "2");
        Node d = new Node(3, "3");
        Node e = new Node(4, "4");

        graph.addEdge(a,d);
        graph.addEdge(a,b);
        graph.addEdge(c,e);

        System.out.println("Using the unmodified version of BFS we get:");
        graph.breadthFirstSearch(a);

        graph.resetNodesVisited();
        System.out.println("Using the modified version of BFS we get:");
        graph.breadthFirstSearchModified(a);
    }
}

输出：

Using the unmodified version of BFS we get:
0 3 1
Using the modified version of BFS we get:
0 3 1
4 2

还有一种叫做“双向” BFS搜索的东西。当我们想要找到两个顶点（节点）之间的最短路径时，这很有用。
这是通过同时（在不同线程中）从起始节点和目标节点运行BFS来实现的。从理论上讲，这可以找到两个节点之间的最短路径，而这仅仅是从起始节点运行BFS的两倍。

注意：与DFS一样，如果我们要以特定顺序（而不是添加边的顺序）遍历邻居，则可以使用aPriorityQueue代替aLinkedList来邻居列表。

该代码是相同的，我们只需要执行Comparable并添加compareTo()方法给我们的Node类。

结论

图形是存储某些类型的数据的便捷方法。该概念是从数学移植而来的，适合于计算机科学的需求。

由于许多事物可以用图形表示，因此图形遍历已成为一项常见的任务，尤其是在数据科学和机器学习中。

广度优先搜索是为数不多的图形遍历算法之一，并且“逐层”访问节点。与深度优先搜索不同，BFS不会主动到达一个分支，直到到达终点为止，而是当我们从一个节点开始搜索时，它会访问该节点的所有未访问邻居，然后再访问另一个节点的所有未访问邻居。。

译者：啊强啊

链接： https://stackabuse.com/graphs-in-java-breadth-first-search-bfs/

来源：Stack Abuse

编辑于 2020-10-15 16:28

Java

Java 编程

Java 程序员

介绍

广度优先搜索

实作

结论