圖的實際應(yīng)用

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

地圖：

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

圖的定義及分類

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

特殊的圖：

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

圖的分類：

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

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

有向圖：邊不僅連接兩個頂點(diǎn)，并且具有方向；

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

相鄰頂點(diǎn)：

當(dāng)兩個頂點(diǎn)通過一條邊相連時，我們稱這兩個頂點(diǎn)是相鄰的，并且稱這條邊依附于這兩個頂點(diǎn)。

度：

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

子圖：

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

路徑：

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

環(huán)：

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

連通圖：

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

連通子圖：

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

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

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

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

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

鄰接矩陣

• 使用一個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即可。

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

鄰接表

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

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

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

圖的實現(xiàn)

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

圖的API設(shè)計

代碼實現(xiàn)

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

    public Graph(int V) {
        // 初始化頂點(diǎn)數(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的鏈表中，這樣頂點(diǎn)v就多了一個相鄰點(diǎn)w
        adj[v].add(w);
        //把v添加到w的鏈表中，這樣頂點(diǎn)w就多了一個相鄰點(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)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論