我們知道，要表示結點，我們可以用一個一維數組來表示，然而對於結點和結點之間的關係，則無法簡單地用一維數組來表示了，我們可以用二維數組來表示，也就是一個矩陣形式的表示方法。
我們假設A是這個二維數組，那麼A中的一個元素aij不僅體現出了結點vi和結點vj的關係，而且aij的值正可以表示權值的大小。
鄰接矩陣模型類
鄰接矩陣模型類的類名為AMWGraph.java，能夠通過該類構造一個鄰接矩陣表示的圖，且提供插入結點，插入邊，取得某一結點的第一個鄰接結點和下一個鄰接結點。
import java.util.ArrayList;
import java.util.LinkedList;
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;
}
}下面再看看java編程實現鄰接矩陣表示稠密圖代碼：
package com.dataStructure.graph;
//// 稠密圖- 使用鄰接矩陣表示
//public class DenseGraph {
//
// private int n; // 節點數
// private int m; // 邊數
// private boolean directed; // 是否為有向圖
// private boolean[][] g; // 圖的具體數據
//
// // 構造函數
// public DenseGraph(int n, boolean directed) {
// assert n >= 0;
// this.n = n;
// this.m = 0; // 初始化沒有任何邊
// this.directed = directed;
// // g初始化為n*n的布爾矩陣, 每一個g[i][j]均為false, 表示沒有任和邊
// // false為boolean型變量的默認值
// g = new boolean[n][n];
// }
//
// public int V() {
// return n;
// } // 返回節點個數
//
// public int E() {
// return m;
// } // 返回邊的個數
//
// // 向圖中添加一個邊
// public void addEdge(int v, int w) {
//
// assert v >= 0 && v < n;
// assert w >= 0 && w < n;
//
// if (hasEdge(v, w))
// return;
//
// // 連接v 和w
// g[v][w] = true;
// if (!directed)
// g[w][v] = true;
//
// // 邊數++
// m++;
// }
//
// // 驗證圖中是否有從v到w的邊
// boolean hasEdge(int v, int w) {
// assert v >= 0 && v < n;
// assert w >= 0 && w < n;
// return g[v][w];
// }
//
// // 返回圖中一個頂點的所有鄰邊
// // 由於java使用引用機制，返回一個Vector不會帶來額外開銷,
// public Iterable<Integer> adj(int v) {
// assert v >= 0 && v < n;
// Vector<Integer> adjV = new Vector<Integer>();
// for(int i = 0 ; i < n ; i ++ )
// if( g[v][i] )
// adjV.add(i);
// return adjV;
// }
//}
import java.util.ArrayList;
import java.util.List;
// 使用鄰接矩陣表示稠密圖
public class DenseGraph{
private int n;
// 圖中的節點數
private int m;
// 圖中的邊數
private Boolean[][] g;
// 鄰接矩陣g
private Boolean directed;
// 是否為有向圖
public DenseGraph(int n, Boolean directed){
this.n = n;
// 初始化圖中的節點數量
this.m = 0;
// 圖中邊（edge）的數量初始化為0
this.directed = directed;
g = new Boolean[n][n];
// 鄰接矩陣g 初始化為一個n*n 的二維矩陣
// 索引代表圖中的節點，g中存儲的值為節點是否有邊
}
// 返回圖中邊的數量
public int E(){
return m;
}
// 返回圖中節點的數量
public int V(){
return n;
}
// 在圖中指定的兩節點之間加邊
public void addEdge(int v, int w){
if (!hasEdge(v, w)){
// 連接[v][w]
g[v][w] = true;
// 無向圖
if (!directed)
g[w][v] = true;
// 圖中邊的數量+1
m++;
}
}
// 判斷兩節點之間是否有邊
private Boolean hasEdge(int v, int w){
return g[v][w];
}
// 返回所有節點v 的鄰接節點
public Iterable<Integer> adjacentNode(int v){
// adjacentL 用於存儲v 的鄰接節點
List<Integer> adjacentL = new ArrayList<>();
// 找到所有與v 鄰接的節點，將其加入adjacentL 中
for (int i = 0; i < n;i++){
if (g[v][i])
adjacentL.add(i);
}
return adjacentL;
}
}
總結
以上就是本文關於Java編程實現鄰接矩陣表示稠密圖代碼示例的全部內容，希望對大家有所幫助。感興趣的朋友可以繼續參閱本站：
java數據結構之樹基本概念解析及代碼示例
Java常見數據結構面試題（帶答案）
多模字符串匹配算法原理及Java實現代碼
如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！