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

Java用鄰接表存儲圖的示例代碼

 更新時間:2022年06月20日 15:58:11   作者:chengqiuming  
鄰接表是圖的一種鏈式存儲方法,其數(shù)據(jù)結(jié)構(gòu)包括兩部分:節(jié)點和鄰接點。本文將用鄰接表實現(xiàn)存儲圖,感興趣的小伙伴可以了解一下

一、點睛

鄰接表是圖的一種鏈式存儲方法,其數(shù)據(jù)結(jié)構(gòu)包括兩部分:節(jié)點和鄰接點。

用鄰接表可以表示無向圖,有向圖和網(wǎng)。在此用無向圖進行說明。

1.無向圖

2.無向圖的鏈接表

3.說明

節(jié)點 a 的鄰接點是節(jié)點 b、d,其鄰接點的存儲下標為1、3,按照頭插法(逆序)將其放入節(jié)點 a 后面的單鏈表中。

節(jié)點 b 的鄰接點是節(jié)點 a、c、d,其鄰接點的存儲下標為0、2、3,按照頭插法(逆序)將其放入節(jié)點 b 后面的單鏈表中。

節(jié)點 c 的鄰接點是節(jié)點 b、d,其鄰接點的存儲下標為1、3,按照頭插法(逆序)將其放入節(jié)點 c 后面的單鏈表中。

節(jié)點 d 的鄰接點是節(jié)點 a、b、c,其鄰接點的存儲下標為0、1、2,按照頭插法(逆序)將其放入節(jié)點 d 后面的單鏈表中。

4.無向圖

鄰接表的特點如下 如果無向圖中有 n 個節(jié)點、e 條邊,則節(jié)點表中有 n 個節(jié)點,鄰節(jié)點表有 2e 個節(jié)點。

節(jié)點的度為該節(jié)點后面單鏈表中的節(jié)點數(shù)。

二、鄰接表的數(shù)據(jù)結(jié)構(gòu)

1.節(jié)點

包括節(jié)點信息 data 和指向第 1 個鄰接點的指針 first。

2.鄰接點

包括該鄰接點的存儲下標 v 和指向下一個鄰接點的指針 next,如果是網(wǎng)的鄰接點,則還需增加一個權(quán)值域 w,如下圖所示。

三、算法步驟

1 輸入節(jié)點數(shù)和邊數(shù)。

2 依次輸入節(jié)點信息,將其存儲到節(jié)點數(shù)組 Vex[] 的 data 域中,將 Vex[] first 域置空。

3 依次輸入每條邊依附的兩個節(jié)點,如果是網(wǎng),則還需要輸入該邊的權(quán)值。

如果是無向圖,則輸入 a b,查詢節(jié)點 a、b 在節(jié)點數(shù)組 Vex[] 中存儲下標 i、j,創(chuàng)建一個新的鄰接點 s,讓 s.v = j;s.next=null;然后將節(jié)點 s 插入第 i 個節(jié)點的第 1 個鄰接點之前(頭插法)。在無向圖中,從節(jié)點 a 到節(jié)點 b 有邊,從節(jié)點 b 到節(jié)點 a 也有邊,因此還需要創(chuàng)建一個新的鄰接點 s2,讓 s2.v = i;s2.next=null;然后讓 s2 節(jié)點插入第 j 個節(jié)點的第 1 個鄰接點之前(頭插法)。

如果是無向圖,則輸入 a b,查詢節(jié)點 a、b 在節(jié)點數(shù)組 Vex[] 中存儲下標 i、j,創(chuàng)建一個新的鄰接點 s,讓 s.v = j;s.next=null;然后將節(jié)點 s 插入第 i 個節(jié)點的第 1 個鄰接點之前(頭插法)。

如果是無向網(wǎng)或有向網(wǎng),則和無向圖或有向圖的處理方式一樣,只是鄰節(jié)點多了一個權(quán)值域。

四、實現(xiàn)

package graph;
 
import java.util.Scanner;
 
public class CreateALGraph {
    static final int MaxVnum = 100;  // 頂點數(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++) // 查找頂點信息的下標
            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("請輸入頂點數(shù)和邊數(shù):");
        Scanner scanner = new Scanner(System.in);
        G.vexnum = scanner.nextInt();
        G.edgenum = scanner.nextInt();
        System.out.println("請輸入頂點信息:");
 
