欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java數(shù)據(jù)結(jié)構(gòu)之圖的領(lǐng)接矩陣詳解

 更新時間:2021年11月30日 16:50:34   作者:    
圖的領(lǐng)接矩陣存儲方式是用兩個數(shù)組來表示圖。一個一位數(shù)組存儲圖中頂點信息,一個二維數(shù)組存儲圖中的邊或弧的信息。本文將為大家重點介紹一下數(shù)據(jù)結(jié)構(gòu)中的圖的鄰接矩陣,快來跟隨小編一起學習吧

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個坑

    這篇文章主要介紹了解決HttpServletResponse和HttpServletRequest取值的2個坑問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
    2023-12-12
  • Spring的Model?和?Map的原理源碼解析

    Spring的Model?和?Map的原理源碼解析

    這篇文章主要介紹了Spring的Model?和?Map的原理解析,本文給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2022-06-06
  • java定時器timer的使用方法代碼示例

    java定時器timer的使用方法代碼示例

    這篇文章主要介紹了java定時器timer的使用方法代碼示例,向大家分享了兩部分代碼,詳細內(nèi)容請參見正文,還是比較不錯的,需要的朋友可以參考下。
    2017-11-11
  • InteliJ IDEA 設(shè)置eclipse快捷鍵 的圖文教程

    InteliJ IDEA 設(shè)置eclipse快捷鍵 的圖文教程

    本文通過圖文并茂的形式給大家介紹了InteliJ IDEA 設(shè)置eclipse快捷鍵 ,非常不錯,具有一定的參考借鑒價值,需要的朋友參考下
    2018-06-06
  • SpringBoot整合Mail發(fā)送郵件功能

    SpringBoot整合Mail發(fā)送郵件功能

    我們在網(wǎng)站上注冊賬號的時候一般需要獲取驗證碼,而這個驗證碼一般發(fā)送在你的手機號上還有的是發(fā)送在你的郵箱中,注冊,賬號密碼…都需要用到驗證,今天就演示一下如何用SpringBoot整合Mail發(fā)送郵箱
    2021-11-11
  • JAVA日期處理類詳解

    JAVA日期處理類詳解

    這篇文章主要介紹了Java實現(xiàn)的日期處理類,結(jié)合完整實例形式分析了Java針對日期的獲取、運算、轉(zhuǎn)換等相關(guān)操作技巧,需要的朋友可以參考下
    2021-08-08
  • MyBatis update標簽詳解

    MyBatis update標簽詳解

    這篇文章主要介紹了MyBatis update標簽,使用 Map 傳遞參數(shù)會導致業(yè)務(wù)可讀性的喪失,繼而導致后續(xù)擴展和維護的困難,所以在實際應(yīng)用中我們應(yīng)該果斷廢棄該方式,需要的朋友可以參考下
    2023-10-10
  • Apache Calcite進行SQL解析(java代碼實例)

    Apache Calcite進行SQL解析(java代碼實例)

    Calcite是一款開源SQL解析工具, 可以將各種SQL語句解析成抽象語法樹AST(Abstract Syntax Tree), 之后通過操作AST就可以把SQL中所要表達的算法與關(guān)系體現(xiàn)在具體代碼之中,今天通過代碼實例給大家介紹Apache Calcite進行SQL解析問題,感興趣的朋友一起看看吧
    2022-01-01
  • java面試常見問題之Hibernate總結(jié)

    java面試常見問題之Hibernate總結(jié)

    這篇文章主要介紹了在java面試過程中hibernate比較常見的問題,包括Hibernate的檢索方式,Hibernate中對象的狀態(tài),Hibernate的3種檢索策略是什么,Session的find()方法以及Query接口的區(qū)別等方面問題的總結(jié),需要的朋友可以參考下
    2015-07-07
  • SpringBoot開發(fā)實戰(zhàn)之自動配置

    SpringBoot開發(fā)實戰(zhàn)之自動配置

    SpringBoot的核心就是自動配置,自動配置又是基于條件判斷來配置Bean,下面這篇文章主要給大家介紹了關(guān)于SpringBoot開發(fā)實戰(zhàn)之自動配置的相關(guān)資料,需要的朋友可以參考下
    2021-08-08

最新評論