鄰接表無向圖的Java語言實現完整源碼

鄰接表無向圖的介紹

鄰接表無向圖是指通過鄰接表表示的無向圖。

上面的圖G1包含了”A,B,C,D,E,F,G”共7個頂點，而且包含了”(A,C),(A,D),(A,F),(B,C),(C,D),(E,G),(F,G)”共7條邊。

上圖右邊的矩陣是G1在內存中的鄰接表示意圖。每一個頂點都包含一條鍊錶，該鍊錶記錄了”該頂點的鄰接點的序號”。例如，第2個頂點(頂點C)包含的鍊錶所包含的節點的數據分別是”0,1,3”；而這”0,1,3”分別對應”A,B,D”的序號，”A,B,D”都是C的鄰接點。就是通過這種方式記錄圖的信息的。

鄰接表無向圖的代碼說明

1. 基本定義

public class ListUDG {// 鄰接表中表對應的鍊錶的頂點private class ENode {int ivex;// 該邊所指向的頂點的位置ENode nextEdge;// 指向下一條弧的指針}// 鄰接表中表的頂點private class VNode {char data;// 頂點信息ENode firstEdge;// 指向第一條依附該頂點的弧};private VNode[] mVexs;// 頂點數組...}

(01)ListUDG是鄰接表對應的結構體。 mVexs則是保存頂點信息的一維數組。

(02)VNode是鄰接表頂點對應的結構體。 data是頂點所包含的數據，而firstEdge是該頂點所包含鍊錶的表頭指針。

(03)ENode是鄰接表頂點所包含的鍊錶的節點對應的結構體。 ivex是該節點所對應的頂點在vexs中的索引，而nextEdge是指向下一個節點的。

2.創建矩陣

這裡介紹提供了兩個創建矩陣的方法。一個是用已知數據，另一個則需要用戶手動輸入數據。

2.1創建圖(用已提供的矩陣)

 /* * 創建圖(用已提供的矩陣) * * 參數說明： * vexs -- 頂點數組* edges -- 邊數組*/public ListUDG(char[] vexs, char[][] edges) {// 初始化"頂點數"和"邊數"int vlen = vexs.length;int elen = edges.length;// 初始化"頂點"mVexs = new VNode[vlen];for (int i = 0; i < mVexs.length; i++) {mVexs[i] = new VNode();mVexs[i].data = vexs[i];mVexs[i].firstEdge = null;}// 初始化"邊"for (int i = 0; i < elen; i++) {// 讀取邊的起始頂點和結束頂點char c1 = edges[i][0];char c2 = edges[i][1];// 讀取邊的起始頂點和結束頂點int p1 = getPosition(edges[i][0]);int p2 = getPosition(edges[i][1]);// 初始化node1ENode node1 = new ENode();node1.ivex = p2;// 將node1鏈接到"p1所在鍊錶的末尾"if(mVexs[p1].firstEdge == null) mVexs[p1].firstEdge = node1; else linkLast(mVexs[p1].firstEdge, node1);// 初始化node2ENode node2 = new ENode();node2.ivex = p1;// 將node2鏈接到"p2所在鍊錶的末尾"if(mVexs[p2].firstEdge == null) mVexs[p2].firstEdge = node2; else linkLast(mVexs[p2].firstEdge, node2);}}

該函數的作用是創建一個鄰接表無向圖。實際上，該方法創建的無向圖，就是上面圖G1。調用代碼如下：

 char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};char[][] edges = new char[][]{ {'A', 'C'}, {'A', 'D'}, {'A', 'F'}, {'B', 'C'}, {'C', 'D'}, {'E', 'G'}, {'F', 'G'}};ListUDG pG;pG = new ListUDG(vexs, edges);

2.2 創建圖(自己輸入)

