圖的實際應(yīng)用

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

地圖：

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

圖的定義及分類

定義： 圖是由一組頂點和一組能夠?qū)蓚€頂點相連的邊組成的。

特殊的圖：

• 自環(huán)：即一條連接一個頂點和其自身的邊；
• 平行邊：連接同一對頂點的兩條邊；

圖的分類：

按照連接兩個頂點的邊的不同，可以把圖分為以下兩種：

無向圖：邊僅僅連接兩個頂點，沒有其他含義；

有向圖：邊不僅連接兩個頂點，并且具有方向；

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

相鄰頂點：

當兩個頂點通過一條邊相連時，我們稱這兩個頂點是相鄰的，并且稱這條邊依附于這兩個頂點。

度：

某個頂點的度就是依附于該頂點的邊的個數(shù)

子圖：

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

路徑：

是由邊順序連接的一系列的頂點組成

環(huán)：

是一條至少含有一條邊且終點和起點相同的路徑

連通圖：

如果圖中任意一個頂點都存在一條路徑到達另外一個頂點，那么這幅圖就稱之為連通圖

連通子圖：

一個非連通圖由若干連通的部分組成，每一個連通的部分都可以稱為該圖的連通子圖

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

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

• 圖中所有的頂點；
• 所有連接頂點的邊；

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

鄰接矩陣

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

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

鄰接表

1.使用一個大小為V的數(shù)組 Queue[V] adj，把索引看做是頂點；

2.每個索引處adj[v]存儲了一個隊列，該隊列中存儲的是所有與該頂點相鄰的其他頂點。

很明顯，鄰接表的空間并不是是線性級別的，所以后面我們一直采用鄰接表這種存儲形式來表示圖。

圖的實現(xiàn)

下面通過代碼實現(xiàn)一個無向圖。

圖的API設(shè)計

代碼實現(xiàn)

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

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

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

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

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

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

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

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

最新評論