Java數據結構之圖的領接矩陣詳解

Posted on by

1.圖的領接矩陣（Adjacency Matrix）存儲結構

圖的領接矩陣（Adjacency Matrix）存儲方式是用兩個數組來表示圖。一個一位數組存儲圖中頂點信息，一個二維數組（稱為領接矩陣）存儲圖中的邊或弧的信息。

舉例

無向圖

無向圖的領接矩陣的第i行或第i列的非零元素個數正好是第i個頂點的度。

有向圖

有向圖的領接矩陣的第i行的非零元素個數正好是第i個頂點的出度，第i列的非零元素個數正好是第i個頂點的入度。

帶權值的網圖

2.圖的接口類

3.圖的類型，用枚舉類表示

public enum GraphKind {
    UDG,DG,UDN,DN;//無向圖、有向圖、無向網、有向網
}

4.圖的領接矩陣描述

對於一個具有n個頂點的圖G，可以將圖G的領接矩陣存儲在一個二維數組中.

package Graph;
/*
    圖的領接矩陣描述類
 */
import java.util.Scanner;
 
public class MyGraph implements IGraph {
    public final static int INFINITY = Integer.MAX_VALUE;
    private GraphKind kind;             //圖的標志
    private int vexNum, arcNum;          //圖當前頂點和邊數
    private Object[] vexs;              //頂點
    private int[][] arcs;               //鄰接矩陣
 
    public MyGraph() {                  //空參構造
        this(null, 0, 0, null, null);
    }
 
    public MyGraph(GraphKind kind, int vexNum, int arcNum, Object[] vexs, int[][] arcs) {   // 實參構造
        this.kind = kind;
        this.vexNum = vexNum;
        this.arcNum = arcNum;
        this.vexs = vexs;
        this.arcs = arcs;
    }
 
    @Override
    public void createGraph() {               //創建新圖
        Scanner sc = new Scanner(System.in);
        System.out.println("請輸入圖的類型：");
        GraphKind kind = GraphKind.valueOf(sc.next());
        switch (kind) {
            case UDG:
                createUDG();
                return;
            case DG:
                createDG();
                return;
            case UDN:
                createUDG();
                return;
            case DN:
                createDN();
                return;
 
        }
    }
 
    private void createUDG() {       //創建無向圖
        Scanner sc = new Scanner(System.in);
        System.out.println("請輸入圖的頂點數、圖的邊數：");
        vexNum = sc.nextInt();
        arcNum = sc.nextInt();
        vexs = new Object[vexNum];
        System.out.println("請分別輸入圖的各個頂點");
        for (int v = 0; v < vexNum; v++)                //構造頂點函數
            vexs[v] = sc.next();
        arcs = new int[vexNum][vexNum];
        for (int v = 0; v < vexNum; v++)
            for (int u = 0; u < vexNum; u++)
                arcs[v][u] = INFINITY;              //初始化領接矩陣
        System.out.println("請輸入各個邊的兩個頂點及其權值：");
        for (int k = 0; k < arcNum; k++) {
            int v = locateVex(sc.next());
            int u = locateVex(sc.next());
            arcs[v][u] = arcs[v][u] = sc.nextInt();
        }
    }
    private void createDG() {       //創建有向圖
    }
    ;
 
    private void createUDN() {       //創建無向網
 
    }
    private void createDN() {           //創建有向網
        Scanner sc = new Scanner(System.in);
        System.out.println("請輸入圖的頂點數、圖的邊數：");
        vexNum = sc.nextInt();
        arcNum = sc.nextInt();
        vexs = new Object[vexNum];
        System.out.println("請分別輸入圖的各個頂點");
        for (int v = 0; v < vexNum; v++)                //構造頂點函數
            vexs[v] = sc.next();
        arcs = new int[vexNum][vexNum];
        for (int v = 0; v < vexNum; v++)
            for (int u = 0; u < vexNum; u++)
                arcs[v][u] = INFINITY;              //初始化領接矩陣
        System.out.println("請輸入各個邊的兩個頂點及其權值：");
        for (int k = 0; k < arcNum; k++) {
            int v = locateVex(sc.next());
            int u = locateVex(sc.next());
            arcs[v][u] = sc.nextInt();
        }
    }
    @Override
    public int getVexNum() {
        return vexNum;   //返回頂點數
    }
 
    @Override
    public int getArcNum() {
        return arcNum;      //返回邊數
    }
 
    @Override              //返回v的第一個領接點，若v沒有領接點返回-1;
    public Object getVex(int v) throws Exception {
        if (v < 0 && v >= vexNum)
            throw new Exception("第" + v + "個頂點不存在！");
        return vexs[v];
          <0v<vexNum
    }
 
    @Override
    public int locateVex(Object vex) {          //頂點定位法
 
        for (int v = 0; v < vexNum; v++)
            if (vexs[v].equals(vex))
                return v;
        return 0;
    }
 
    @Override                            
    public int firstAdjVex(int v) throws Exception {   //查找第一個領接點
        if (v < 0 && v >= vexNum)
            throw new Exception("第" + v + "個頂點不存在！");
        for (int j = 0; j < vexNum; j++)
            if (arcs[v][j] != 0 && arcs[v][j] < INFINITY)
                return j;
                return -1;
    }
 
    
    @Override
    public int nextAdjvex(int v, int w) {         //查找下一個領接點
        return 0;
    }
    public GraphKind getKind(){                   //返回圖標類型
        return kind;
    }
 
  
    public int[][] getArcs() {              //返回鄰接矩陣的值
        return arcs;
    }
 
                                            //返回頂點
    public Object[] getVexs() {
        return vexs;
    }
}

測試類

    public static void main(String[] args) throws Exception {
        MyGraph M=new MyGraph();                                //創建圖空間
        M.createGraph();
        System.out.println("創建無向網的頂點個數為："+M.getVexNum());
        System.out.println("創建無向網的邊個數為："+M.getArcNum());
        System.out.println("請輸入要查找頂點的值：");
        Scanner sc=new Scanner(System.in);                  
        Object top=sc.next();
        System.out.println("要查找頂點"+top+"的值為："+ M.locateVex(top));
        System.out.println("請輸入要查找頂點的索引：");
        int x= sc.nextInt();
        System.out.println("要查找位置"+x+"處的頂點值為："+M.getVex(x) );
        System.out.println("請輸入鄰接點的頂點的位置：");
        int n= sc.nextInt();
        System.out.println("要查找位置"+n+"處的頂點值為："+M.firstAdjVex(n) );
    }
}

結果

以上就是Java數據結構之圖的領接矩陣詳解的詳細內容，更多關於Java數據結構資料請關註WalkonNet其它相關文章！

推薦閱讀：