java圖的概念和圖的存儲

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

錦江網(wǎng)站制作公司哪家好，找創(chuàng)新互聯(lián)建站！從網(wǎng)頁設(shè)計、網(wǎng)站建設(shè)、微信開發(fā)、APP開發(fā)、響應(yīng)式網(wǎng)站等網(wǎng)站項目制作，到程序開發(fā)，運營維護(hù)。創(chuàng)新互聯(lián)建站2013年至今到現(xiàn)在10年的時間，我們擁有了豐富的建站經(jīng)驗和運維經(jīng)驗，來保證我們的工作的順利進(jìn)行。專注于網(wǎng)站建設(shè)就選創(chuàng)新互聯(lián)建站。

圖的概念和圖的存儲

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

圖的概念

圖的定義

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

有向邊和無向邊

邊，根據(jù)是否有方向，分為無向邊和有向邊。無向邊指頂點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) 條邊。

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

簡單圖

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

稀疏圖和稠密圖

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

網(wǎng)

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

子圖

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

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

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

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

路徑

無向圖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。

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

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

連通圖

在無向圖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 個頂點，但只有足以構(gòu)成一棵樹的 n-1 條邊。如下所示，圖1是一個連通圖，圖2和圖3都是它的生成樹：

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

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

圖的存儲

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

1. 鄰接矩陣

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

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

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

無向圖

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

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

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

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

有向圖

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

網(wǎng)

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

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

2. 鄰接表

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

無向圖

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

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

有向圖

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

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

網(wǎng)

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

3. 十字鏈表

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

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

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

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

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

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

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

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

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

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

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

4. 鄰接多重表

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

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

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

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

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

5. 邊集數(shù)組

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

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

當(dāng)前標(biāo)題：java圖的概念和圖的存儲
網(wǎng)頁鏈接：http://muchs.cn/article38/iidosp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供虛擬主機、App設(shè)計、網(wǎng)站建設(shè)、網(wǎng)站改版、電子商務(wù)、網(wǎng)站設(shè)計

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)