鄰接表無向圖的Java語言實(shí)現(xiàn)完整源碼
更新時(shí)間：2017年12月08日 10:44:14 作者：Coding-lover
這篇文章主要介紹了鄰接表無向圖的Java語言實(shí)現(xiàn)完整源碼，具有一定借鑒價(jià)值，需要的朋友可以參考下。
鄰接表無向圖的介紹
鄰接表無向圖是指通過鄰接表表示的無向圖。
上面的圖G1包含了”A,B,C,D,E,F,G”共7個(gè)頂點(diǎn)，而且包含了”(A,C),(A,D),(A,F),(B,C),(C,D),(E,G),(F,G)”共7條邊。
上圖右邊的矩陣是G1在內(nèi)存中的鄰接表示意圖。每一個(gè)頂點(diǎn)都包含一條鏈表，該鏈表記錄了”該頂點(diǎn)的鄰接點(diǎn)的序號(hào)”。例如，第2個(gè)頂點(diǎn)(頂點(diǎn)C)包含的鏈表所包含的節(jié)點(diǎn)的數(shù)據(jù)分別是”0,1,3”；而這”0,1,3”分別對(duì)應(yīng)”A,B,D”的序號(hào)，”A,B,D”都是C的鄰接點(diǎn)。就是通過這種方式記錄圖的信息的。
鄰接表無向圖的代碼說明
1. 基本定義
public class ListUDG {
// 鄰接表中表對(duì)應(yīng)的鏈表的頂點(diǎn)
private class ENode {
int ivex;
// 該邊所指向的頂點(diǎn)的位置
ENode nextEdge;
// 指向下一條弧的指針
}
// 鄰接表中表的頂點(diǎn)
private class VNode {
char data;
// 頂點(diǎn)信息
ENode firstEdge;
// 指向第一條依附該頂點(diǎn)的弧
}
;
private VNode[] mVexs;
// 頂點(diǎn)數(shù)組
...
}
(01)ListUDG是鄰接表對(duì)應(yīng)的結(jié)構(gòu)體。mVexs則是保存頂點(diǎn)信息的一維數(shù)組。
(02)VNode是鄰接表頂點(diǎn)對(duì)應(yīng)的結(jié)構(gòu)體。data是頂點(diǎn)所包含的數(shù)據(jù)，而firstEdge是該頂點(diǎn)所包含鏈表的表頭指針。
(03)ENode是鄰接表頂點(diǎn)所包含的鏈表的節(jié)點(diǎn)對(duì)應(yīng)的結(jié)構(gòu)體。ivex是該節(jié)點(diǎn)所對(duì)應(yīng)的頂點(diǎn)在vexs中的索引，而nextEdge是指向下一個(gè)節(jié)點(diǎn)的。
2.創(chuàng)建矩陣
這里介紹提供了兩個(gè)創(chuàng)建矩陣的方法。一個(gè)是用已知數(shù)據(jù)，另一個(gè)則需要用戶手動(dòng)輸入數(shù)據(jù)。
2.1創(chuàng)建圖(用已提供的矩陣)
/*
* 創(chuàng)建圖(用已提供的矩陣)
*
* 參數(shù)說明：
* vexs -- 頂點(diǎn)數(shù)組
* edges -- 邊數(shù)組
*/
public ListUDG(char[] vexs, char[][] edges) {
// 初始化"頂點(diǎn)數(shù)"和"邊數(shù)"
int vlen = vexs.length;
int elen = edges.length;
// 初始化"頂點(diǎn)"
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++) {
// 讀取邊的起始頂點(diǎn)和結(jié)束頂點(diǎn)
char c1 = edges[i][0];
char c2 = edges[i][1];
// 讀取邊的起始頂點(diǎn)和結(jié)束頂點(diǎn)
int p1 = getPosition(edges[i][0]);
int p2 = getPosition(edges[i][1]);
// 初始化node1
ENode node1 = new ENode();
node1.ivex = p2;
// 將node1鏈接到"p1所在鏈表的末尾"
if(mVexs[p1].firstEdge == null)
mVexs[p1].firstEdge = node1; else
linkLast(mVexs[p1].firstEdge, node1);
// 初始化node2
ENode node2 = new ENode();
node2.ivex = p1;
// 將node2鏈接到"p2所在鏈表的末尾"
if(mVexs[p2].firstEdge == null)
mVexs[p2].firstEdge = node2; else
linkLast(mVexs[p2].firstEdge, node2);
}
}
該函數(shù)的作用是創(chuàng)建一個(gè)鄰接表無向圖。實(shí)際上，該方法創(chuàng)建的無向圖，就是上面圖G1。調(diào)用代碼如下：
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 創(chuàng)建圖(自己輸入)
/*
* 創(chuàng)建圖(自己輸入數(shù)據(jù))
*/
public ListUDG() {
// 輸入"頂點(diǎn)數(shù)"和"邊數(shù)"
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 ;
}
// 初始化"頂點(diǎn)"
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++) {
// 讀取邊的起始頂點(diǎn)和結(jié)束頂點(diǎn)
System.out.printf("edge(%d):", i);
char c1 = readchar();
char c2 = readchar();
int p1 = getPosition(c1);
int p2 = getPosition(c2);
// 初始化node1
ENode node1 = new ENode();
node1.ivex = p2;
// 將node1鏈接到"p1所在鏈表的末尾"
if(mVexs[p1].firstEdge == null)
mVexs[p1].firstEdge = node1; else
linkLast(mVexs[p1].firstEdge, node1);
// 初始化node2
ENode node2 = new ENode();
node2.ivex = p1;
// 將node2鏈接到"p2所在鏈表的末尾"
if(mVexs[p2].firstEdge == null)
mVexs[p2].firstEdge = node2; else
linkLast(mVexs[p2].firstEdge, node2);
}
}
該函數(shù)是讀取用戶的輸入，將輸入的數(shù)據(jù)轉(zhuǎn)換成對(duì)應(yīng)的無向圖。
鄰接表無向圖的完整源碼
import java.io.IOException;
import java.util.Scanner;
public class ListUDG {
// 鄰接表中表對(duì)應(yīng)的鏈表的頂點(diǎn)
private class ENode {
int ivex;
// 該邊所指向的頂點(diǎn)的位置
ENode nextEdge;
// 指向下一條弧的指針
}
// 鄰接表中表的頂點(diǎn)
private class VNode {
char data;
// 頂點(diǎn)信息
ENode firstEdge;
// 指向第一條依附該頂點(diǎn)的弧
}
;
private VNode[] mVexs;
// 頂點(diǎn)數(shù)組
/*
* 創(chuàng)建圖(自己輸入數(shù)據(jù))
*/
public ListUDG() {
// 輸入"頂點(diǎn)數(shù)"和"邊數(shù)"
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 ;
}
// 初始化"頂點(diǎn)"
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++) {
// 讀取邊的起始頂點(diǎn)和結(jié)束頂點(diǎn)
System.out.printf("edge(%d):", i);
char c1 = readchar();
char c2 = readchar();
int p1 = getPosition(c1);
int p2 = getPosition(c2);
// 初始化node1
ENode node1 = new ENode();
node1.ivex = p2;
// 將node1鏈接到"p1所在鏈表的末尾"
if(mVexs[p1].firstEdge == null)
mVexs[p1].firstEdge = node1; else
linkLast(mVexs[p1].firstEdge, node1);
// 初始化node2
ENode node2 = new ENode();
node2.ivex = p1;
// 將node2鏈接到"p2所在鏈表的末尾"
if(mVexs[p2].firstEdge == null)
mVexs[p2].firstEdge = node2; else
linkLast(mVexs[p2].firstEdge, node2);
}
}
/*
* 創(chuàng)建圖(用已提供的矩陣)
*
* 參數(shù)說明：
* vexs -- 頂點(diǎn)數(shù)組
* edges -- 邊數(shù)組
*/
public ListUDG(char[] vexs, char[][] edges) {
// 初始化"頂點(diǎn)數(shù)"和"邊數(shù)"
int vlen = vexs.length;
int elen = edges.length;
// 初始化"頂點(diǎn)"
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++) {
// 讀取邊的起始頂點(diǎn)和結(jié)束頂點(diǎn)
char c1 = edges[i][0];
char c2 = edges[i][1];
// 讀取邊的起始頂點(diǎn)和結(jié)束頂點(diǎn)
int p1 = getPosition(edges[i][0]);
int p2 = getPosition(edges[i][1]);
// 初始化node1
ENode node1 = new ENode();
node1.ivex = p2;
// 將node1鏈接到"p1所在鏈表的末尾"
if(mVexs[p1].firstEdge == null)
mVexs[p1].firstEdge = node1; else
linkLast(mVexs[p1].firstEdge, node1);
// 初始化node2
ENode node2 = new ENode();
node2.ivex = p1;
// 將node2鏈接到"p2所在鏈表的末尾"
if(mVexs[p2].firstEdge == null)
mVexs[p2].firstEdge = node2; else
linkLast(mVexs[p2].firstEdge, node2);
}
}
/*
* 將node節(jié)點(diǎn)鏈接到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;
}
/*
* 讀取一個(gè)輸入字符
*/
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;
}
/*
* 讀取一個(gè)輸入字符
*/
private int readint() {
Scanner scanner = new Scanner(System.in);
return scanner.nextint();
}
/*
* 打印矩陣隊(duì)列圖
*/
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;
// 自定義"圖"(輸入矩陣隊(duì)列)
//pG = new ListUDG();
// 采用已有的"圖"
pG = new ListUDG(vexs, edges);
pG.print();
// 打印圖
}
}
總結(jié)
以上就是本文關(guān)于鄰接表無向圖的Java語言實(shí)現(xiàn)完整源碼的全部?jī)?nèi)容，希望對(duì)大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站：
Java計(jì)算數(shù)學(xué)表達(dá)式代碼詳解
如有不足之處，歡迎留言指出。感謝朋友們對(duì)本站的支持！
相關(guān)文章
Java中的synchronized?優(yōu)化方法之鎖膨脹機(jī)制
這篇文章主要介紹了Java中的synchronized?優(yōu)化方法之鎖膨脹機(jī)制，鎖膨脹機(jī)制是提升?synchronized?性能最有利的方法之一，下面我們就來看看什么事鎖膨脹及鎖膨脹的各種細(xì)節(jié)2022-05-05
這篇文章主要介紹了Java實(shí)現(xiàn)線程的四種方式解析,線程是進(jìn)程中的一個(gè)執(zhí)行單元,負(fù)責(zé)當(dāng)前進(jìn)程中程序的執(zhí)行,一個(gè)進(jìn)程中至少有一個(gè)線程,一個(gè)進(jìn)程中是可以有多個(gè)線程的,這個(gè)應(yīng)用程序也可以稱之為多線程程序,需要的朋友可以參考下2023-10-10
Java畢業(yè)設(shè)計(jì)實(shí)戰(zhàn)之健身器材商城系統(tǒng)的實(shí)現(xiàn)
只學(xué)書上的理論是遠(yuǎn)遠(yuǎn)不夠的，只有在實(shí)戰(zhàn)中才能獲得能力的提升，本篇文章手把手帶你用java+Jdbc+Servlet+Ajax+Fileupload+mysql實(shí)現(xiàn)健身器材商城系統(tǒng),大家可以在過程中查缺補(bǔ)漏，提升水平2022-03-03
這篇文章主要給大家介紹了關(guān)于Java如何重寫object類的equals方法的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-12-12
java lambda循環(huán)_使用Java 8 Lambda簡(jiǎn)化嵌套循環(huán)操作
這篇文章主要介紹了java lambda循環(huán)_使用Java 8 Lambda簡(jiǎn)化嵌套循環(huán)操作，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2020-09-09
java使用PDFRenderer實(shí)現(xiàn)預(yù)覽PDF功能
這篇文章主要為大家詳細(xì)介紹了java使用PDFRenderer實(shí)現(xiàn)預(yù)覽PDF功能，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-12-12
Java實(shí)現(xiàn)將png格式圖片轉(zhuǎn)換成jpg格式圖片的方法【測(cè)試可用】
這篇文章主要介紹了Java實(shí)現(xiàn)將png格式圖片轉(zhuǎn)換成jpg格式圖片的方法,涉及java文件讀寫及圖形創(chuàng)建等相關(guān)操作技巧,需要的朋友可以參考下2018-03-03
RestTemplate如何通過HTTP?Basic?Auth認(rèn)證示例說明
這篇文章主要為大家介紹了RestTemplate如何通過HTTP?Basic?Auth認(rèn)證的示例說明，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-03-03
這篇文章主要介紹了MyBatis-Plus執(zhí)行SQL分析打印過程,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-09-09
Java使用Callable接口實(shí)現(xiàn)多線程的實(shí)例代碼
這篇文章主要介紹了Java使用Callable接口實(shí)現(xiàn)多線程的實(shí)例代碼,實(shí)現(xiàn)Callable和實(shí)現(xiàn)Runnable類似,但是功能更強(qiáng)大,具體表現(xiàn)在可以在任務(wù)結(jié)束后提供一個(gè)返回值,Runnable不行,call方法可以拋出異,Runnable的run方法不行,需要的朋友可以參考下2023-08-08