圖的入門實作——鄰接矩陣實作

要求: 代碼實作如下圖結構

使用臨界矩陣效果如下：

思路分析

1. 存儲頂點String 使用 ArrayList
2. 儲存矩陣 int[][] edges

代碼實作：

public class Graph {
    public static void main(String[] args) {
        // 測試圖是否建立
        int n = 5;
        String[] vertexValue= {"A","B","C","D","E"};
        // 建立圖對象
        Graph graph = new Graph(n);
        for (String value : vertexValue) {
            graph.insertVertex(value);
        }
        // 添加邊A-B
        graph.insertEdge(0,1,1);
        // 添加邊A-C
        graph.insertEdge(0,2,1);
        // 添加邊B-C
        graph.insertEdge(1,2,1);
        // 添加邊B-D
        graph.insertEdge(1,3,1);
        // 添加邊B-E
        graph.insertEdge(1,4,1);


        graph.showGraph();
    }
    /**
     * 存儲頂點的集合
      */
    private ArrayList<String> vertexList;

    /**
     * 存儲圖對應的相鄰矩陣
     */
    private int[][] edges;

    /**
     * 表示邊的數目
     */
    private int numOfEdges;

    /**
     * 圖的類的構造器
     * @param n 表示頂點的個數
     */
    public Graph(int n){
        // 初始化矩陣和vertexList
        edges = new int[n][n];
        vertexList = new ArrayList<String>(n);
        // 初始化邊的數目為0
        numOfEdges = 0;
    }

    /**
     * 擷取目前圖中結點的個數
     * @return
     */
    public int getNumOfVertex(){
        return vertexList.size();
    }

    /**
     * 擷取目前圖中邊的個數
     * @return
     */
    public int getNumOfEdges(){
        return numOfEdges;
    }


    /**
     * 根據索引傳回對應的頂點資料
     * @param i
     * @return
     */
    public String getValueByIndex(int i){
        return vertexList.get(i);
    }

    /**
     * 傳回對應下标中的邊的權值
     * @param v1
     * @param v2
     * @return
     */
    public int getWeight(int v1,int v2){
        return edges[v1][v2];
    }


    /**
     * 顯示目前矩陣
     */
    public void showGraph(){
        for (int[] link : edges) {
            System.out.println(Arrays.toString(link));
        }

    }

    /**
     * 添加結點的方法
     * @param vertex
     */
    public void insertVertex(String vertex){
        vertexList.add(vertex);
    }


    /**
     * 添加邊的方法，将邊使用二維數組表示
     * @param v1 頂點1對應的下标
     * @param v2 頂點2對應的下标
     * @param weight 權值：如果頂點1和頂點2之間存在邊，那麼權值為1，反之為0
     */
    public void insertEdge(int v1,int v2,int weight){
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        // 邊的數量+1
        numOfEdges++;
    }


}