java圖的概念和圖的存儲

本篇內(nèi)容主要講解“java圖的概念和圖的存儲”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“java圖的概念和圖的存儲”吧!

圖的概念和圖的存儲

圖（Graph）是數(shù)據(jù)結(jié)構(gòu)中最復(fù)雜的一種結(jié)構(gòu)，線性表描述的是一對一關(guān)系，樹描述的是一對多關(guān)系，而圖描述的是多對多關(guān)系。無論是一對一還是一對多，都有一個(gè)明確的切入點(diǎn)，而圖卻不具備這種簡單的屬性。正因?yàn)榇耍P(guān)于圖的基礎(chǔ)知識也是最多，下面我們就先對這些基礎(chǔ)知識進(jìn)行梳理。

圖的概念

圖的定義

圖（Graph）是由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間邊的集合組成，通常表示為：G(V, E)，其中 G 表示一個(gè)圖， V 是圖 G 中頂點(diǎn)的集合， E 是圖 G 中邊的集合。頂點(diǎn)，就是圖中的數(shù)據(jù)元素，邊則用來表示數(shù)據(jù)之間的邏輯關(guān)系。頂點(diǎn)是有窮非空的，邊則可以為空集。

有向邊和無向邊

邊，根據(jù)是否有方向，分為無向邊和有向邊。無向邊指頂點(diǎn)v_i到v_j之間的邊沒有方向，用(v_i, v_j)表示。有向邊指頂點(diǎn)v_i到v_j之間的邊有方向，也稱作弧，用<v_i, v_j>表示，其中v_i稱為弧尾或初始點(diǎn)，v_j稱為弧頭或終端點(diǎn)，也就是箭頭從v_i指向v_j，順序不能交換。如下圖所示，左邊的圖都是無向邊，右邊的圖都是有向邊：

左圖可以表示為G₁ = (V₁, {E₁})，其中頂點(diǎn)集合V₁={A, B, C, D}，邊集合E₁={(A, B), (B, C), (C, D), (D, A), (A, C)}。右圖可以表示為G₂ = (V₂, {E₂})，其中頂點(diǎn)集合V₂={A, B, C, D}，弧集合E₂={<A, B>, <B, C>, <C, A>, <A, D>}。

有向圖和無向圖

如果圖中任意兩個(gè)頂點(diǎn)之間的邊都是無向邊，則稱該圖為無向圖。在無向圖中，如果任意兩個(gè)頂點(diǎn)之間都存在邊，則稱該圖為無向完全圖。含有 n 個(gè)頂點(diǎn)的無向完全圖有 n(n-1)/2 條邊。

同樣地，如果圖中任意兩個(gè)頂點(diǎn)之間的邊都是有向邊，則稱該圖為有向圖。在有向圖中，如果任意兩個(gè)頂點(diǎn)之間都存在方向互為相反的兩條弧，則稱該圖為有向完全圖。含有 n 個(gè)頂點(diǎn)的有向完全圖有 n(n-1) 條邊。

如下所示，左圖為無向完全圖，右側(cè)為有向完全圖：

簡單圖

在圖中，若不存在頂點(diǎn)到其自身的邊，且同一條邊不重復(fù)出現(xiàn)，則稱這樣的圖為簡單圖。我們要研究的圖都是簡單圖。如下所示，都不是簡單圖，不屬于我們學(xué)習(xí)的范疇。

稀疏圖和稠密圖

有很少條邊或弧的圖稱為稀疏圖，反之稱為稠密圖。這是一個(gè)相對的概念。

網(wǎng)

帶權(quán)的圖稱為網(wǎng)，權(quán)指的是在圖的邊或弧上的數(shù)字，例如下圖就是一張帶權(quán)的圖：

子圖

假設(shè)有兩個(gè)圖G=(V, {E})和G'=(V', {E'})，如果V'∈V且E'屬于E，則稱G'為G的子圖。簡言之，就是部分與整體的關(guān)系。

頂點(diǎn)與邊的關(guān)系

對于無向圖G=(V, {E})，如果邊(v, v')∈E，則稱頂點(diǎn) v 和 v' 互為鄰接點(diǎn)，即 v 和 v' 相鄰接，邊(v, v')依附于頂點(diǎn) v 和 v'，或者說(v, v')與頂點(diǎn) v 和 v' 相關(guān)聯(lián)。頂點(diǎn) v 的度是和 v 相關(guān)聯(lián)的邊的數(shù)目，記為TD(v)。無向圖的邊的個(gè)數(shù)和頂點(diǎn)度數(shù)的關(guān)系如下：

對于有向圖G=(V, {E})，如果弧<v, v'>∈E，則稱頂點(diǎn) v 鄰接到 v'，v' 鄰接自 v，弧<v, v'>和頂點(diǎn) v, v'相關(guān)聯(lián)。以頂點(diǎn) v 為頭的弧的數(shù)目稱為 v 的入度，記為ID(v)，以 v 為尾的弧的數(shù)目稱為 v 的出度，記為OD(v)，頂點(diǎn) v 的度為TD(v) = ID(v) + OD(v)。有向圖的弧的個(gè)數(shù)和出度、入度的關(guān)系如下：

