当前位置：首页 > article >正文

算法-图-数据结构（邻接矩阵）-BFS广度优先遍历

article 2025/2/25 14:48:47

邻接矩阵广度优先遍历（BFS）是一种用于遍历或搜索图的算法，以下是具体介绍：

1. 基本概念
图是一种非线性的数据结构，由顶点和边组成，可分为无向图、有向图、加权图、无权图等。邻接矩阵是表示图的一种数据结构，是一个二维数组，其中行和列都对应图中的顶点。如果顶点i与顶点j之间存在一条边，则矩阵的第i行第j列的元素为1；否则为0[^4^]。
广度优先搜索是一种遍历或搜索图的算法，它按照从根节点到最远节点的层次顺序进行搜索。在邻接矩阵中，BFS可以使用队列实现。

2. 算法步骤
2.1 初始化队列，用于存储待访问的节点，并将起点加入队列。
2.1 标记已访问节点，通常使用一个数组来记录每个节点是否已被访问过，以避免重复访问。
2.3从队列中取出一个节点，检查该节点是否为目标节点。如果是，则搜索结束；如果不是，将其所有未访问的邻接节点加入队列，并标记为已访问。
重复步骤3，直到队列为空或找到目标节点

3.算法实现

图数据结构定义

package com.example.demo;
//邻接矩阵广度优先遍历
public class YuGraph {
    private String[] v;
    private int[][] vG;
    //默认空构造
    YuGraph(){

    }
    //初始赋值构造
    YuGraph(String[] v,int [][] vG ){
        this.v=v;
        this.vG=vG;
    }

    public String[] getV() {
        return v;
    }

    public void setV(String[] v) {
        this.v = v;
    }

    public int[][] getvG() {
        return vG;
    }

    public void setvG(int[][] vG) {
        this.vG = vG;
    }
}

BFS算法实现

package com.example.demo;

import java.util.ArrayDeque;
import java.util.List;
import java.util.Queue;

//广度优先遍历
public class YuTestBFS {
    //插入变的关系
    public static void insertBian(int [][] a, int i,int j)
    {
        a[i][j]=1;
    }
    public static void bfsCreate()
    {
        //创建顶点
        String[] v=new String[]{"A","B","C","D","E"};
        //创建边
        int [][] vG=new int[v.length][v.length];
        //插入ab,bc,be,cd
        insertBian(vG,0,1);
        //bc
        insertBian(vG,1,2);
        //be
        insertBian(vG,1,4);
        //cd
        insertBian(vG,2,3);
        //创建邻接矩阵
        YuGraph graph=new  YuGraph(v,vG);
        //打印结果
        System.out.println("顶点");
        for(int i=0;i<graph.getV().length;i++)
        {
            System.out.print(graph.getV()[i]);
            System.out.print(" ");
        }
        System.out.println();
        System.out.println("邻接矩阵");
        for(int i=0;i<graph.getvG().length;i++)
        {
            for(int j=0;j<graph.getV().length;j++)
            {
                System.out.print(graph.getvG()[i][j]);
                System.out.print(" ");
            }
            System.out.println();
        }
        //BFS访问实现
        //1.定义访问标记列表
        boolean [] flagArr=new boolean[v.length];
        for(int i=0;i<v.length;i++)
        {
            flagArr[i]=false;
        }
        //2.定义辅助队列
        Queue<Integer> queue=new ArrayDeque<>();
        //A顶点入队
        queue.offer(0);
        flagArr[0]=true;
        System.out.print("BFS广度优先访问顶点:");
        System.out.print(v[0]);
        System.out.print(" ");
        //当队列不为空，逐层访问
        while (!queue.isEmpty())
        {
            //对头出队
            int vHead= queue.poll();
            //访问队头所在的邻接矩阵
            for(int i=0;i<v.length;i++)
            {
                if(graph.getvG()[vHead][i]==1&&flagArr[i]==false)
                {
                    //访问
                    System.out.print("访问 ");
                    System.out.print(v[i]);
                    System.out.print(" ");
                    flagArr[i]=false;
                    //被访问的点入队
                    queue.offer(i);
                }
            }
        }
    }

    public static void main(String[] args) {
        bfsCreate();
    }
}

结果样例