JAVA-图的广度优先遍历

1、建立结点类

//结点类

public class Bread_Node {
    // 顶点内容
    private String data;
    // 顶点是否被访问过，true为已被访问，false为未被访问
    private boolean isVisited;

    public Bread_Node(String data) {
        this.data = data;
    }

    public String getData() {
        return data;
    }

    public void setData(String data) {
        this.data = data;
    }

    public boolean isVisited() {
        return isVisited;
    }

    public void setVisited(boolean isVisited) {
        this.isVisited = isVisited;
    }

}

2、建立一个类存储图的数据

//数据源

public class Bread_GraphData {

    // 邻接矩阵
    public int[][] getMatrix() {

        // 1代表有边，0代表无边
        int[][] matrix = { { 0, 1, 0, 1, 0, 0, 0, 0 }, { 1, 0, 1, 0, 0, 1, 0, 0 }, { 0, 1, 0, 0, 1, 0, 0, 0 },
                { 1, 0, 0, 0, 0, 0, 1, 1 }, { 0, 0, 1, 0, 0, 1, 0, 0 }, { 0, 1, 0, 0, 1, 0, 0, 0 },
                { 0, 0, 0, 1, 0, 0, 0, 0 }, { 0, 0, 0, 1, 0, 0, 0, 0 } };

        return matrix;
    }

    // 顶点标签
    public String[] getNodeData() {
        String[] nodeData = { "A", "B", "C", "D", "E", "F", "G", "H" };
        return nodeData;
    }
}

3、图的广度优先遍历算法

//广度优先遍历

import java.util.ArrayList;
import java.util.List;
import java.util.Vector;

public class BreadthFirstTraverse {

    private List<Bread_Node> list = new ArrayList<Bread_Node>();

    private Bread_GraphData gd = new Bread_GraphData();

    // 邻接矩阵
    private int[][] matrix = gd.getMatrix();

    /**
     * 遍历树的过程中，同一层的结点存放到一个数组中，
     * 树有多少层则需要多少个数组来存放
     * @param nodeIndex
     */
    public void breadthFirstTraverse(int nodeIndex) {

        // 所有的顶点数据
        String[] nodeData = gd.getNodeData();

        // 结点列表，存储所有的顶点
        for (String data : nodeData) {
            list.add(new Bread_Node(data));
        }

        // 取得传进来的结点下标对应的结点
        Bread_Node node = list.get(nodeIndex);

        // 打印传进来的结点
        System.out.print(node.getData() + " ");

        // 标记为已访问
        node.setVisited(true);

        // 当前数组，存储这一层已确定的顶点的索引
        Vector<Integer> curVec = new Vector<Integer>();

        // 添加传进来的顶点的索引到当前数组中
        curVec.add(nodeIndex);

        breadthFirstTraverse_Inner(curVec);

    }

    // 传进去的是上一层顶点数组
    private void breadthFirstTraverse_Inner(Vector<Integer> preVec) {

        // 当前这一层的数组
        Vector<Integer> curVec = new Vector<Integer>();

        /**
         * preVec.size()表示上一层的结点个数 下面的for循环一完成，就表示已将preVec的下一层顶点全都访问完了
         */
        for (int i = 0; i < preVec.size(); i++) {
            // 由邻接矩阵判断传进来的上一层数组中的结点与其他结点有无连接
            for (int j = 0; j < matrix.length; j++) {
                // 有边
                if (matrix[preVec.get(i)][j] != 0) {
                    // 若已被访问过
                    if (list.get(j).isVisited()) {
                        continue;
                    } else {
                        // 没有被访问过
                        // 访问该顶点，输出
                        System.out.print(list.get(j).getData() + " ");
                        // 设置该顶点为已被访问
                        list.get(j).setVisited(true);
                        // 将该顶点放入当前这一层的数组中
                        curVec.add(j);
                    }
                }
            }
        }

        // 判断本层是否存在刚被访问过的顶点
        if (curVec.size() == 0) {
            // 若本层无顶点，那下面的层就更不存在了
            return;
        } else {
            breadthFirstTraverse_Inner(curVec);
        }

    }
}

4、测试

//测试类
//广度优先遍历结果：A B D C F G H E 

public class Bread_Test {

    public static void main(String[] args) {
        BreadthFirstTraverse bft = new BreadthFirstTraverse();
        bft.breadthFirstTraverse(0);

    }

}

5、测试结果