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 = { { , , , , , , ,  }, { , , , , , , ,  }, { , , , , , , ,  },
                { , , , , , , ,  }, { , , , , , , ,  }, { , , , , , , ,  },
                { , , , , , , ,  }, { , , , , , , ,  } };

        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 = ; i < preVec.size(); i++) {
            // 由鄰接矩陣判斷傳進來的上一層數組中的結點與其他結點有無連接配接
            for (int j = ; j < matrix.length; j++) {
                // 有邊
                if (matrix[preVec.get(i)][j] != ) {
                    // 若已被通路過
                    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() == ) {
            // 若本層無頂點，那下面的層就更不存在了
            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();

    }

}
           

5、測試結果