        for (i = 0; i < G.vexnum; i++)//輸入頂點信息,存入頂點信息數(shù)組
            G.Vex[i].data = scanner.next().charAt(0);
        for (i = 0; i < G.vexnum; i++)
            G.Vex[i].first = null;
        System.out.println("請依次輸入每條邊的兩個頂點u,v");
 
        while (G.edgenum-- > 0) {
            u = scanner.next().charAt(0);
            v = scanner.next().charAt(0);
            i = locatevex(G, u); // 查找頂點 u 的存儲下標
            j = locatevex(G, v); // 查找頂點 v 的存儲下標
            if (i != -1 && j != -1)
                insertedge(G, i, j);
            else {
                System.out.println("輸入頂點信息錯!請重新輸入!");
                G.edgenum++; // 本次輸入不算
            }
        }
    }
}
 
// 定義鄰接點類型
class AdjNode {
    int v; // 鄰接點下標
    AdjNode next; // 指向下一個鄰接點
}
 
// 定義頂點類型
class VexNode {
    char data; // VexType為頂點的數(shù)據(jù)類型,根據(jù)需要定義
    AdjNode first; // 指向第一個鄰接點
}
 
// 定義鄰接表類型
class ALGraph {
    VexNode Vex[] = new VexNode[CreateALGraph.MaxVnum];
    int vexnum; // 頂點數(shù)
    int edgenum; // 邊數(shù)
}

五、測試

白色為輸出,綠色為輸入

以上就是Java用鄰接表存儲圖的示例代碼的詳細內(nèi)容,更多關(guān)于Java鄰接表存儲圖的資料請關(guān)注腳本之家其它相關(guān)文章!

相關(guān)文章

  • java正則表達式獲取指定HTML標簽的指定屬性值且替換的方法

    java正則表達式獲取指定HTML標簽的指定屬性值且替換的方法

    下面小編就為大家?guī)硪黄猨ava正則表達式獲取指定HTML標簽的指定屬性值且替換的方法。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2016-12-12
  • 詳解java nio中的select和channel

    詳解java nio中的select和channel

    這篇文章主要介紹了java nio中的select和channel
    2019-05-05
  • Spring基礎(chǔ)之AOP的概念介紹

    Spring基礎(chǔ)之AOP的概念介紹

    AOP是Spring的關(guān)鍵特性之一,雖然Spring的IOC特性并不依賴于AOP,本文重點介紹AOP編程中的一些術(shù)語,這些術(shù)語不僅僅局限于Spring,它適用于所有的AOP編程,感興趣的朋友一起看看吧
    2022-06-06
  • 分布式醫(yī)療掛號系統(tǒng)EasyExcel導入導出數(shù)據(jù)字典的使用

    分布式醫(yī)療掛號系統(tǒng)EasyExcel導入導出數(shù)據(jù)字典的使用

    這篇文章主要為大家介紹了分布式醫(yī)療掛號系統(tǒng)EasyExcel導入導出數(shù)據(jù)字典的使用,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪
    2022-04-04
  • Java中的Comparable和Comparator接口

    Java中的Comparable和Comparator接口

    這篇文章主要介紹了Java中的Comparable和Comparator接口,文章圍繞主題展開詳細的內(nèi)容戒殺,具有一定的參考價值,需要的小伙伴可以參考一下
    2022-09-09
  • Eclipse項目有紅感嘆號的解決方法

    Eclipse項目有紅感嘆號的解決方法

    這篇文章主要為大家詳細介紹了Eclipse項目有紅感嘆號的解決方法,給出了Eclipse項目有紅感嘆號的原因,以及如何解決?,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2017-04-04
  • @RequestParam 接收參數(shù)的值為null的處理方式

    @RequestParam 接收參數(shù)的值為null的處理方式

    這篇文章主要介紹了@RequestParam 接收參數(shù)的值為null的處理方式,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2021-11-11
  • SpringBoot配置@Configuration注解和@bean注解

    SpringBoot配置@Configuration注解和@bean注解

    這篇文章主要介紹了SpringBoot配置@Configuration注解和@bean注解,文章圍繞主題相關(guān)內(nèi)容展開詳細介紹,具有一定的參考價值,需要的小伙伴可以參考一下
    2022-04-04
  • 基于Mybatis-Plus的CRUD的實現(xiàn)

    基于Mybatis-Plus的CRUD的實現(xiàn)

    這篇文章主要介紹了基于Mybatis-Plus的CRUD的實現(xiàn),文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2019-11-11
  • 深入了解java中的逃逸分析

    深入了解java中的逃逸分析

    這篇文章主要介紹了深入了解java中的逃逸分析,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
    2019-09-09

最新評論