首页 > 编程语言 >(Java)数据结构——图(第三节)BFS的实现

(Java)数据结构——图(第三节)BFS的实现

时间:2024-04-05 10:29:05浏览次数:30  
标签:index 结点 Java 邻接 int BFS neighbor 数据结构 cur

前言

本博客是博主用于复习数据结构以及算法的博客,如果疏忽出现错误,还望各位指正。

广度优先搜索的原理


好了,还是这张图,不过是广度优先搜索

不难看出,就是“一层一层”搜

这次咱从A开始,因为如果从B开始的话,只需要一次,搜索过程就是

B直接搜完,入队A C D E,isVistied全部ture,结束

所以从A开始

A开始,入队B、C,对应isVistited变为true

B出队,遍历,A,C已经遍历过,队尾入D、E,变true

C出队,没新的可入的

D出队

E出队

OK结束

所以,基本原理就是咱上一节说的:我的回合,碰到邻接结点先存起来,我的回合结束,再进入新的回合(队头)

广度优先搜索的代码实现

好了,说完原理,我们来进行代码实现

还是那两个方法

 一个是寻找当前结点的第一个邻接结点

    //获取index行 第一个邻接结点
    public int getFirstNeighbor(int index){
        for(int i = 0;i < vertexList.size();i++){
            if(edges[index][i] != Integer.MAX_VALUE){
                return i;    //找到就返回邻接结点的坐标
            }
        }
        return -1;    //没找到的话,返回-1
    }

另一个就是寻找当前结点的邻接结点的邻接结点(有点抽象,不过请看代码)

    //获取row行 column列之后的第一个邻接结点
    public int getNextNeighbor(int row,int column){
        for(int i = column + 1;i < vertexList.size();i++){
            if(edges[row][i] != Integer.MAX_VALUE){
                return i;    //找到就返回邻接结点的坐标
            }
        }
        return -1;    //没找到的话,返回-1
    }

之后就是主要的从哪个点开始进行BFS,最后那是要格外注意的,先前没有进入递归,因为是我的回合不停下,可以对比DFS,咱就可以理解了。

DFS里面,会调用含参DFS,之后再回到我的回合继续

BFS就是,入队,然后一直是我的回合


    public void BFS(int index,boolean[] isVisited){
        //BFS是由队列实现的,所以我们先创建一个队列
        LinkedList<Integer> queue = new LinkedList<>();
        System.out.print(getVertexByIndex(index)+" ");    //打印当前结点
        isVisited[index] =true;    //遍历标志ture
        queue.addLast(index);    //队尾加入元素
        int cur,neighbor;    //队列头节点cur和邻接结点neighbor
        while(!queue.isEmpty()){//如果队列不为空的话,就一直进行下去
            //取出队列头结点下标
            cur = queue.removeFirst();    //可以用作出队
            //得到第一个邻接结点的下标
            neighbor = getFirstNeighbor(cur);
            //之后遍历下一个
            while(neighbor != -1){//邻接结点存在
                //是否访问过
                if(!isVisited[neighbor]){
                    System.out.print(getVertexByIndex(neighbor)+" ");
                    isVisited[neighbor] = true;
                    queue.addLast(neighbor);
                }
                //在cur行找neighbor列之后的下一个邻接结点
                neighbor = getNextNeighbor(cur,neighbor);
            }
        }
    }

同样地,所有图的情况

//考虑到连通分量,需要对所有结点进行一次遍历,因为有Visited,所以不用考虑冲突情况
    public void BFS(){
        for(int i=0;i<vertexList.size();i++){
            if(!isVisited[i]){
                BFS(i,isVisited);
            }
        }
    }

以上就是BFS的所有内容

给出完整代码如下:

注意:每次之后记得清理isVisited为false,不然都是true

//package GraphTest.Demo;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

