您好,登錄后才能下訂單哦!
這篇“Java如何用鄰接矩陣存儲(chǔ)圖”文章的知識(shí)點(diǎn)大部分人都不太理解,所以小編給大家總結(jié)了以下內(nèi)容,內(nèi)容詳細(xì),步驟清晰,具有一定的借鑒價(jià)值,希望大家閱讀完這篇文章能有所收獲,下面我們一起來看看這篇“Java如何用鄰接矩陣存儲(chǔ)圖”文章吧。
鄰接矩陣通常采用一個(gè)一維數(shù)組存儲(chǔ)圖中節(jié)點(diǎn)的信息,采用一個(gè)二維數(shù)組存儲(chǔ)圖中節(jié)點(diǎn)之間的鄰接關(guān)系。
鄰接矩陣可以用來表示無向圖、有向圖和網(wǎng)。
在無向圖中,若從節(jié)點(diǎn) Vi 到節(jié)點(diǎn) Vj 有邊,則鄰接矩陣 M[i][j] = M[j][i ]= 1,否則 M[i][j] = 0。
無向圖的鄰接矩陣的特定如下。
a 無向圖的鄰接矩陣是對稱矩陣,并且是唯一的。
b 第 I 行或第 i 列非零的個(gè)數(shù)正好是第 i 個(gè)節(jié)點(diǎn)的度。
在有向圖中,若從節(jié)點(diǎn) Vi 到節(jié)點(diǎn) Vj 有邊,則鄰接矩陣 M[i][j]=1,否則 M[i][j]=0 。
有向圖的鄰接矩陣的特定如下。
a 有向圖的鄰接矩陣不一定是對稱的。
b 第 i 行非零元素的個(gè)數(shù)正好是第 i 個(gè)節(jié)點(diǎn)的出度,第 i 列非零元素的個(gè)數(shù)正好是第 i 個(gè)節(jié)點(diǎn)的入度。
網(wǎng)是帶權(quán)圖,需要存儲(chǔ)邊的權(quán)值,則鄰接矩陣表示為:M[i][j] = Wij,其他情況為無窮大。
1 輸入節(jié)點(diǎn)數(shù)和邊數(shù)。
2 依次輸入節(jié)點(diǎn)信息,將其存儲(chǔ)到節(jié)點(diǎn)數(shù)組 Vex[] 中。
3 初始化鄰接矩陣,如果是圖,則將其初始化為0,如果是網(wǎng),則將其初始化為無窮大。
4 依次輸入每條邊依附的兩個(gè)節(jié)點(diǎn),如果是網(wǎng),則還需要輸入該邊的權(quán)值。
如果是無向圖,則輸入a,b,查詢節(jié)點(diǎn)a、b在節(jié)點(diǎn)數(shù)組 Vex[] 中的存儲(chǔ)下標(biāo) i、j,讓 Edge[i][j]=Edge[j][i]=1。
如果是有向圖,則輸入a,b,查詢節(jié)點(diǎn)a、b在節(jié)點(diǎn)數(shù)組 Vex[] 中的存儲(chǔ)下標(biāo) i、j,讓 Edge[i][j]=1。
如果是無向網(wǎng),則輸入a,b,w,查詢節(jié)點(diǎn)a、b在節(jié)點(diǎn)數(shù)組 Vex[] 中的存儲(chǔ)下標(biāo) i、j,讓 Edge[i][j]=Edge[j][i]=w。
如果是有向網(wǎng),則輸入a,b,w,查詢節(jié)點(diǎn)a、b在節(jié)點(diǎn)數(shù)組 Vex[] 中的存儲(chǔ)下標(biāo) i、j,讓 Edge[i][j]=w。
package graph; import java.util.Scanner; public class CreateAMGraph { static final int MaxVnum = 100; // 頂點(diǎn)數(shù)最大值 static int locatevex(AMGraph G, char x) { for (int i = 0; i < G.vexnum; i++) // 查找頂點(diǎn)信息的下標(biāo) if (x == G.Vex[i]) return i; return -1; // 沒找到 } static void CreateAMGraph(AMGraph G) { Scanner scanner = new Scanner(System.in); int i, j; char u, v; System.out.println("請輸入頂點(diǎn)數(shù):"); G.vexnum = scanner.nextInt(); System.out.println("請輸入邊數(shù):"); G.edgenum = scanner.nextInt(); System.out.println("請輸入頂點(diǎn)信息:"); // 輸入頂點(diǎn)信息,存入頂點(diǎn)信息數(shù)組 for (int k = 0; k < G.vexnum; k++) { G.Vex[k] = scanner.next().charAt(0); } //初始化鄰接矩陣所有值為0,如果是網(wǎng),則初始化鄰接矩陣為無窮大 for (int m = 0; m < G.vexnum; m++) for (int n = 0; n < G.vexnum; n++) G.Edge[m][n] = 0; System.out.println("請輸入每條邊依附的兩個(gè)頂點(diǎn):"); while (G.edgenum-- > 0) { u = scanner.next().charAt(0); v = scanner.next().charAt(0); i = locatevex(G, u);// 查找頂點(diǎn) u 的存儲(chǔ)下標(biāo) j = locatevex(G, v);// 查找頂點(diǎn) v 的存儲(chǔ)下標(biāo) if (i != -1 && j != -1) G.Edge[i][j] = G.Edge[j][i] = 1; //鄰接矩陣儲(chǔ)置1 else { System.out.println("輸入頂點(diǎn)信息錯(cuò)!請重新輸入!"); G.edgenum++; // 本次輸入不算 } } } static void print(AMGraph G) { // 輸出鄰接矩陣 System.out.println("圖的鄰接矩陣為:"); for (int i = 0; i < G.vexnum; i++) { for (int j = 0; j < G.vexnum; j++) System.out.print(G.Edge[i][j] + "\t"); System.out.println(); } } public static void main(String[] args) { AMGraph G = new AMGraph(); CreateAMGraph(G); print(G); } } class AMGraph { char Vex[] = new char[CreateAMGraph.MaxVnum]; int Edge[][] = new int[CreateAMGraph.MaxVnum][CreateAMGraph.MaxVnum]; int vexnum; // 頂點(diǎn)數(shù) int edgenum; // 邊數(shù) }
綠色為輸入,白色為輸出。
以上就是關(guān)于“Java如何用鄰接矩陣存儲(chǔ)圖”這篇文章的內(nèi)容,相信大家都有了一定的了解,希望小編分享的內(nèi)容對大家有幫助,若想了解更多相關(guān)的知識(shí)內(nèi)容,請關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。