java圖的概念和圖的存儲

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

圖的概念和圖的存儲

圖（Graph）是數據結構中最復雜的一種結構，線性表描述的是一對一關系，樹描述的是一對多關系，而圖描述的是多對多關系。無論是一對一還是一對多，都有一個明確的切入點，而圖卻不具備這種簡單的屬性。正因為此，關于圖的基礎知識也是最多，下面我們就先對這些基礎知識進行梳理。

圖的概念

圖的定義

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

有向邊和無向邊

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

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

有向圖和無向圖

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

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

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

簡單圖

在圖中，若不存在頂點到其自身的邊，且同一條邊不重復出現，則稱這樣的圖為簡單圖。我們要研究的圖都是簡單圖。如下所示，都不是簡單圖，不屬于我們學習的范疇。

稀疏圖和稠密圖

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

網

帶權的圖稱為網，權指的是在圖的邊或弧上的數字，例如下圖就是一張帶權的圖：

子圖

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

頂點與邊的關系

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

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

路徑

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

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

路徑的長度是路徑上的邊或弧的數目。

第一個頂點到最后一個頂點相同的路徑稱為回路或環。序列中頂點不重復出現的路徑稱為簡單路徑。除了第一個頂點和最后一個頂點之外，其余頂點不重復出現的回路，稱為簡單回路或簡單環。

連通圖

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

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

生成樹和有向樹

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

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

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

圖的存儲

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

1. 鄰接矩陣

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

設G有n個頂點，則鄰接矩陣是一個n*n的方陣，定義為：

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

無向圖

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

• 判斷兩個頂點之間是否有邊

• 獲取某個頂點的度，只需要求第 i 行或第 i 列的和即可。

• 獲取某個頂點的所有臨界點，只需要遍歷第 i 行即可。

有向圖

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

網

因為網的每條邊都有權值，所以對應的公式稍有改變，如下所示：

這里∞表示的是不可能出現的值。網的鄰接矩陣存儲示例如下：

2. 鄰接表

數組的優缺點我們都已經熟知，那么使用鄰接矩陣就一定會面臨空間浪費的問題，上述示例中0或者∞越多，對應圖中邊數相對于頂點數而言較少時，空間的使用率也就越低。鄰接表的思想和哈希表類似，使用數組結合鏈表的方式來存儲圖。

無向圖

鄰接表使用一個數組來存儲每個頂點，數組的每一位都包含一個鏈表，用來存儲與此頂點相鄰的邊，示例如下：

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

有向圖

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

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

網

用鄰接表來存儲網的結構只需要增加一個weight字段即可，這里不再演示。

3. 十字鏈表

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

十字鏈表也使用數組來存儲頂點，只是每一位數據除了頂點外，還有兩個鏈表分別表示出邊表和入邊表，數據的結構如下所示：

邊表的結構也有所改變，結構如下：

其中，tailvex表示弧起點在頂點表的下標，headvex表示弧終點在頂點表的下標，headlink是入邊表指針域，指向下一個終點相同的邊，taillink是出邊表指針域，指向下一個起點相同的邊。

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

首先，把全部頂點存儲起來，如下所示：

然后，我們建立頂點v₀的出邊表，可以發現只有<v₀, v₃>這一條邊，所以它的出邊表如下：

同理，其他頂點的出邊表如下：

現在，我們來建立入邊表，對于頂點v₀，它的入邊有兩條，分別是<v₁, v₀>和<v₂, v₀>。可以看到，這兩個邊在出邊表中已經存在了，直接為其建立起關系即可，如下所示：

同理建立起其他頂點的入邊表，結果如下：

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

4. 鄰接多重表

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

可以看到，這是因為數據的重復造成的，所以我們可以仿照十字鏈表的方式構造一個鄰接多重表，來解決以上問題。為此，需要重新定義邊表結構，如下：

其中，ivex和jvex是某條邊依附的兩個頂點在頂點表的下標，ilink表示依附于頂點ivex的下一條邊，jlink表示依附于頂點jvex的的下一條邊。

有了十字鏈表的經驗，構建一個鄰接多重表十分容易，我們以上圖為例，首先建立好頂點結點和邊表結點，如下所示：

這里需要注意的是，邊表的每個結點僅出現一次，接下來我們按照規定把這些結點間關系連接起來即可，如下所示：

5. 邊集數組

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

到此，相信大家對“java圖的概念和圖的存儲”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！