public class Graph{//这是一个图类
    /***基础属性***/
    int[][] edges;    //邻接矩阵存储边
    ArrayList<EData> to = new ArrayList<>();    //EData包含start,end,weight三个属性,相当于另一种存储方式,主要是为了实现kruskal算法定义的
    ArrayList<String> vertexList = new ArrayList<>();    //存储结点名称,当然你若想用Integer也可以,这个是我自己复习用的
    int numOfEdges;    //边的个数
    boolean[] isVisited;
    //构造器
    Graph(int n){
        this.edges = new int[n][n];
        //为了方便,决定讲结点初始化为INF,这也方便后续某些操作
        int INF = Integer.MAX_VALUE;
        for(int i=0;i<n;i++){
            Arrays.fill(edges[i],INF);
        }
        this.numOfEdges = 0;
        this.isVisited = new boolean[n];
    }
    //插入点
    public void insertVertex(String vertex){//看自己个人喜好,我这边是一个一个在主方法里插入点的名称
        vertexList.add(vertex);
    }
    //点的个数
    public int getNumOfVertex(){
        return vertexList.size();
    }
    //获取第i个节点的名称
    public String getVertexByIndex(int i){
        return vertexList.get(i);
    }
    //获取该节点的下标
    public int getIndexOfVertex(String vertex){
        return vertexList.indexOf(vertex);
    }
    //插入边
    public void insertEdge(int v1,int v2,int weight){
        //注意,这里是无向图
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        this.numOfEdges++;
        //如果要用Kruskal算法的话这里+
        to.add(new EData(v1,v2,weight));    //加入from to这种存储方式
    }
    //边的个数
    public int getNumOfEdge(){
        return this.numOfEdges;
    }
    //得到点到点的权值
    public int getWeight(int v1,int v2){//获取v1和v2边的权重
        return edges[v1][v2];
    }
    //打印图
    public void showGraph(){
        for(int[] line:edges){
            System.out.println(Arrays.toString(line));
        }
    }
    //获取index行 第一个邻接结点
    public int getFirstNeighbor(int index){
        for(int i = 0;i < vertexList.size();i++){
            if(edges[index][i] != Integer.MAX_VALUE){
                return i;    //找到就返回邻接结点的坐标
            }
        }
        return -1;    //没找到的话,返回-1
    }
    //获取row行 column列之后的第一个邻接结点
    public int getNextNeighbor(int row,int column){
        for(int i = column + 1;i < vertexList.size();i++){
            if(edges[row][i] != Integer.MAX_VALUE){
                return i;    //找到就返回邻接结点的坐标
            }
        }
        return -1;    //没找到的话,返回-1
    }
    //DFS实现,先定义一个isVisited布尔数组确认该点是否遍历过

    public void DFS(int index,boolean[] isVisited){
        System.out.print(getVertexByIndex(index)+" ");    //打印当前结点
        isVisited[index] = true;
        //查找index的第一个邻接结点f
        int f = getFirstNeighbor(index);
        //
        while(f != -1){//说明有
            if(!isVisited[f]){//f没被访问过
                DFS(f,isVisited);    //就进入该节点f进行遍历
            }
            //如果f已经被访问过,从当前 i 行的 f列 处往后找
            f = getNextNeighbor(index,f);
        }
    }
    //考虑到连通分量,需要对所有结点进行一次遍历,因为有Visited,所以不用考虑冲突情况
    public void DFS(){
        for(int i=0;i<vertexList.size();i++){
            if(!isVisited[i]){
                DFS(i,isVisited);
            }
        }
    }

    public void BFS(int index,boolean[] isVisited){
        //BFS是由队列实现的,所以我们先创建一个队列
        LinkedList<Integer> queue = new LinkedList<>();
        System.out.print(getVertexByIndex(index)+" ");    //打印当前结点
        isVisited[index] =true;    //遍历标志ture
        queue.addLast(index);    //队尾加入元素
        int cur,neighbor;    //队列头节点cur和邻接结点neighbor
        while(!queue.isEmpty()){//如果队列不为空的话,就一直进行下去
            //取出队列头结点下标
            cur = queue.removeFirst();    //可以用作出队
            //得到第一个邻接结点的下标
            neighbor = getFirstNeighbor(cur);
            //之后遍历下一个
            while(neighbor != -1){//邻接结点存在
                //是否访问过
                if(!isVisited[neighbor]){
                    System.out.print(getVertexByIndex(neighbor)+" ");
                    isVisited[neighbor] = true;
                    queue.addLast(neighbor);
                }
                //在cur行找neighbor列之后的下一个邻接结点
                neighbor = getNextNeighbor(cur,neighbor);
            }
        }
    }
    //考虑到连通分量,需要对所有结点进行一次遍历,因为有Visited,所以不用考虑冲突情况
    public void BFS(){
        for(int i=0;i<vertexList.size();i++){
            if(!isVisited[i]){
                BFS(i,isVisited);
            }
        }
    }

    public static void main(String[] args) {
        int n = 5;
        String[] Vertexs ={"A","B","C","D","E"};
        //创建图对象
        Graph graph = new Graph(n);
        for(String value:Vertexs){
            graph.insertVertex(value);
        }
        graph.insertEdge(0,1,7);
        graph.insertEdge(0,2,1);
        graph.insertEdge(1,2,6);
        graph.insertEdge(1,3,3);
        graph.insertEdge(1,4,5);
        graph.insertEdge(3,4,8);
        graph.showGraph();
//        for(EData i : graph.to){
//            System.out.println(i.toString());
//        }
        graph.DFS(1, graph.isVisited);
        System.out.println();
        graph.DFS();//再求求所有的,看有没有剩下的
        System.out.println();
        Arrays.fill(graph.isVisited,false);
        graph.BFS(1, graph.isVisited);
        System.out.println();
        Arrays.fill(graph.isVisited,false);
        graph.BFS();
        System.out.println();
    }
}

