您好,登錄后才能下訂單哦!
本篇內(nèi)容介紹了“Java數(shù)據(jù)結(jié)構(gòu)圖的領(lǐng)接矩陣舉例分析”的有關(guān)知識(shí),在實(shí)際案例的操作過(guò)程中,不少人都會(huì)遇到這樣的困境,接下來(lái)就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧!希望大家仔細(xì)閱讀,能夠?qū)W有所成!
圖的領(lǐng)接矩陣(Adjacency Matrix)存儲(chǔ)方式是用兩個(gè)數(shù)組來(lái)表示圖。一個(gè)一位數(shù)組存儲(chǔ)圖中頂點(diǎn)信息,一個(gè)二維數(shù)組(稱為領(lǐng)接矩陣)存儲(chǔ)圖中的邊或弧的信息。
舉例
無(wú)向圖
無(wú)向圖的領(lǐng)接矩陣的第i行或第i列的非零元素個(gè)數(shù)正好是第i個(gè)頂點(diǎn)的度。
有向圖
有向圖的領(lǐng)接矩陣的第i行的非零元素個(gè)數(shù)正好是第i個(gè)頂點(diǎn)的出度,第i列的非零元素個(gè)數(shù)正好是第i個(gè)頂點(diǎn)的入度。
帶權(quán)值的網(wǎng)圖
public enum GraphKind { UDG,DG,UDN,DN;//無(wú)向圖、有向圖、無(wú)向網(wǎng)、有向網(wǎng) }
對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的圖G,可以將圖G的領(lǐng)接矩陣存儲(chǔ)在一個(gè)二維數(shù)組中.
package Graph; /* 圖的領(lǐng)接矩陣描述類 */ import java.util.Scanner; public class MyGraph implements IGraph { public final static int INFINITY = Integer.MAX_VALUE; private GraphKind kind; //圖的標(biāo)志 private int vexNum, arcNum; //圖當(dāng)前頂點(diǎn)和邊數(shù) private Object[] vexs; //頂點(diǎn) private int[][] arcs; //鄰接矩陣 public MyGraph() { //空參構(gòu)造 this(null, 0, 0, null, null); } public MyGraph(GraphKind kind, int vexNum, int arcNum, Object[] vexs, int[][] arcs) { // 實(shí)參構(gòu)造 this.kind = kind; this.vexNum = vexNum; this.arcNum = arcNum; this.vexs = vexs; this.arcs = arcs; } @Override public void createGraph() { //創(chuàng)建新圖 Scanner sc = new Scanner(System.in); System.out.println("請(qǐng)輸入圖的類型:"); GraphKind kind = GraphKind.valueOf(sc.next()); switch (kind) { case UDG: createUDG(); return; case DG: createDG(); return; case UDN: createUDG(); return; case DN: createDN(); return; } } private void createUDG() { //創(chuàng)建無(wú)向圖 Scanner sc = new Scanner(System.in); System.out.println("請(qǐng)輸入圖的頂點(diǎn)數(shù)、圖的邊數(shù):"); vexNum = sc.nextInt(); arcNum = sc.nextInt(); vexs = new Object[vexNum]; System.out.println("請(qǐng)分別輸入圖的各個(gè)頂點(diǎn)"); for (int v = 0; v < vexNum; v++) //構(gòu)造頂點(diǎn)函數(shù) vexs[v] = sc.next(); arcs = new int[vexNum][vexNum]; for (int v = 0; v < vexNum; v++) for (int u = 0; u < vexNum; u++) arcs[v][u] = INFINITY; //初始化領(lǐng)接矩陣 System.out.println("請(qǐng)輸入各個(gè)邊的兩個(gè)頂點(diǎn)及其權(quán)值:"); for (int k = 0; k < arcNum; k++) { int v = locateVex(sc.next()); int u = locateVex(sc.next()); arcs[v][u] = arcs[v][u] = sc.nextInt(); } } private void createDG() { //創(chuàng)建有向圖 } ; private void createUDN() { //創(chuàng)建無(wú)向網(wǎng) } private void createDN() { //創(chuàng)建有向網(wǎng) Scanner sc = new Scanner(System.in); System.out.println("請(qǐng)輸入圖的頂點(diǎn)數(shù)、圖的邊數(shù):"); vexNum = sc.nextInt(); arcNum = sc.nextInt(); vexs = new Object[vexNum]; System.out.println("請(qǐng)分別輸入圖的各個(gè)頂點(diǎn)"); for (int v = 0; v < vexNum; v++) //構(gòu)造頂點(diǎn)函數(shù) vexs[v] = sc.next(); arcs = new int[vexNum][vexNum]; for (int v = 0; v < vexNum; v++) for (int u = 0; u < vexNum; u++) arcs[v][u] = INFINITY; //初始化領(lǐng)接矩陣 System.out.println("請(qǐng)輸入各個(gè)邊的兩個(gè)頂點(diǎn)及其權(quán)值:"); for (int k = 0; k < arcNum; k++) { int v = locateVex(sc.next()); int u = locateVex(sc.next()); arcs[v][u] = sc.nextInt(); } } @Override public int getVexNum() { return vexNum; //返回頂點(diǎn)數(shù) } @Override public int getArcNum() { return arcNum; //返回邊數(shù) } @Override //返回v的第一個(gè)領(lǐng)接點(diǎn),若v沒(méi)有領(lǐng)接點(diǎn)返回-1; public Object getVex(int v) throws Exception { if (v < 0 && v >= vexNum) throw new Exception("第" + v + "個(gè)頂點(diǎn)不存在!"); return vexs[v]; <0v<vexNum } @Override public int locateVex(Object vex) { //頂點(diǎn)定位法 for (int v = 0; v < vexNum; v++) if (vexs[v].equals(vex)) return v; return 0; } @Override public int firstAdjVex(int v) throws Exception { //查找第一個(gè)領(lǐng)接點(diǎn) if (v < 0 && v >= vexNum) throw new Exception("第" + v + "個(gè)頂點(diǎn)不存在!"); for (int j = 0; j < vexNum; j++) if (arcs[v][j] != 0 && arcs[v][j] < INFINITY) return j; return -1; } @Override public int nextAdjvex(int v, int w) { //查找下一個(gè)領(lǐng)接點(diǎn) return 0; } public GraphKind getKind(){ //返回圖標(biāo)類型 return kind; } public int[][] getArcs() { //返回鄰接矩陣的值 return arcs; } //返回頂點(diǎn) public Object[] getVexs() { return vexs; } }
public static void main(String[] args) throws Exception { MyGraph M=new MyGraph(); //創(chuàng)建圖空間 M.createGraph(); System.out.println("創(chuàng)建無(wú)向網(wǎng)的頂點(diǎn)個(gè)數(shù)為:"+M.getVexNum()); System.out.println("創(chuàng)建無(wú)向網(wǎng)的邊個(gè)數(shù)為:"+M.getArcNum()); System.out.println("請(qǐng)輸入要查找頂點(diǎn)的值:"); Scanner sc=new Scanner(System.in); Object top=sc.next(); System.out.println("要查找頂點(diǎn)"+top+"的值為:"+ M.locateVex(top)); System.out.println("請(qǐng)輸入要查找頂點(diǎn)的索引:"); int x= sc.nextInt(); System.out.println("要查找位置"+x+"處的頂點(diǎn)值為:"+M.getVex(x) ); System.out.println("請(qǐng)輸入鄰接點(diǎn)的頂點(diǎn)的位置:"); int n= sc.nextInt(); System.out.println("要查找位置"+n+"處的頂點(diǎn)值為:"+M.firstAdjVex(n) ); } }
“Java數(shù)據(jù)結(jié)構(gòu)圖的領(lǐng)接矩陣舉例分析”的內(nèi)容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站,小編將為大家輸出更多高質(zhì)量的實(shí)用文章!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。