java实现广度优先搜索算法

2023-12-26 18:34:32

广度优先搜索算法(BFS)是一种用于图遍历的算法。它从图的某个节点开始,依次访问其所有邻接节点,再依次访问邻接节点的邻接节点,以此类推,直到遍历完所有节点。

BFS使用队列数据结构来实现遍历过程。具体步骤如下:

  1. 将起始节点标记为已访问,并将其加入队列。
  2. 重复以下步骤直到队列为空:
    • 从队列中取出一个节点,并访问该节点。
    • 将该节点的所有未访问邻接节点加入队列,并标记为已访问。
  3. 遍历完所有节点后,算法结束。

BFS的特点是按层遍历图,即先访问起始节点的所有邻接节点,然后访问邻接节点的邻接节点,以此类推。因此,BFS可以用来解决寻找最短路径的问题,即找到从起始节点到目标节点的最短路径。

BFS的时间复杂度为O(V+E),其中V是图的节点数,E是图的边数。

以下是使用Java实现广度优先搜索算法的示例代码:

import java.util.LinkedList;
import java.util.Queue;

class Graph {
    private int V; // 图的顶点数
    private LinkedList<Integer> adj[]; // 邻接表

    public Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i=0; i<v; ++i) {
            adj[i] = new LinkedList();
        }
    }

    // 添加边
    void addEdge(int v, int w) {
        adj[v].add(w);
    }

    // 广度优先搜索
    void BFS(int s) {
        boolean visited[] = new boolean[V]; // 记录顶点是否被访问过

        Queue<Integer> queue = new LinkedList<>(); // 创建队列用于广度优先搜索
        visited[s] = true; // 标记起始顶点为已访问
        queue.add(s); // 将起始顶点加入队列

        while (queue.size() != 0) {
            s = queue.poll(); // 从队列中弹出一个顶点并访问
            System.out.print(s + " ");

            // 遍历邻接表中的所有相邻顶点
            for (int i : adj[s]) {
                if (!visited[i]) {
                    visited[i] = true; // 标记相邻顶点为已访问
                    queue.add(i); // 将相邻顶点加入队列
                }
            }
        }
    }

    public static void main(String args[]) {
        Graph g = new Graph(4);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        System.out.println("广度优先遍历 (从顶点2开始):");
        g.BFS(2);
    }
}

在上面的示例代码中,我们首先创建了一个Graph类来表示图。Graph类中包含一个邻接表用于存储图的结构,并提供addEdge方法来添加边。

然后定义了一个BFS方法来执行广度优先搜索算法。在BFS方法中,我们使用一个boolean数组visited来记录顶点是否被访问过。我们使用一个Queue来存储待访问的顶点,起始时将起始顶点加入队列,并标记为已访问。

接下来,我们开始进行循环,直到队列为空。在每次循环中,我们从队列中弹出一个顶点s,并访问该顶点,然后遍历邻接表中的所有相邻顶点。如果相邻顶点i没有被访问过,我们将其标记为已访问,并将其加入到队列中。

最后,我们在main方法中创建一个图对象,并添加一些边来测试广度优先搜索算法。我们从顶点2开始进行广度优先遍历,并输出遍历的结果。

以上就是用Java实现广度优先搜索算法的示例代码。

文章来源:https://blog.csdn.net/m0_37649480/article/details/135192017
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。