前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >如何使用Java实现图的广度优先搜索?

如何使用Java实现图的广度优先搜索?

作者头像
用户1289394
发布2024-05-10 17:19:22
1380
发布2024-05-10 17:19:22
举报
文章被收录于专栏:Java学习网

图的广度优先搜索(Breadth-First Search,简称BFS)是一种用于遍历和搜索图的算法。它从图中的一个顶点开始,逐层地遍历其相邻顶点,并保持一个队列来存储待访问的顶点。BFS算法的核心思想是先访问离起始顶点最近的顶点,在此基础上逐层向外扩展,直到遍历完所有的顶点。

下面是使用Java实现图的广度优先搜索的示例代码:

代码语言:javascript
复制
import java.util.*;

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

    public GraphBFS(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]; // 记录顶点是否被访问过

        LinkedList<Integer> queue = new LinkedList<>(); // 使用队列保存待访问的顶点
        visited[s] = true;
        queue.add(s);

        while (queue.size() != 0) {
            s = queue.poll();
            System.out.print(s + " ");

            // 获取s的邻接顶点,如果未被访问过,则加入队列并标记为已访问
            Iterator<Integer> iterator = adj[s].listIterator();
            while (iterator.hasNext()) {
                int n = iterator.next();
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }

    public static void main(String args[]) {
        GraphBFS g = new GraphBFS(6);

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

        System.out.println("广度优先遍历结果:");
        g.BFS(0);
    }
}

上述示例代码中,我们首先定义了一个图的类GraphBFS,包含了图的顶点个数V和邻接表数组adj。构造函数用于初始化图的顶点和邻接表。addEdge方法用于添加边。

在BFS方法中,我们使用一个visited数组来记录顶点是否被访问过,并使用一个队列queue来保存待访问的顶点。首先将起始顶点标记为已访问,并入队。然后,开始循环遍历队列。每次从队列中取出一个顶点s,输出它,并将其未访问过的邻接顶点加入队列并标记为已访问。这样就完成了一次广度优先搜索。最终,所有顶点被访问完毕。

在main方法中,我们创建了一个图,并添加了边。然后调用BFS方法以广度优先的方式遍历图,并输出结果。

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

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2024-05-09,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 Java学习网 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档