圖(Graph)G由兩個集合V和E組成，記為G=(V, E)，其中V是頂點的有窮非空集合，E是V中頂點偶對的有窮集合，這些頂點偶對稱為邊。V(G)和E(G)通常分別表示圖G的頂點集合和邊集合，E(G)可以為空集。若EG)為空，則圖G只有頂點而沒有邊。

子圖：假設有兩個圖G=(V,E)和G1=（V1,E1）;如果V1V，E1E，則稱G1為G的子圖。

完全圖：任意兩個頂點都有一條邊相連。（指的是無向圖）

無向完全圖和有向完全圖:對于無向圖，若具有n(n-1)/2條邊，則稱為無向完全圖；對于有向圖,若具有n(n-1)條弧,則稱為有向完全圖。

稀疏圖和稠密圖:有很少條邊或?。ㄈ鏴<nlogn)的圖稱為稀疏圖，反之稱為稠密圖

權和網(wǎng):在實際應用中，每條邊可以標上具有某種含義的數(shù)值，該數(shù)值稱為該邊上的權，這些權可以表示從一個頂點到另一個頂點的距離或耗費。這種帶權的圖通常稱為網(wǎng)。

鄰接點:對于無向圖G，如果圖的邊(v, v1)E，則稱頂點v和v1互為鄰接點，即v和v1相鄰接。