路徑

無向圖G=(V, {E})中從頂點(diǎn) v 到 v' 的路徑是一個(gè)頂點(diǎn)序列(v=v_i,0,v_i,1,...,v_i,m=v')，其中(v_i,j-1,v_i,j)∈E，1≤j≤m。

如果是有向圖，則路徑也是有向的，頂點(diǎn)序列滿足<v_i,j-1, v_i,j>∈E，1≤j≤m。

路徑的長度是路徑上的邊或弧的數(shù)目。

第一個(gè)頂點(diǎn)到最后一個(gè)頂點(diǎn)相同的路徑稱為回路或環(huán)。序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑稱為簡單路徑。除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)之外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路，稱為簡單回路或簡單環(huán)。

連通圖

在無向圖G中，如果從頂點(diǎn) v 到 v' 有路徑，則稱 v 和 v' 是連通的。如果對于圖中的任意兩個(gè)頂點(diǎn) v_i,v_j∈V，v_i 和 v_j 都是連通的，則稱G是連通圖。無向圖中的極大連通子圖稱為連通分量。如下圖，左圖不是連通圖，但它有兩個(gè)連通分量：

在有向圖G中，如果對于每一對v_i,v_j∈V、v_i≠v_j，從 v_i 到 v_j 都存在路徑，則稱G是強(qiáng)連通圖。有向圖中的極大強(qiáng)連通子圖稱為有向圖的強(qiáng)連通分量。如下圖所示，雖然它不是強(qiáng)連通圖，但它有兩個(gè)強(qiáng)連通分量：

生成樹和有向樹

連通圖的生成樹是一個(gè)極小的連通子圖，它含有圖中全部的 n 個(gè)頂點(diǎn)，但只有足以構(gòu)成一棵樹的 n-1 條邊。如下所示，圖1是一個(gè)連通圖，圖2和圖3都是它的生成樹：

n個(gè)頂點(diǎn)和 n-1 條邊是構(gòu)成生成樹的必要條件，但是它并不充分，如下所示，就不是一個(gè)生成樹：

如果一個(gè)有向圖恰有一個(gè)頂點(diǎn)的入度為0，其余頂點(diǎn)的入度均為1，則是一棵有向樹。一個(gè)有向圖的生成森林由若干棵有向樹組成，含有圖中全部頂點(diǎn)，但只有足以構(gòu)成若干棵不相交的有向樹的弧。如下圖所示，圖1就可以拆分成圖2和圖3兩棵有向樹。

圖的存儲

線性表和圖都有一個(gè)明確的切入點(diǎn)，但是對圖而言，每個(gè)頂點(diǎn)都可以當(dāng)做是起點(diǎn)，而且每個(gè)頂點(diǎn)之間都可能有邏輯關(guān)系，也就是說，單純的使用數(shù)組或鏈表是無法完成圖的存儲的。圖的存儲當(dāng)前主要有以下五種方式：

1. 鄰接矩陣

圖的鄰接矩陣（Adjacency Matrix）存儲方式是用兩個(gè)數(shù)組來表示圖。一個(gè)一維數(shù)組存儲圖中頂點(diǎn)信息，一個(gè)二維數(shù)組（稱為鄰接矩陣）存儲圖中的邊或弧的信息。

設(shè)G有n個(gè)頂點(diǎn)，則鄰接矩陣是一個(gè)n*n的方陣，定義為：

下面，我們就無向圖、有向圖和網(wǎng)分別演示鄰接矩陣的存儲方式。

無向圖

其中主對角線的值為0，表示頂點(diǎn)到其本身沒有邊。無向圖的鄰接矩陣一定是對稱的，也就是以主對角線劃分的右上方和左下方對稱。從矩陣中我們可以獲取以下信息：

• 判斷兩個(gè)頂點(diǎn)之間是否有邊

• 獲取某個(gè)頂點(diǎn)的度，只需要求第 i 行或第 i 列的和即可。

• 獲取某個(gè)頂點(diǎn)的所有臨界點(diǎn)，只需要遍歷第 i 行即可。

有向圖

有向圖的表示和無向圖類似，如下所示：

網(wǎng)

因?yàn)榫W(wǎng)的每條邊都有權(quán)值，所以對應(yīng)的公式稍有改變，如下所示：

這里∞表示的是不可能出現(xiàn)的值。網(wǎng)的鄰接矩陣存儲示例如下：

2. 鄰接表

數(shù)組的優(yōu)缺點(diǎn)我們都已經(jīng)熟知，那么使用鄰接矩陣就一定會(huì)面臨空間浪費(fèi)的問題，上述示例中0或者∞越多，對應(yīng)圖中邊數(shù)相對于頂點(diǎn)數(shù)而言較少時(shí)，空間的使用率也就越低。鄰接表的思想和哈希表類似，使用數(shù)組結(jié)合鏈表的方式來存儲圖。

