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

 

介绍

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

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

• • 广度优先搜索（BFS）

广度优先搜索

广度优先搜索（BFS）会“逐层”访问。这意味着在一个Graph中（如下图所示），它首先访问起始节点的所有子节点。这些孩子被视为“第二层”。

与（DFS）不同，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
    
     > 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
    
      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, 2Node 1 has neighbors: 0Node 2 has neighbors: 3, 0Node 3 has neighbors: 2, 0

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

 

 

 

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

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

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

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

1. 从队列中删除第一个元素，在本例中为1，将其标记为已访问
2. 将所有1的未访问邻居添加到队列（仅0）

1. 从队列中删除第一个元素，在这种情况下为0，将其标记为已访问
2. 将所有0的未访问邻居添加到队列中（节点3和2，1已被标记为已访问）

1. 从队列中删除第一个元素，在本例中为3，将其标记为已访问
2. 将所有3个未访问的邻居添加到队列中（不存在）

1. 从队列中删除第一个元素，在本例中为2，将其标记为已访问
2. 将所有2个未访问的邻居添加到队列中（同样，没有一个）
3. 队列现在为空，BFS已完成

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

QueueJava中有几种类型的实现，但是我们将改用a LinkedList，因为它提供了所有必需的方法。

我们将以下方法添加到我们的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
    
      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
     
       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 1Using the modified version of BFS we get:0 3 14 2

还有一种叫做“双向” BFS搜索的东西。当我们想要找到两个顶点（节点）之间的最短路径时，这很有用。

这是通过同时（在不同线程中）从起始节点和目标节点运行BFS来实现的。从理论上讲，这可以找到两个节点之间的最短路径，其速度是仅从起始节点运行BFS的速度的两倍。

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

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

 

结论

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

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

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