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

Java數(shù)據(jù)結(jié)構(gòu)之圖的基礎(chǔ)概念和數(shù)據(jù)模型詳解

 更新時(shí)間:2022年11月01日 09:00:59   作者:JAVA旭陽(yáng)  
在現(xiàn)實(shí)生活中,有許多應(yīng)用場(chǎng)景會(huì)包含很多點(diǎn)以及點(diǎn)點(diǎn)之間的連接,而這些應(yīng)用場(chǎng)景我們都可以用即將要學(xué)習(xí)的圖這種數(shù)據(jù)結(jié)構(gòu)去解決。本文主要介紹了圖的基礎(chǔ)概念和數(shù)據(jù)模型,感興趣的可以了解一下

圖的實(shí)際應(yīng)用

在現(xiàn)實(shí)生活中,有許多應(yīng)用場(chǎng)景會(huì)包含很多點(diǎn)以及點(diǎn)點(diǎn)之間的連接,而這些應(yīng)用場(chǎng)景我們都可以用即將要學(xué)習(xí)的圖這種數(shù)據(jù)結(jié)構(gòu)去解決。

地圖:

我們生活中經(jīng)常使用的地圖,基本上是由城市以及連接城市的道路組成,如果我們把城市看做是一個(gè)一個(gè)的點(diǎn),把道路看做是一條一條的連接,那么地圖就是我們將要學(xué)習(xí)的圖這種數(shù)據(jù)結(jié)構(gòu)。

圖的定義及分類(lèi)

定義: 圖是由一組頂點(diǎn)和一組能夠?qū)蓚€(gè)頂點(diǎn)相連的邊組成的。

特殊的圖:

  • 自環(huán):即一條連接一個(gè)頂點(diǎn)和其自身的邊;
  • 平行邊:連接同一對(duì)頂點(diǎn)的兩條邊;

圖的分類(lèi):

按照連接兩個(gè)頂點(diǎn)的邊的不同,可以把圖分為以下兩種:

無(wú)向圖:邊僅僅連接兩個(gè)頂點(diǎn),沒(méi)有其他含義;

有向圖:邊不僅連接兩個(gè)頂點(diǎn),并且具有方向;

圖的相關(guān)術(shù)語(yǔ)

相鄰頂點(diǎn):

當(dāng)兩個(gè)頂點(diǎn)通過(guò)一條邊相連時(shí),我們稱(chēng)這兩個(gè)頂點(diǎn)是相鄰的,并且稱(chēng)這條邊依附于這兩個(gè)頂點(diǎn)。

度:

某個(gè)頂點(diǎn)的度就是依附于該頂點(diǎn)的邊的個(gè)數(shù)

子圖:

是一幅圖的所有邊的子集(包含這些邊依附的頂點(diǎn))組成的圖;

路徑:

是由邊順序連接的一系列的頂點(diǎn)組成

環(huán):

是一條至少含有一條邊且終點(diǎn)和起點(diǎn)相同的路徑

連通圖:

如果圖中任意一個(gè)頂點(diǎn)都存在一條路徑到達(dá)另外一個(gè)頂點(diǎn),那么這幅圖就稱(chēng)之為連通圖

連通子圖:

一個(gè)非連通圖由若干連通的部分組成,每一個(gè)連通的部分都可以稱(chēng)為該圖的連通子圖

圖的存儲(chǔ)結(jié)構(gòu)

要表示一幅圖,只需要表示清楚以下兩部分內(nèi)容即可:

  • 圖中所有的頂點(diǎn);
  • 所有連接頂點(diǎn)的邊;

常見(jiàn)的圖的存儲(chǔ)結(jié)構(gòu)有兩種:鄰接矩陣和鄰接表。

鄰接矩陣

  • 使用一個(gè)V*V的二維數(shù)組int[V][V] adj,把索引的值看做是頂點(diǎn);
  • 如果頂點(diǎn)v和頂點(diǎn)w相連,我們只需要將adj[v][w]和adj[w][v]的值設(shè)置為1,否則設(shè)置為0即可。

很明顯,鄰接矩陣這種存儲(chǔ)方式的空間復(fù)雜度是V^2的,如果我們處理的問(wèn)題規(guī)模比較大的話(huà),內(nèi)存空間極有可能不夠用。

鄰接表

1.使用一個(gè)大小為V的數(shù)組 Queue[V] adj,把索引看做是頂點(diǎn);

2.每個(gè)索引處adj[v]存儲(chǔ)了一個(gè)隊(duì)列,該隊(duì)列中存儲(chǔ)的是所有與該頂點(diǎn)相鄰的其他頂點(diǎn)。

很明顯,鄰接表的空間并不是是線性級(jí)別的,所以后面我們一直采用鄰接表這種存儲(chǔ)形式來(lái)表示圖。

圖的實(shí)現(xiàn)

下面通過(guò)代碼實(shí)現(xiàn)一個(gè)無(wú)向圖。

圖的API設(shè)計(jì)

類(lèi)名Graph
成員變量1.private final int V: 記錄頂點(diǎn)數(shù)量2.private int E: 記錄邊數(shù)量3.private Queue[] adj: 鄰接表
構(gòu)造方法Graph(int V):創(chuàng)建一個(gè)包含V個(gè)頂點(diǎn)但不包含邊的圖
成員方法1.public int V():獲取圖中頂點(diǎn)的數(shù)量2.public int E():獲取圖中邊的數(shù)量3.public void addEdge(int v,int w):向圖中添加一條邊 v-w4.public Queue adj(int v):獲取和頂點(diǎn)v相鄰的所有頂點(diǎn)

代碼實(shí)現(xiàn)

/**
 * 無(wú)向圖的表示
 *
 * @author alvin
 * @date 2022/10/30
 * @since 1.0
 **/
public class Graph {
    //頂點(diǎn)數(shù)目
    private final int V;
    //邊的數(shù)目
    private int E;
    //鄰接表,隊(duì)列的形式
    private Queue<Integer>[] adj;

    public Graph(int V) {
        // 初始化頂點(diǎn)數(shù)量
        this.V = V;
        //初始化邊的數(shù)量
        this.E = 0;
        //初始化鄰接表
        this.adj = new Queue[V];
        //初始化鄰接表中的空隊(duì)列
        for (int i = 0; i < adj.length; i++) {
            adj[i] = new ArrayDeque<>();
        }
    }

    public void addEdge(int v, int w) {
        //把w添加到v的鏈表中,這樣頂點(diǎn)v就多了一個(gè)相鄰點(diǎn)w
        adj[v].add(w);
        //把v添加到w的鏈表中,這樣頂點(diǎn)w就多了一個(gè)相鄰點(diǎn)v
        adj[w].add(v);
        //邊的數(shù)目自增1
        E++;
    }

    //獲取頂點(diǎn)數(shù)目
    public int V() {
        return V;
    }

    //獲取邊的數(shù)目
    public int E(){
        return E;
    }

    //獲取和頂點(diǎn)v相鄰的所有頂點(diǎn)
    public Queue<Integer> adj(int v) {
        return adj[v];
    }
}

數(shù)組adj的索引表示頂點(diǎn)。

到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)之圖的基礎(chǔ)概念和數(shù)據(jù)模型詳解的文章就介紹到這了,更多相關(guān)Java數(shù)據(jù)結(jié)構(gòu) 圖內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

最新評(píng)論