存儲結構
要存儲一個圖，我們知道圖既有結點，又有邊，對於有權圖來說，每條邊上還帶有權值。常用的圖的存儲結構主要有以下二種：
鄰接矩陣鄰接表
鄰接矩陣
我們知道，要表示結點，我們可以用一個一維數組來表示，然而對於結點和結點之間的關係，則無法簡單地用一維數組來表示了，我們可以用二維數組來表示，也就是一個矩陣形式的表示方法。
我們假設A是這個二維數組，那麼A中的一個元素aij不僅體現出了結點vi和結點vj的關係，而且aij的值正可以表示權值的大小。
以下是一個無向圖的鄰接矩陣表示示例：
從上圖我們可以看到，無向圖的鄰接矩陣是對稱矩陣，也一定是對稱矩陣。且其左上角到右下角的對角線上值為零（對角線上表示的是相同的結點）
有向圖的鄰接矩陣是怎樣的呢？
對於帶權圖，aij的值可用來表示權值的大小，上面兩張圖是不帶權的圖，因此它們值都是1。
鄰接表
我們知道，圖的鄰接矩陣存儲方法用的是一個n*n的矩陣，當這個矩陣是稠密的矩陣（比如說當圖是完全圖的時候），那麼當然選擇用鄰接矩陣存儲方法。
可是如果這個矩陣是一個稀疏的矩陣呢，這個時候鄰接表存儲結構就是一種更節省空間的存儲結構了。
對於上文中的無向圖，我們可以用鄰接表來表示，如下：
每一個結點後面所接的結點都是它的鄰接結點。
鄰接矩陣與鄰接表的比較
當圖中結點數目較小且邊較多時，採用鄰接矩陣效率更高。
當節點數目遠大且邊的數目遠小於相同結點的完全圖的邊數時，採用鄰接表存儲結構更有效率。
鄰接矩陣的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()); }}控制台輸出結果如下圖所示：
總結
以上就是本文關於Java語言描述存儲結構與鄰接矩陣代碼示例的全部內容，希望對大家有所幫助。感興趣的朋友可以繼續參閱本站其他相關專題，如有不足之處，歡迎留言指出。