溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
存儲結構
要存儲一個圖，我們知道圖既有結點，又有邊，對于有權圖來說，每條邊上還帶有權值。常用的圖的存儲結構主要有以下二種：
鄰接矩陣
鄰接表
鄰接矩陣
我們知道，要表示結點，我們可以用一個一維數組來表示，然而對于結點和結點之間的關系，則無法簡單地用一維數組來表示了，我們可以用二維數組來表示，也就是一個矩陣形式的表示方法。
我們假設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語言描述存儲結構與鄰接矩陣代碼示例的全部內容，希望對大家有所幫助。感興趣的朋友可以繼續參閱本站其他相關專題，如有不足之處，歡迎留言指出。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
