Java語言描述存儲結構與鄰接矩陣代碼示例

更新時間：2017年11月29日 14:14:53 作者：beanlam

這篇文章主要介紹了Java語言描述存儲結構與鄰接矩陣代碼示例，涉及Java存儲結構，鄰接矩陣，鄰接表的介紹與比較，然后分享了鄰接矩陣的Java實現等相關內容，具有一定借鑒價值，需要的朋友可以參考。

存儲結構

要存儲一個圖，我們知道圖既有結點，又有邊，對于有權圖來說，每條邊上還帶有權值。常用的圖的存儲結構主要有以下二種：

鄰接矩陣
鄰接表

鄰接矩陣

我們知道，要表示結點，我們可以用一個一維數組來表示，然而對于結點和結點之間的關系，則無法簡單地用一維數組來表示了，我們可以用二維數組來表示，也就是一個矩陣形式的表示方法。

我們假設A是這個二維數組，那么A中的一個元素aij不僅體現出了結點vi和結點vj的關系，而且aij的值正可以表示權值的大小。

以下是一個無向圖的鄰接矩陣表示示例：

從上圖我們可以看到，無向圖的鄰接矩陣是對稱矩陣，也一定是對稱矩陣。且其左上角到右下角的對角線上值為零（對角線上表示的是相同的結點）

有向圖的鄰接矩陣是怎樣的呢？

對于帶權圖，aij的值可用來表示權值的大小，上面兩張圖是不帶權的圖，因此它們值都是1。

鄰接表

我們知道，圖的鄰接矩陣存儲方法用的是一個n*n的矩陣，當這個矩陣是稠密的矩陣（比如說當圖是完全圖的時候），那么當然選擇用鄰接矩陣存儲方法。

可是如果這個矩陣是一個稀疏的矩陣呢，這個時候鄰接表存儲結構就是一種更節(jié)省空間的存儲結構了。

對于上文中的無向圖，我們可以用鄰接表來表示，如下：

每一個結點后面所接的結點都是它的鄰接結點。

鄰接矩陣與鄰接表的比較

當圖中結點數目較小且邊較多時，采用鄰接矩陣效率更高。
當節(jié)點數目遠大且邊的數目遠小于相同結點的完全圖的邊數時，采用鄰接表存儲結構更有效率。

鄰接矩陣的Java實現

鄰接矩陣模型類

鄰接矩陣模型類的類名為AMWGraph.java，能夠通過該類構造一個鄰接矩陣表示的圖，且提供插入結點，插入邊，取得某一結點的第一個鄰接結點和下一個鄰接結點。

import java.util.ArrayList;
import java.util.LinkedList;
/**
 * @description 鄰接矩陣模型類
 * @author beanlam
 * @time 2015.4.17 
 */
public class AMWGraph {
  private ArrayList vertexList;//存儲點的鏈表
  private int[][] edges;//鄰接矩陣，用來存儲邊
  private int numOfEdges;//邊的數目

  public AMWGraph(int n) {
    //初始化矩陣，一維數組，和邊的數目
    edges=new int[n][n];
    vertexList=new ArrayList(n);
    numOfEdges=0;
  }

  //得到結點的個數
  public int getNumOfVertex() {
    return vertexList.size();
  }

  //得到邊的數目
  public int getNumOfEdges() {
    return numOfEdges;
  }

  //返回結點i的數據
  public Object getValueByIndex(int i) {
    return vertexList.get(i);
  }

  //返回v1,v2的權值
  public int getWeight(int v1,int v2) {
    return edges[v1][v2];
  }

  //插入結點
  public void insertVertex(Object vertex) {
    vertexList.add(vertexList.size(),vertex);
  }

  //插入結點
  public void insertEdge(int v1,int v2,int weight) {
    edges[v1][v2]=weight;
    numOfEdges++;
  }

  //刪除結點
  public void deleteEdge(int v1,int v2) {
    edges[v1][v2]=0;
    numOfEdges--;
  }

  //得到第一個鄰接結點的下標
  public int getFirstNeighbor(int index) {
    for(int j=0;j<vertexList.size();j++) {
      if (edges[index][j]>0) {
        return j;
      }
    }
    return -1;
  }

  //根據前一個鄰接結點的下標來取得下一個鄰接結點
  public int getNextNeighbor(int v1,int v2) {
    for (int j=v2+1;j<vertexList.size();j++) {
      if (edges[v1][j]>0) {
        return j;
      }
    }
    return -1;
  }
}

鄰接矩陣模型類的測試

接下來根據下面一個有向圖來設置測試該模型類

TestAMWGraph.java測試程序如下所示：

/**
 * @description AMWGraph類的測試類
 * @author beanlam
 * @time 2015.4.17
 */
public class TestAMWGraph {
  public static void main(String args[]) {
    int n=4,e=4;//分別代表結點個數和邊的數目
    String labels[]={"V1","V1","V3","V4"};//結點的標識
    AMWGraph graph=new AMWGraph(n);
    for(String label:labels) {
      graph.insertVertex(label);//插入結點
    }
    //插入四條邊
    graph.insertEdge(0, 1, 2);
    graph.insertEdge(0, 2, 5);
    graph.insertEdge(2, 3, 8);
    graph.insertEdge(3, 0, 7);

    System.out.println("結點個數是："+graph.getNumOfVertex());
    System.out.println("邊的個數是："+graph.getNumOfEdges());

    graph.deleteEdge(0, 1);//刪除<V1,V2>邊
    System.out.println("刪除<V1,V2>邊后...");
    System.out.println("結點個數是："+graph.getNumOfVertex());
    System.out.println("邊的個數是："+graph.getNumOfEdges());
  }
}

控制臺輸出結果如下圖所示：