關聯(lián)（依附）：邊/弧與頂點之間的關系；邊(v, v')依附于頂點v和v1，或者說邊(v, v1)與頂點v和v1相關聯(lián)。

頂點的度：與該頂點相關聯(lián)的邊的數(shù)目，記為TD(v);在有向圖中，頂點的度等于該頂點的入度與出度之和，頂點v的入度是以v為終點的有向邊的條數(shù)，記作ID(v),頂點的出度是以v為始點的有向邊的條數(shù)，記作OD(v)。

路徑：接續(xù)的邊構成的頂點序列

路徑長度：路徑上邊或弧的數(shù)目/權值之和

回路(環(huán))：第一個頂點和最后一個頂點相同的路徑

簡單路徑：除路徑起點和終點可以相同外，其余頂點均不相同的路徑

簡單回路（簡單環(huán)）：除路徑起點和終點相同外，其余頂點均不相同的路徑。

連通：兩個頂點之間有路徑，則稱這兩個頂點是連通的。

連通圖：對于圖中任意兩個頂點都是連通的，則稱該圖是連通圖

強連通圖：在有向圖中對于任意兩個頂點是連通的，則稱該圖是強連通圖。

連通分量：指的是無向圖中的極大連通子圖（極大連通子圖意思為該子圖是G的連通子圖，將G的任何不在該子圖中的頂點加入，子圖不再連通）

強連通分量：有向圖的極大強連通子圖

極小連通子圖：該子圖是G的連通子圖，在該子圖中刪除任何一條邊子圖不再連通

連通圖的生成樹：包含無向圖所有頂點的極小連通子圖

有向樹：有一個頂點的入度為0，其余頂點的入度均為1的有向圖稱為有向樹

生成森林：對于非連通圖，由各個連通分量的生成樹的集合

圖的基本概念：

1、有向圖

若E是有向邊(也稱弧)的有限集合時，則圖G為有向圖?；∈琼旤c的有序對，記為<v, w>，其中v,w是頂點，v稱為弧尾，w稱為弧頭，<v,w>稱為從頂點v到頂點w的弧，也稱v鄰接到w，或w鄰接自v。

圖(a)所示的有向圖G可表示為：

2、無向圖

若E是無向邊(簡稱邊)的有限集合時，則圖G為無向圖。邊是頂點的無序對，記為(v, w)或(w,v),因為(v,w)=(w,v), 其中v,w是頂點?？梢哉f頂點w和頂點v互為鄰接點。邊(v, w)依附于頂點w和v，或者說邊(v, w)和頂點v, w相關聯(lián)。

圖(b)所示的無向圖G2可表示為：

無向圖是對稱的

3、完全圖（也稱簡單完全圖）

對于無向圖，∣E∣的取值范圍是0 到n ( n ? 1 ) / 2 ，有n ( n ? 1 ) / 2 條邊的無向圖稱為完全圖，在完全圖中任意兩個頂點之間都存在邊。對于有向圖，∣E∣的取值范圍是0 到n ( n ? 1 ) ，有n ( n ? 1 ) 條弧的有向圖稱為有向完全圖，在有向完全圖中任意兩個頂點之間都存在方向相反的兩條弧。

4、稠密圖、稀疏圖

邊數(shù)很少的圖稱為稀疏圖，反之稱為稠密圖。稀疏和稠密本身是模糊的概念，稀疏圖和稠密圖常常是相對而言的。一般當圖G滿足∣ E ∣ < ∣ V ∣ l o g ∣ V時，可以將G 視為稀疏圖。

5、子圖

設有兩個圖G = ( V , E ) 和G ′ = ( V ′ , E ′ ) ，若V '是V 的子集，且E ′?是E 的子集，則稱G ′ G的子圖。

6、出度、入度

出度：以尾為弧

入度：以頭為弧

對于無向圖，頂點v的度是指依附于該頂點的邊的條數(shù)，記為T D ( v )。在具有n 個頂點、e 條邊的無向圖中，

7、回路或環(huán)

第一個頂點和最后一個頂點相同

8、連通圖

圖中任意兩頂點連通，則這個圖為連通圖（它是無向圖）

9、非連通圖

如果一個圖有n個頂點和小于n-1條邊，就是非連通圖

10、生成樹

連通圖的生成樹是包含圖中全部頂點的一個極小連通子圖。若圖中頂點數(shù)為n ,則它的生成樹含有n ? 1 條邊（無向圖）

11、生成森林

一個有向圖恰有一個頂點的入度為0，其余頂點的入度均為1，則是一顆有向樹。生成森林由多個有向樹組成。

圖的存儲結構：

數(shù)組表示法：

用兩個數(shù)組分別存儲數(shù)據(jù)元素（頂點）的信息和數(shù)據(jù)元素之間的關系（邊或弧）

其中圖用0或1來表示，網(wǎng)用權或者∞來表示

網(wǎng)的鄰接矩陣：

定義：? ? ? ? ? ? ? ? ? ? ? ? ? ?

? 若<>或（）

? ? ? ? ? ? ? ? ?∞? ?反之

圖的鄰接表特點：有e條邊就會有2e個1對稱，即：

鄰接表：

鄰接表是一種常用的圖的數(shù)據(jù)結構，用于表示圖中頂點之間的關系。它通過使用鏈表來存儲每個頂點的鄰接點。

在鄰接表中，圖的頂點被表示為一個數(shù)組，數(shù)組的每個元素都是一個鏈表。鏈表中的每個節(jié)點表示一個鄰接點，節(jié)點中存儲了與該頂點相鄰的頂點的信息。

連接點域：指示與定點鄰接的點在圖中位置（下標）

鏈域：下一條邊或弧的結點

數(shù)據(jù)域：數(shù)據(jù)域存儲和邊或弧相關的信息，如權值

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?頭結點

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?表結點
?

若無向圖中有n個頂點，e條邊，則它的鄰接表需n個頭結點和2e個表結點

若有向圖中有n個頂點，e條邊，則它的鄰接表需n個頭結點和e個表結點

圖的遍歷（相當于樹）：

深度優(yōu)先搜索類似于樹的先序遍歷(廣度=層次)。如其名稱中所暗含的意思一樣，這種搜索算法所遵循的搜索策略是盡可能“深”地搜索一個圖。它的基本思想如下:首先訪問圖中某一起始頂點v，然后由v出發(fā)，訪問與v鄰接且未被訪問的任一頂點再訪問與鄰接且未被訪問的任一頂點…重復上述過程。當不能再繼續(xù)向下訪問時，依次退回到最近被訪問的頂點，若它還有鄰接頂點未被訪問過，則從該點開始繼續(xù)上述搜索過程，直至圖中所有頂點均被訪問過為止。

圖的連通性：

最小生成樹：

一顆生成樹就的代價就是樹上各代價之和。對于一個帶權連通無向圖G = ( V , E ) ，生成樹不同，其中邊的權值之和最小的那棵生成樹（構造連通網(wǎng)的最小代價生成樹），稱為G的最小生成樹。

克魯斯卡爾算法：

構造最小生成樹的過程如下圖所示。初始時為只有n個頂點而無邊的非連通圖T = V ，每個頂點自成一個連通分量，然后按照邊的權值由小到大的順序，不斷選取當前未被選取過且權值最小的邊，若該邊依附的頂點落在T中不同的連通分量上，則將此邊加入T ，否則舍棄此邊而選擇下一條權值最小的邊。以此類推，直至T 中所有頂點都在一個連通分量上。

我們將下面左圖的鄰接矩陣通過程序轉化為右圖的邊集數(shù)組，并且對它們按權值從小到大排序

拓撲排序

對一個AOV網(wǎng)進行拓撲排序的算法有很多，下面介紹比較常用的一種方法的步驟:

①從AOV網(wǎng)中選擇一個沒有前驅的頂點并輸出。
②從網(wǎng)中刪除該頂點和所有以它為起點的有向邊。
③重復①和②直到當前的AOV網(wǎng)為空或當前網(wǎng)中不存在無前驅的頂點為止。如果輸出頂點數(shù)少了，哪怕是少了一個，也說明這個網(wǎng)存在環(huán)(回路)，不是AOV網(wǎng)。
文章來源地址http://www.zghlxwxcb.cn/news/detail-773754.html

到了這里，關于數(shù)據(jù)結構第七章的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！