您好,登錄后才能下訂單哦!
本篇內(nèi)容主要講解“Java怎么用鄰接表存儲(chǔ)圖”,感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷,實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“Java怎么用鄰接表存儲(chǔ)圖”吧!
鄰接表是圖的一種鏈?zhǔn)酱鎯?chǔ)方法,其數(shù)據(jù)結(jié)構(gòu)包括兩部分:節(jié)點(diǎn)和鄰接點(diǎn)。
用鄰接表可以表示無向圖,有向圖和網(wǎng)。在此用無向圖進(jìn)行說明。
節(jié)點(diǎn) a 的鄰接點(diǎn)是節(jié)點(diǎn) b、d,其鄰接點(diǎn)的存儲(chǔ)下標(biāo)為1、3,按照頭插法(逆序)將其放入節(jié)點(diǎn) a 后面的單鏈表中。
節(jié)點(diǎn) b 的鄰接點(diǎn)是節(jié)點(diǎn) a、c、d,其鄰接點(diǎn)的存儲(chǔ)下標(biāo)為0、2、3,按照頭插法(逆序)將其放入節(jié)點(diǎn) b 后面的單鏈表中。
節(jié)點(diǎn) c 的鄰接點(diǎn)是節(jié)點(diǎn) b、d,其鄰接點(diǎn)的存儲(chǔ)下標(biāo)為1、3,按照頭插法(逆序)將其放入節(jié)點(diǎn) c 后面的單鏈表中。
節(jié)點(diǎn) d 的鄰接點(diǎn)是節(jié)點(diǎn) a、b、c,其鄰接點(diǎn)的存儲(chǔ)下標(biāo)為0、1、2,按照頭插法(逆序)將其放入節(jié)點(diǎn) d 后面的單鏈表中。
鄰接表的特點(diǎn)如下 如果無向圖中有 n 個(gè)節(jié)點(diǎn)、e 條邊,則節(jié)點(diǎn)表中有 n 個(gè)節(jié)點(diǎn),鄰節(jié)點(diǎn)表有 2e 個(gè)節(jié)點(diǎn)。
節(jié)點(diǎn)的度為該節(jié)點(diǎn)后面單鏈表中的節(jié)點(diǎn)數(shù)。
包括節(jié)點(diǎn)信息 data 和指向第 1 個(gè)鄰接點(diǎn)的指針 first。
包括該鄰接點(diǎn)的存儲(chǔ)下標(biāo) v 和指向下一個(gè)鄰接點(diǎn)的指針 next,如果是網(wǎng)的鄰接點(diǎn),則還需增加一個(gè)權(quán)值域 w,如下圖所示。
1 輸入節(jié)點(diǎn)數(shù)和邊數(shù)。
2 依次輸入節(jié)點(diǎn)信息,將其存儲(chǔ)到節(jié)點(diǎn)數(shù)組 Vex[] 的 data 域中,將 Vex[] first 域置空。
3 依次輸入每條邊依附的兩個(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,創(chuàng)建一個(gè)新的鄰接點(diǎn) s,讓 s.v = j;s.next=null;然后將節(jié)點(diǎn) s 插入第 i 個(gè)節(jié)點(diǎn)的第 1 個(gè)鄰接點(diǎn)之前(頭插法)。在無向圖中,從節(jié)點(diǎn) a 到節(jié)點(diǎn) b 有邊,從節(jié)點(diǎn) b 到節(jié)點(diǎn) a 也有邊,因此還需要?jiǎng)?chuàng)建一個(gè)新的鄰接點(diǎn) s2,讓 s2.v = i;s2.next=null;然后讓 s2 節(jié)點(diǎn)插入第 j 個(gè)節(jié)點(diǎn)的第 1 個(gè)鄰接點(diǎn)之前(頭插法)。
如果是無向圖,則輸入 a b,查詢節(jié)點(diǎn) a、b 在節(jié)點(diǎn)數(shù)組 Vex[] 中存儲(chǔ)下標(biāo) i、j,創(chuàng)建一個(gè)新的鄰接點(diǎn) s,讓 s.v = j;s.next=null;然后將節(jié)點(diǎn) s 插入第 i 個(gè)節(jié)點(diǎn)的第 1 個(gè)鄰接點(diǎn)之前(頭插法)。
如果是無向網(wǎng)或有向網(wǎng),則和無向圖或有向圖的處理方式一樣,只是鄰節(jié)點(diǎn)多了一個(gè)權(quán)值域。
package graph; import java.util.Scanner; public class CreateALGraph { static final int MaxVnum = 100; // 頂點(diǎn)數(shù)最大值 public static void main(String[] args) { ALGraph G = new ALGraph(); for (int i = 0; i < G.Vex.length; i++) { G.Vex[i] = new VexNode(); } CreateALGraph(G); // 創(chuàng)建有向圖鄰接表 printg(G); // 輸出鄰接表 } static int locatevex(ALGraph G, char x) { for (int i = 0; i < G.vexnum; i++) // 查找頂點(diǎn)信息的下標(biāo) if (x == G.Vex[i].data) return i; return -1; // 沒找到 } // 插入一條邊 static void insertedge(ALGraph G, int i, int j) { AdjNode s = new AdjNode(); s.v = j; s.next = G.Vex[i].first; G.Vex[i].first = s; } // 輸出鄰接表 static void printg(ALGraph G) { System.out.println("----------鄰接表如下:----------"); for (int i = 0; i < G.vexnum; i++) { AdjNode t = G.Vex[i].first; System.out.print(G.Vex[i].data + ": "); while (t != null) { System.out.print("[" + t.v + "]\t"); t = t.next; } System.out.println(); } } // 創(chuàng)建有向圖鄰接表 static void CreateALGraph(ALGraph G) { int i, j; char u, v; System.out.println("請輸入頂點(diǎn)數(shù)和邊數(shù):"); Scanner scanner = new Scanner(System.in); G.vexnum = scanner.nextInt(); G.edgenum = scanner.nextInt(); System.out.println("請輸入頂點(diǎn)信息:"); for (i = 0; i < G.vexnum; i++)//輸入頂點(diǎn)信息,存入頂點(diǎn)信息數(shù)組 G.Vex[i].data = scanner.next().charAt(0); for (i = 0; i < G.vexnum; i++) G.Vex[i].first = null; System.out.println("請依次輸入每條邊的兩個(gè)頂點(diǎn)u,v"); 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) insertedge(G, i, j); else { System.out.println("輸入頂點(diǎn)信息錯(cuò)!請重新輸入!"); G.edgenum++; // 本次輸入不算 } } } } // 定義鄰接點(diǎn)類型 class AdjNode { int v; // 鄰接點(diǎn)下標(biāo) AdjNode next; // 指向下一個(gè)鄰接點(diǎn) } // 定義頂點(diǎn)類型 class VexNode { char data; // VexType為頂點(diǎn)的數(shù)據(jù)類型,根據(jù)需要定義 AdjNode first; // 指向第一個(gè)鄰接點(diǎn) } // 定義鄰接表類型 class ALGraph { VexNode Vex[] = new VexNode[CreateALGraph.MaxVnum]; int vexnum; // 頂點(diǎn)數(shù) int edgenum; // 邊數(shù) }
白色為輸出,綠色為輸入
到此,相信大家對“Java怎么用鄰接表存儲(chǔ)圖”有了更深的了解,不妨來實(shí)際操作一番吧!這里是億速云網(wǎng)站,更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢,關(guān)注我們,繼續(xù)學(xué)習(xí)!
免責(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)容。