Java數(shù)據(jù)結(jié)構(gòu)之圖的領(lǐng)接矩陣詳解
1.圖的領(lǐng)接矩陣(Adjacency Matrix)存儲結(jié)構(gòu)
圖的領(lǐng)接矩陣(Adjacency Matrix)存儲方式是用兩個數(shù)組來表示圖。一個一位數(shù)組存儲圖中頂點信息,一個二維數(shù)組(稱為領(lǐng)接矩陣)存儲圖中的邊或弧的信息。
舉例
無向圖
無向圖的領(lǐng)接矩陣的第i行或第i列的非零元素個數(shù)正好是第i個頂點的度。
有向圖
有向圖的領(lǐng)接矩陣的第i行的非零元素個數(shù)正好是第i個頂點的出度,第i列的非零元素個數(shù)正好是第i個頂點的入度。
帶權(quán)值的網(wǎng)圖
2.圖的接口類
3.圖的類型,用枚舉類表示
public enum GraphKind { UDG,DG,UDN,DN;//無向圖、有向圖、無向網(wǎng)、有向網(wǎng) }
4.圖的領(lǐng)接矩陣描述
對于一個具有n個頂點的圖G,可以將圖G的領(lǐng)接矩陣存儲在一個二維數(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; //圖的標志 private int vexNum, arcNum; //圖當前頂點和邊數(shù) private Object[] vexs; //頂點 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) { // 實參構(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("請輸入圖的類型:"); 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)建無向圖 Scanner sc = new Scanner(System.in); System.out.println("請輸入圖的頂點數(shù)、圖的邊數(shù):"); vexNum = sc.nextInt(); arcNum = sc.nextInt(); vexs = new Object[vexNum]; System.out.println("請分別輸入圖的各個頂點"); for (int v = 0; v < vexNum; v++) //構(gòu)造頂點函數(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("請輸入各個邊的兩個頂點及其權(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ǎng) } private void createDN() { //創(chuàng)建有向網(wǎng) Scanner sc = new Scanner(System.in); System.out.println("請輸入圖的頂點數(shù)、圖的邊數(shù):"); vexNum = sc.nextInt(); arcNum = sc.nextInt(); vexs = new Object[vexNum]; System.out.println("請分別輸入圖的各個頂點"); for (int v = 0; v < vexNum; v++) //構(gòu)造頂點函數(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("請輸入各個邊的兩個頂點及其權(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; //返回頂點數(shù) } @Override public int getArcNum() { return arcNum; //返回邊數(shù) } @Override //返回v的第一個領(lǐng)接點,若v沒有領(lǐng)接點返回-1; public Object getVex(int v) throws Exception { if (v < 0 && v >= vexNum) throw new Exception("第" + v + "個頂點不存在!"); return vexs[v]; <0v<vexNum } @Override public int locateVex(Object vex) { //頂點定位法 for (int v = 0; v < vexNum; v++) if (vexs[v].equals(vex)) return v; return 0; } @Override public int firstAdjVex(int v) throws Exception { //查找第一個領(lǐng)接點 if (v < 0 && v >= vexNum) throw new Exception("第" + v + "個頂點不存在!"); 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) { //查找下一個領(lǐng)接點 return 0; } public GraphKind getKind(){ //返回圖標類型 return kind; } public int[][] getArcs() { //返回鄰接矩陣的值 return arcs; } //返回頂點 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ǎng)的頂點個數(shù)為:"+M.getVexNum()); System.out.println("創(chuàng)建無向網(wǎng)的邊個數(shù)為:"+M.getArcNum()); System.out.println("請輸入要查找頂點的值:"); Scanner sc=new Scanner(System.in); Object top=sc.next(); System.out.println("要查找頂點"+top+"的值為:"+ M.locateVex(top)); System.out.println("請輸入要查找頂點的索引:"); int x= sc.nextInt(); System.out.println("要查找位置"+x+"處的頂點值為:"+M.getVex(x) ); System.out.println("請輸入鄰接點的頂點的位置:"); int n= sc.nextInt(); System.out.println("要查找位置"+n+"處的頂點值為:"+M.firstAdjVex(n) ); } }
結(jié)果
以上就是Java數(shù)據(jù)結(jié)構(gòu)之圖的領(lǐng)接矩陣詳解的詳細內(nèi)容,更多關(guān)于Java數(shù)據(jù)結(jié)構(gòu)資料請關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
解決HttpServletResponse和HttpServletRequest取值的2個坑
這篇文章主要介紹了解決HttpServletResponse和HttpServletRequest取值的2個坑問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-12-12InteliJ IDEA 設(shè)置eclipse快捷鍵 的圖文教程
本文通過圖文并茂的形式給大家介紹了InteliJ IDEA 設(shè)置eclipse快捷鍵 ,非常不錯,具有一定的參考借鑒價值,需要的朋友參考下2018-06-06Apache Calcite進行SQL解析(java代碼實例)
Calcite是一款開源SQL解析工具, 可以將各種SQL語句解析成抽象語法樹AST(Abstract Syntax Tree), 之后通過操作AST就可以把SQL中所要表達的算法與關(guān)系體現(xiàn)在具體代碼之中,今天通過代碼實例給大家介紹Apache Calcite進行SQL解析問題,感興趣的朋友一起看看吧2022-01-01