class EData{
    //当然,这是为了方便,直接记录结点下标,而不记录像"A"这种
    int start;
    int end;
    int weight;
    EData(int start,int end,int weight){
        this.start = start;
        this.end = end;
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "EData{" +
                "start=" + start +
                ", end=" + end +
                ", weight=" + weight +
                '}';
    }
}

前两行是DFS,DFS结点B之后没有进行清理

后两行是BFS,一个从B开始,一个从A开始

标签:index,结点,Java,邻接,int,BFS,neighbor,数据结构,cur
From: https://blog.csdn.net/m0_60631836/article/details/137385201

相关文章

  • Java -fastjson api
    构造json对象需求:构造以下请求体{"attrSelectionVO":[{"attrAccessId":"eea99a0894504a2b89f3cfeb4be051d3","attrValueList":[{"attrValue":"输送型","att......
  • Java.lang.OutOfMemoryError: GC overhead limit exceeded
    缘由系统是微服务架构,在服务器上跑了近11个微服务,某天发布更新部署新功能,几分钟后发现系统跑着跑着崩了。。。排查通过对11个微服务运行打印的日志,发现只有基础微服务日志中出现了GCoverheadlimitexceeded报错信息,然后从报GC异常的上一个报错的异常进行定位,发现是因为某......
  • Java项目:基于Springboot+vue实现的医院住院管理系统设计与实现(源码+数据库+开题报告+
    一、项目简介本项目是一套基于Springboot+vue实现的医院住院管理系统设包含:项目源码、数据库脚本等,该项目附带全部源码可作为毕设使用。项目都经过严格调试,eclipse或者idea确保可以运行!该系统功能完善、界面美观、操作简单、功能齐全、管理便捷,具有很高的实际应用价值......
  • 【附源码】计算机毕业设计智慧社区团购系统的设计(java+springboot+mysql+mybatis+论文
    本系统(程序+源码)带文档lw万字以上  文末可领取本课题的JAVA源码参考系统程序文件列表系统的选题背景和意义随着互联网技术的发展和普及,社区团购作为一种新兴的电商模式,正逐渐改变着人们的购物习惯。然而,传统的社区团购系统存在着一些问题,如信息不透明、效率低下、用户体......
  • 【附源码】计算机毕业设计游戏分享网站(java+springboot+mysql+mybatis+论文)
    本系统(程序+源码)带文档lw万字以上  文末可领取本课题的JAVA源码参考系统程序文件列表系统的选题背景和意义随着互联网技术的发展,游戏行业正逐渐向数字化、网络化方向发展。越来越多的游戏玩家开始通过网络分享自己的游戏心得、攻略和视频等内容,形成了一个庞大的游戏分享......
  • 【附源码】计算机毕业设计在线药品销售系统(java+springboot+mysql+mybatis+论文)
    本系统(程序+源码)带文档lw万字以上  文末可领取本课题的JAVA源码参考系统程序文件列表系统的选题背景和意义随着互联网技术的不断发展,人们的生活方式也在逐渐改变。在药品销售领域,传统的线下药店已经不能满足人们的需求。在线药品销售系统应运而生,为人们提供了一个更加便......
  • day18java学习打卡:类中属性的使用
    /* *类中属性的使用: *  *属性(成员变量) vs 局部变量 *1.相同点: * 1.1定义变量的格式:数据类型变量名=变量值; * 1.2先声明,后使用 * 1.3变量都有其对应的作用域 *  *  *2.不同点: * 2.1在类中声明的位置不同 *   属性:直接......
  • 【附源码】计算机毕业设计中医保健网站(java+springboot+mysql+mybatis+论文)
    本系统(程序+源码)带文档lw万字以上  文末可领取本课题的JAVA源码参考系统程序文件列表系统的选题背景和意义中医保健网站是一个提供中医养生、保健知识的在线平台。随着人们生活水平的提高,越来越多的人开始关注自己的身体健康,而中医作为中国传统医学的一种,具有悠久的历史......
  • 【附源码】计算机毕业设计长护险管理系统的设计与实现(java+springboot+mysql+mybatis+
    本系统(程序+源码)带文档lw万字以上  文末可领取本课题的JAVA源码参考系统程序文件列表系统的选题背景和意义长护险管理系统是一种基于互联网技术的信息化管理平台,旨在提高长期护理保险(简称“长护险”)的管理效率和服务质量。随着人口老龄化的加剧和社会保障体系的完善,长护......
  • 2024年4月4号java学习
    继承减少编写重复的代码,提高代码的复用性,使用extends关键字用来表示继承一个类如果类和类有相同的特性,并且一个类是另一个类的一种那么就可以使用继承java中只支持单继承,但有多层继承所有的类都间接或者直接继承Object类子类能够继承父类的东西虚方法表中包含:非私有方法,非f......