 /* * 創建圖(自己輸入數據) */public ListUDG() {// 輸入"頂點數"和"邊數"System.out.printf("input vertex number: ");int vlen = readint();System.out.printf("input edge number: ");int elen = readint();if ( vlen < 1 || elen < 1 || (elen > (vlen*(vlen - 1)))) {System.out.printf("input error: invalid parameters!/n");return ;}// 初始化"頂點"mVexs = new VNode[vlen];for (int i = 0; i < mVexs.length; i++) {System.out.printf("vertex(%d): ", i);mVexs[i] = new VNode();mVexs[i].data = readchar();mVexs[i].firstEdge = null;}// 初始化"邊"//mMatrix = new int[vlen][vlen];for (int i = 0; i < elen; i++) {// 讀取邊的起始頂點和結束頂點System.out.printf("edge(%d):", i);char c1 = readchar();char c2 = readchar();int p1 = getPosition(c1);int p2 = getPosition(c2);// 初始化node1ENode node1 = new ENode();node1.ivex = p2;// 將node1鏈接到"p1所在鍊錶的末尾"if(mVexs[p1].firstEdge == null) mVexs[p1].firstEdge = node1; else linkLast(mVexs[p1].firstEdge, node1);// 初始化node2ENode node2 = new ENode();node2.ivex = p1;// 將node2鏈接到"p2所在鍊錶的末尾"if(mVexs[p2].firstEdge == null) mVexs[p2].firstEdge = node2; else linkLast(mVexs[p2].firstEdge, node2);}}

該函數是讀取用戶的輸入，將輸入的數據轉換成對應的無向圖。

鄰接表無向圖的完整源碼

import java.io.IOException;import java.util.Scanner;public class ListUDG {// 鄰接表中表對應的鍊錶的頂點private class ENode {int ivex;// 該邊所指向的頂點的位置ENode nextEdge;// 指向下一條弧的指針}// 鄰接表中表的頂點private class VNode {char data;// 頂點信息ENode firstEdge;// 指向第一條依附該頂點的弧};private VNode[] mVexs;// 頂點數組/* * 創建圖(自己輸入數據) */public ListUDG() {// 輸入"頂點數"和"邊數"System.out.printf("input vertex number: ");int vlen = readint();System.out.printf("input edge number: ");int elen = readint();if ( vlen < 1 || elen < 1 || (elen > (vlen*(vlen - 1)))) {System.out.printf("input error: invalid parameters!/n");return ;}// 初始化"頂點"mVexs = new VNode[vlen];for (int i = 0; i < mVexs.length; i++) {System.out.printf("vertex(%d): ", i);mVexs[i] = new VNode();mVexs[i].data = readchar();mVexs[i].firstEdge = null;}// 初始化"邊"//mMatrix = new int[vlen][vlen];for (int i = 0; i < elen; i++) {// 讀取邊的起始頂點和結束頂點System.out.printf("edge(%d):", i);char c1 = readchar();char c2 = readchar();int p1 = getPosition(c1);int p2 = getPosition(c2);// 初始化node1ENode node1 = new ENode();node1.ivex = p2;// 將node1鏈接到"p1所在鍊錶的末尾"if(mVexs[p1].firstEdge == null) mVexs[p1].firstEdge = node1; else linkLast(mVexs[p1].firstEdge, node1);// 初始化node2ENode node2 = new ENode();node2.ivex = p1;// 將node2鏈接到"p2所在鍊錶的末尾"if(mVexs[p2].firstEdge == null) mVexs[p2].firstEdge = node2; else linkLast(mVexs[p2].firstEdge, node2);}}/* * 創建圖(用已提供的矩陣) * * 參數說明： * vexs -- 頂點數組* edges -- 邊數組*/public ListUDG(char[] vexs, char[][] edges) {// 初始化"頂點數"和"邊數"int vlen = vexs.length;int elen = edges.length;// 初始化"頂點"mVexs = new VNode[vlen];for (int i = 0; i < mVexs.length; i++) {mVexs[i] = new VNode();mVexs[i].data = vexs[i];mVexs[i].firstEdge = null;}// 初始化"邊"for (int i = 0; i < elen; i++) {// 讀取邊的起始頂點和結束頂點char c1 = edges[i][0];char c2 = edges[i][1];// 讀取邊的起始頂點和結束頂點int p1 = getPosition(edges[i][0]);int p2 = getPosition(edges[i][1]);// 初始化node1ENode node1 = new ENode();node1.ivex = p2;// 將node1鏈接到"p1所在鍊錶的末尾"if(mVexs[p1].firstEdge == null) mVexs[p1].firstEdge = node1; else linkLast(mVexs[p1].firstEdge, node1);// 初始化node2ENode node2 = new ENode();node2.ivex = p1;// 將node2鏈接到"p2所在鍊錶的末尾"if(mVexs[p2].firstEdge == null) mVexs[p2].firstEdge = node2; else linkLast(mVexs[p2].firstEdge, node2);}}/* * 將node節點鏈接到list的最後*/private void linkLast(ENode list, ENode node) {ENode p = list;while(p.nextEdge!=null) p = p.nextEdge;p.nextEdge = node;}/* * 返回ch位置*/private int getPosition(char ch) {for (int i=0; i<mVexs.length; i++) if(mVexs[i].data==ch) return i;return -1;}/* * 讀取一個輸入字符*/private char readchar() {char ch='0';do {try {ch = (char)System.in.read();}catch (IOException e) {e.printStackTrace();}}while(!((ch>='a'&&ch<='z') || (ch>='A'&&ch<='Z')));return ch;}/* * 讀取一個輸入字符*/private int readint() {Scanner scanner = new Scanner(System.in);return scanner.nextint();}/* * 打印矩陣隊列圖*/public void print() {System.out.printf("List Graph:/n");for (int i = 0; i < mVexs.length; i++) {System.out.printf("%d(%c): ", i, mVexs[i].data);ENode node = mVexs[i].firstEdge;while (node != null) {System.out.printf("%d(%c) ", node.ivex, mVexs[node.ivex].data);node = node.nextEdge;}System.out.printf("/n");}}public static void main(String[] args) {char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};char[][] edges = new char[][]{ {'A', 'C'}, {'A', 'D'}, {'A', 'F'}, {'B', 'C'}, {'C', 'D'}, {'E', 'G'}, {'F', 'G'}};ListUDG pG;// 自定義"圖"(輸入矩陣隊列)//pG = new ListUDG();// 採用已有的"圖"pG = new ListUDG(vexs, edges);pG.print();// 打印圖}}

總結

以上就是本文關於鄰接表無向圖的Java語言實現完整源碼的全部內容，希望對大家有所幫助。感興趣的朋友可以繼續參閱本站：

Java計算數學表達式代碼詳解

Java中可變長度參數代碼詳解

Java語言求解完美數代碼分析

如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！