Java編程實(shí)現(xiàn)鄰接矩陣表示稠密圖代碼示例
我們知道,要表示結(jié)點(diǎn),我們可以用一個(gè)一維數(shù)組來(lái)表示,然而對(duì)于結(jié)點(diǎn)和結(jié)點(diǎn)之間的關(guān)系,則無(wú)法簡(jiǎn)單地用一維數(shù)組來(lái)表示了,我們可以用二維數(shù)組來(lái)表示,也就是一個(gè)矩陣形式的表示方法。
我們假設(shè)A是這個(gè)二維數(shù)組,那么A中的一個(gè)元素aij不僅體現(xiàn)出了結(jié)點(diǎn)vi和結(jié)點(diǎn)vj的關(guān)系,而且aij的值正可以表示權(quán)值的大小。
鄰接矩陣模型類
鄰接矩陣模型類的類名為AMWGraph.java,能夠通過(guò)該類構(gòu)造一個(gè)鄰接矩陣表示的圖,且提供插入結(jié)點(diǎn),插入邊,取得某一結(jié)點(diǎn)的第一個(gè)鄰接結(jié)點(diǎn)和下一個(gè)鄰接結(jié)點(diǎn)。
import java.util.ArrayList;
import java.util.LinkedList;
public class AMWGraph {
private ArrayList vertexList;
//存儲(chǔ)點(diǎn)的鏈表
private int[][] edges;
//鄰接矩陣,用來(lái)存儲(chǔ)邊
private int numOfEdges;
//邊的數(shù)目
public AMWGraph(int n) {
//初始化矩陣,一維數(shù)組,和邊的數(shù)目
edges=new int[n][n];
vertexList=new ArrayList(n);
numOfEdges=0;
}
//得到結(jié)點(diǎn)的個(gè)數(shù)
public int getNumOfVertex() {
return vertexList.size();
}
//得到邊的數(shù)目
public int getNumOfEdges() {
return numOfEdges;
}
//返回結(jié)點(diǎn)i的數(shù)據(jù)
public Object getValueByIndex(int i) {
return vertexList.get(i);
}
//返回v1,v2的權(quán)值
public int getWeight(int v1,int v2) {
return edges[v1][v2];
}
//插入結(jié)點(diǎn)
public void insertVertex(Object vertex) {
vertexList.add(vertexList.size(),vertex);
}
//插入結(jié)點(diǎn)
public void insertEdge(int v1,int v2,int weight) {
edges[v1][v2]=weight;
numOfEdges++;
}
//刪除結(jié)點(diǎn)
public void deleteEdge(int v1,int v2) {
edges[v1][v2]=0;
numOfEdges--;
}
//得到第一個(gè)鄰接結(jié)點(diǎn)的下標(biāo)
public int getFirstNeighbor(int index) {
for (int j=0;j<vertexList.size();j++) {
if (edges[index][j]>0) {
return j;
}
}
return -1;
}
//根據(jù)前一個(gè)鄰接結(jié)點(diǎn)的下標(biāo)來(lái)取得下一個(gè)鄰接結(jié)點(diǎn)
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編程實(shí)現(xiàn)鄰接矩陣表示稠密圖代碼:
package com.dataStructure.graph;
//// 稠密圖 - 使用鄰接矩陣表示
//public class DenseGraph {
//
// private int n; // 節(jié)點(diǎn)數(shù)
// private int m; // 邊數(shù)
// private boolean directed; // 是否為有向圖
// private boolean[][] g; // 圖的具體數(shù)據(jù)
//
// // 構(gòu)造函數(shù)
// public DenseGraph(int n, boolean directed) {
// assert n >= 0;
// this.n = n;
// this.m = 0; // 初始化沒(méi)有任何邊
// this.directed = directed;
// // g初始化為n*n的布爾矩陣, 每一個(gè)g[i][j]均為false, 表示沒(méi)有任和邊
// // false為boolean型變量的默認(rèn)值
// g = new boolean[n][n];
// }
//
// public int V() {
// return n;
// } // 返回節(jié)點(diǎn)個(gè)數(shù)
//
// public int E() {
// return m;
// } // 返回邊的個(gè)數(shù)
//
// // 向圖中添加一個(gè)邊
// 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;
//
// // 邊數(shù) ++
// m++;
// }
//
// // 驗(yàn)證圖中是否有從v到w的邊
// boolean hasEdge(int v, int w) {
// assert v >= 0 && v < n;
// assert w >= 0 && w < n;
// return g[v][w];
// }
//
// // 返回圖中一個(gè)頂點(diǎn)的所有鄰邊
// // 由于java使用引用機(jī)制,返回一個(gè)Vector不會(huì)帶來(lái)額外開(kāi)銷,
// 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;
// 圖中的節(jié)點(diǎn)數(shù)
private int m;
// 圖中的邊數(shù)
private Boolean[][] g;
// 鄰接矩陣g
private Boolean directed;
// 是否為有向圖
public DenseGraph(int n, Boolean directed){
this.n = n;
// 初始化圖中的節(jié)點(diǎn)數(shù)量
this.m = 0;
// 圖中邊(edge)的數(shù)量初始化為0
this.directed = directed;
g = new Boolean[n][n];
// 鄰接矩陣 g 初始化為一個(gè) n*n 的二維矩陣
// 索引代表圖中的節(jié)點(diǎn),g中存儲(chǔ)的值為 節(jié)點(diǎn)是否有邊
}
// 返回圖中邊的數(shù)量
public int E(){
return m;
}
// 返回圖中節(jié)點(diǎn)的數(shù)量
public int V(){
return n;
}
// 在圖中指定的兩節(jié)點(diǎn)之間加邊
public void addEdge(int v, int w){
if (!hasEdge(v, w)){
// 連接[v][w]
g[v][w] = true;
// 無(wú)向圖
if (!directed)
g[w][v] = true;
// 圖中邊的數(shù)量+1
m++;
}
}
// 判斷兩節(jié)點(diǎn)之間是否有邊
private Boolean hasEdge(int v, int w){
return g[v][w];
}
// 返回所有 節(jié)點(diǎn) v 的 鄰接節(jié)點(diǎn)
public Iterable<Integer> adjacentNode(int v){
// adjacentL 用于存儲(chǔ) v 的鄰接節(jié)點(diǎn)
List<Integer> adjacentL = new ArrayList<>();
// 找到所有與 v 鄰接的節(jié)點(diǎn),將其加入 adjacentL 中
for (int i = 0; i < n;i++){
if (g[v][i])
adjacentL.add(i);
}
return adjacentL;
}
}
總結(jié)
以上就是本文關(guān)于Java編程實(shí)現(xiàn)鄰接矩陣表示稠密圖代碼示例的全部?jī)?nèi)容,希望對(duì)大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站:
java數(shù)據(jù)結(jié)構(gòu)之樹(shù)基本概念解析及代碼示例
Java常見(jiàn)數(shù)據(jù)結(jié)構(gòu)面試題(帶答案)
多模字符串匹配算法原理及Java實(shí)現(xiàn)代碼
如有不足之處,歡迎留言指出。感謝朋友們對(duì)本站的支持!
- java 矩陣乘法的mapreduce程序?qū)崿F(xiàn)
- java 二維數(shù)組矩陣乘法的實(shí)現(xiàn)方法
- Java矩陣連乘問(wèn)題(動(dòng)態(tài)規(guī)劃)算法實(shí)例分析
- Java實(shí)現(xiàn)的求逆矩陣算法示例
- java實(shí)現(xiàn)任意矩陣Strassen算法
- Java實(shí)現(xiàn)輸出回環(huán)數(shù)(螺旋矩陣)的方法示例
- Java實(shí)現(xiàn)矩陣加減乘除及轉(zhuǎn)制等運(yùn)算功能示例
- Java編程實(shí)現(xiàn)打印螺旋矩陣實(shí)例代碼
- Java編程數(shù)組中最大子矩陣簡(jiǎn)便解法實(shí)現(xiàn)代碼
- Java實(shí)現(xiàn)的計(jì)算稀疏矩陣余弦相似度示例
- Java實(shí)現(xiàn)的矩陣乘法示例
相關(guān)文章
springmvc 中dao層和service層的區(qū)別說(shuō)明
這篇文章主要介紹了springmvc 中dao層和service層的區(qū)別說(shuō)明,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2021-08-08Springboot中如何自定義監(jiān)聽(tīng)器
這篇文章主要介紹了Springboot中自定義監(jiān)聽(tīng)器,自定義事件需要繼承ApplicationEvent類,并添加一個(gè)構(gòu)造函數(shù),用于接收事件源對(duì)象,本文通過(guò)示例代碼給大家介紹的非常詳細(xì),感興趣的朋友一起看看吧2024-07-07Java如何替換RequestBody和RequestParam參數(shù)的屬性
近期由于接手的老項(xiàng)目中存在所有接口中新增一個(gè)加密串來(lái)給接口做一個(gè)加密效果,所以就研究了一下Http請(qǐng)求鏈路,發(fā)現(xiàn)可以通過(guò)?javax.servlet.Filter去實(shí)現(xiàn),這篇文章主要介紹了Java替換RequestBody和RequestParam參數(shù)的屬性,需要的朋友可以參考下2023-10-10利用Spring boot如何創(chuàng)建簡(jiǎn)單的web交互應(yīng)用
這篇文章主要介紹了利用Spring boot如何創(chuàng)建簡(jiǎn)單的web交互應(yīng)用的相關(guān)資料,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家具有一定的參考價(jià)值,需要的朋友們下面來(lái)一起看看吧。2017-04-04Java連接SQL?Server數(shù)據(jù)庫(kù)的超詳細(xì)教程
在Java應(yīng)用程序中我們經(jīng)常需要與數(shù)據(jù)庫(kù)進(jìn)行交互,一種常見(jiàn)的數(shù)據(jù)庫(kù)是Microsoft?SQL?Server,下面這篇文章主要給大家介紹了關(guān)于Java連接SQL?Server數(shù)據(jù)庫(kù)的超詳細(xì)教程,需要的朋友可以參考下2024-01-01淺析java中 Spring MVC 攔截器作用及其實(shí)現(xiàn)
本篇文章主要介紹了java中SpringMVC 攔截器的使用及其實(shí)例,需要的朋友可以參考2017-04-04使用Java實(shí)現(xiàn)簡(jiǎn)單串口通信
這篇文章主要介紹了使用Java實(shí)現(xiàn)簡(jiǎn)單串口通信,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-07-07Spring cloud 查詢返回廣告創(chuàng)意實(shí)例代碼
在本篇文章里小編給大家整理的是關(guān)于Spring cloud 查詢返回廣告創(chuàng)意實(shí)例代碼,需要的朋友們可以跟著學(xué)習(xí)下。2019-08-08