java实现广度优先算法

实现思路
广度优先方式，是一种地毯式搜索，层层递进的方式，即从开始节点依次遍历相邻节点，层层递进

代码实现
基于之前图的数据结构，实现广度优先算法

import java.util.*;


public class UndiGraph {
    
    private int point;

    
    private linkedList adjacencyList[];

    
    public UndiGraph(int point){
        this.point = point;
        // 初始化连接表数组
        adjacencyList = new linkedList[point];
        for (int i = 0; i < point; i++) {
            // 初始化邻接表的每一个槽位的连表
            adjacencyList[i] = new linkedList<>();
        }
    }

    
    public void addPoint(int s,int t) {
        // 数组的下标，代表当前顶点，连表的数据代表的临边数据
        adjacencyList[s].add(t);
        // 因为没有方向，两个节点是互联关系，因此目标节点连线出也有源节点
        adjacencyList[t].add(s);
    }

    
    public void bfs(int f,int t){
        if (f == t){
            return;
        }
        // 定义一个boolean类型的数组，用来记录顶点是否被访问过
        boolean[] visited = new boolean[this.point];
        // 表明起始顶点已经被访问
        visited[f] = true;
        
        Queue queue = new linkedList<>();
        queue.add(f);
        
        int[] prev = new int[this.point];
        // 初始化线路为-1
        initRouter(prev);
        
        while (!queue.isEmpty()){
            // 取出队列中的顶点，获取相邻顶点进行访问
            Integer p = queue.poll();
            // 遍历顶点的相邻顶点
            for (int i = 0; i < this.adjacencyList[p].size(); i++) {
                // 获取当前节点所连接的点
                Integer sibiling = this.adjacencyList[p].get(i);
                // 判断节点是否有被访问过，未访问过，则进行访问操作
                if (!visited[sibiling]){
                    prev[sibiling] = p;
                    if (sibiling==t){
                        printRouterST(prev,f,t);
                        return;
                    }
                    // 标记
                    visited[sibiling] = true;
                    // 相邻顶点存入队列
                    queue.add(sibiling);
                }
            }
        }
    }
    
    public void initRouter(int[] router){
        for (int i = 0; i < router.length; i++) {
            router[i] = -1;
        }
    }


    
    public void printRouterST(int[] prev,int s,int t){
        if (prev[t] != -1 && s != t){
            // prev记录的是当前路线，因此向前追溯，一直到开始节点依次打印
            printRouterST(prev,s,prev[t]);
        }
        System.out.print(t+">>");
    }

    public static void main(String[] args) {
        UndiGraph undiGraph = new UndiGraph(8);
        undiGraph.addPoint(0,1);
        undiGraph.addPoint(0,3);
        undiGraph.addPoint(1,2);
        undiGraph.addPoint(1,4);
        undiGraph.addPoint(2,5);
        undiGraph.addPoint(3,4);
        undiGraph.addPoint(4,5);
        undiGraph.addPoint(4,6);
        undiGraph.addPoint(5,7);
        undiGraph.addPoint(6,7);
        //undiGraph.bfs(0,7);

        undiGraph.bfsAllRouter(0,7);
    }
}