Java实现深度优先和广度优先

图实现代码（公共部分）

/**
 * 无向图实现：邻接矩阵
 */
public class Matrix {
    //用于保存顶点信息
    private static List<String> arrayList = new ArrayList<>();
    //用于绑定顶点和数组
    private static Map<String,Integer> hashMap = new HashMap<>();
    private static int nums = 0;
    //二阶矩阵用于保存顶点间的连通情况
    public int[][] edges;
    //用于标记是否被查询过
    public boolean[] isSearch;

    public Matrix(int n) {
        edges = new int[n][n];
        isSearch = new boolean[n];
    }

    public void register() {
        arrayList.forEach((String node) -> hashMap.put(node,nums++));
    }

    public void add(String node) {
        arrayList.add(node);
    }

    public void add(String start, String end, int weight) {
        int start_num = hashMap.get(start);
        int end_num = hashMap.get(end);
        //因为是无向图，所以需要双向添加权重
        edges[start_num][end_num] = weight;
        edges[end_num][start_num] = weight;
    }

    public int getNums() {
        return nums;
    }

    public void print() {
        for(int i=0; i<edges.length; i++) {
            for(int j=0; j<edges.length; j++) {
                System.out.print(edges[i][j] + " ");
            }
            System.out.println("");
        }
    }
}

深度优先

深度优先是指：首顶点开始访问，当访问完顶点的第一个邻接顶点时候，以该领结顶点为首顶点访问它对应的第一次邻接顶点，以此类推，当访问不到邻接顶点的时候，返回上一层，由上一层向第二个邻接顶点访问，继续以此方式类推

    /*
    深度优先实现：（核心：优先深度，即纵向）
    1.搜索首顶点的第一个邻接顶点，搜索到后再次向下搜索
    2.如果搜索不到，则返回上层顶点，去搜索第二个邻接顶点，依此顺序反复进行
     */
    //用于DFS，此处的n相当于edges的横坐标，用于搜索第一个邻接顶点
    public int getFirst(int n) {
        //此时的 i 相当于edges的纵坐标
        for(int i=0;i<edges.length; i++) {
            //找到并且没有被遍历过的，如果被search过就往后遍历
            if(edges[n][i] == 1 && !isSearch[i]) {
                return i;
            }
        }
        //代表没找到
        return -1;
    }

    public void DFS(int n) {
        if (n == -1) {
            return;
        }
        System.out.println("Searched -> " + n);
        isSearch[n] = true;
        int first = getFirst(n);
        DFS(first);
    }

样例测试

    public static void main(String[] args) {
        Matrix matrix = new Matrix(3);
        //添加顶点信息
        matrix.add("北京");
        matrix.add("武汉");
        matrix.add("十堰");

        //将顶点进行注册
        matrix.register();

        //添加顶点间的关系
//        matrix.add("北京","武汉",1);
        matrix.add("北京","十堰",1);
        matrix.add("武汉","十堰",1);

        //输出邻接矩阵
        matrix.print();
        //代表从首顶点开始访问
        matrix.DFS(0);
    }

//输出结果
0 0 1 
0 0 1 
1 1 0 
Searched -> 0
Searched -> 2
Searched -> 1

广度优先

广度优先是指：首顶点开始顺序向后访问（即访问所有自己可达的顶点），每访问一个我们需要将其入队（此处需要一个队列，元素不可重复，这里我简称这种关系为父子顶点），如果存在自己不可达的顶点，则尝试使用队列中已访问过的订单进行尝试访问（即出队），如果子顶点可以访问到父顶点无法访问到的顶点时，将现在访问的结点入队，并设置标记为true（代表已访问），以此类推。
有点类似于Java的类加载机制，父顶点访问不到的再由子顶点进行访问。

/*
    广度优先实现：（核心：优先广度，即横向）
    1.首先获取首顶点，向后遍历，如果后面的顶点可以访问则直接访问，如果不能访问，则从已访问的顶点中进行间接获取。
    例：
    A->B
    B->C
   首先访问A，然后通过A访问B，（这里需要注意通过间接访问已访问的结点的是需要一个队列实现，）
   然后想访问C，发现A无法访问，则从A已访问的顶点B检验，发现B能访问C，访问结束。
     */
    public void BFS(int n) {
        Queue<Integer> queue = new LinkedList<>();
        System.out.println("First Searched -> " + n);
        isSearch[n] = true;
        for(int i=0; i<edges.length; i++) {
            //通过自身可直接访问
            if(edges[n][i] == 1 && !isSearch[i]) {
                System.out.println(n + " Searched -> " + i);
                //将已访问结点入队
                queue.offer(i);
                isSearch[i] = true;
                nums++;
            }
        }
        //代码进行到这里说明首顶点已经访问了自己能访问的所有顶点，并且将其入队


        //将队列中的全部顶点进行一个按队列遍历
        while(!queue.isEmpty() && nums != n) {
            //获取队首的顶点值 (相当于横坐标)
            Integer next = queue.poll();
            for(int i=0; i<edges.length; i++) {
                if(edges[next][i] == 1 && !isSearch[i]) {
                    System.out.println(next + " Searched -> " + i);
                    //将已访问结点入队
                    queue.offer(i);
                    isSearch[i] = true;
                    nums++;
                }
            }
        }
    }

样例测试

    public static void main(String[] args) {
        Matrix matrix = new Matrix(3);
        //添加顶点信息
        matrix.add("北京");
        matrix.add("武汉");
        matrix.add("十堰");

        //将顶点进行注册
        matrix.register();

        //添加顶点间的关系
//        matrix.add("北京","武汉",1);
        matrix.add("北京","十堰",1);
        matrix.add("武汉","十堰",1);

        //输出邻接矩阵
        matrix.print();
        matrix.BFS(0);
    }


//测试结果
0 0 1 
0 0 1 
1 1 0 
//为了看的更方便是通过谁找到的谁，这里输出结果动了一下手脚
First Searched -> 0
0 Searched -> 2
2 Searched -> 1