無向圖

鄰接表使用一個(gè)數(shù)組來存儲每個(gè)頂點(diǎn)，數(shù)組的每一位都包含一個(gè)鏈表，用來存儲與此頂點(diǎn)相鄰的邊，示例如下：

從鄰接表中，也可以輕易地獲取到頂點(diǎn)、邊和度的值。

有向圖

有向圖的鄰接表和無向圖類似，但是它獲取出度容易，獲取入度卻比較困難，如下所示：

獲取一個(gè)頂點(diǎn)的出度只需要計(jì)算鏈表的長度即可，但是入度卻沒有有效的獲取方式，所以通常還會(huì)建立一個(gè)逆鄰接表作為補(bǔ)充，如下所示：

網(wǎng)

用鄰接表來存儲網(wǎng)的結(jié)構(gòu)只需要增加一個(gè)weight字段即可，這里不再演示。

3. 十字鏈表

鄰接表在表示有向圖時(shí)，需要鄰接表和逆鄰接表兩張表配合使用，較為繁瑣，我們可以把鄰接表和逆鄰接表結(jié)合為一張表，這就是十字鏈表。

十字鏈表也使用數(shù)組來存儲頂點(diǎn)，只是每一位數(shù)據(jù)除了頂點(diǎn)外，還有兩個(gè)鏈表分別表示出邊表和入邊表，數(shù)據(jù)的結(jié)構(gòu)如下所示：

邊表的結(jié)構(gòu)也有所改變，結(jié)構(gòu)如下：

其中，tailvex表示弧起點(diǎn)在頂點(diǎn)表的下標(biāo)，headvex表示弧終點(diǎn)在頂點(diǎn)表的下標(biāo)，headlink是入邊表指針域，指向下一個(gè)終點(diǎn)相同的邊，taillink是出邊表指針域，指向下一個(gè)起點(diǎn)相同的邊。

接下來，我們以下圖為例，演示十字鏈表的建立過程：

首先，把全部頂點(diǎn)存儲起來，如下所示：

然后，我們建立頂點(diǎn)v₀的出邊表，可以發(fā)現(xiàn)只有<v₀, v₃>這一條邊，所以它的出邊表如下：

同理，其他頂點(diǎn)的出邊表如下：

現(xiàn)在，我們來建立入邊表，對于頂點(diǎn)v₀，它的入邊有兩條，分別是<v₁, v₀>和<v₂, v₀>?？梢钥吹?，這兩個(gè)邊在出邊表中已經(jīng)存在了，直接為其建立起關(guān)系即可，如下所示：

同理建立起其他頂點(diǎn)的入邊表，結(jié)果如下：

可以看到，十字鏈表除了結(jié)構(gòu)較為復(fù)雜之外，不僅解決了鄰接表無法同時(shí)獲取入度和出度的問題，也沒有增加所需的時(shí)間復(fù)雜度等，因此十分適合有向圖的存儲。

4. 鄰接多重表

十字鏈表是針對有向圖的優(yōu)化，而鄰接表在表示無向圖時(shí)也存在一定的問題。比如我們要把下圖的邊(v₂, v₀)刪除，在鄰接表中就要?jiǎng)h除兩個(gè)位置：

可以看到，這是因?yàn)閿?shù)據(jù)的重復(fù)造成的，所以我們可以仿照十字鏈表的方式構(gòu)造一個(gè)鄰接多重表，來解決以上問題。為此，需要重新定義邊表結(jié)構(gòu)，如下：

其中，ivex和jvex是某條邊依附的兩個(gè)頂點(diǎn)在頂點(diǎn)表的下標(biāo)，ilink表示依附于頂點(diǎn)ivex的下一條邊，jlink表示依附于頂點(diǎn)jvex的的下一條邊。

有了十字鏈表的經(jīng)驗(yàn)，構(gòu)建一個(gè)鄰接多重表十分容易，我們以上圖為例，首先建立好頂點(diǎn)結(jié)點(diǎn)和邊表結(jié)點(diǎn)，如下所示：

這里需要注意的是，邊表的每個(gè)結(jié)點(diǎn)僅出現(xiàn)一次，接下來我們按照規(guī)定把這些結(jié)點(diǎn)間關(guān)系連接起來即可，如下所示：

5. 邊集數(shù)組

如果我們僅關(guān)注邊的操作，還可以使用邊集數(shù)組，它由兩個(gè)一維數(shù)組組成，一個(gè)數(shù)組用來存儲頂點(diǎn)的信息，另一個(gè)數(shù)組存儲邊的信息。邊的數(shù)組的每個(gè)元素都由一條邊的起點(diǎn)下標(biāo)、終點(diǎn)下標(biāo)和權(quán)組成。這個(gè)存儲方式主要用于尋找連通網(wǎng)的最小生成樹算法：克魯斯卡爾算法。

到此，相信大家對“java圖的概念和圖的存儲”有了更深的了解，不妨來實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！