資料結構之圖

圖是由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為:G(V.E),其中，G表示一個圖，V是圖G中頂點的集合，E是圖G中邊的集合。

需要注意的幾個地方:

1.線性表中我們把資料元素叫元素，樹中将資料元素叫結點，在圖中資料元素，我們則稱之為頂點。

2.線性表中可以沒有資料元素，稱為空表。樹中可以沒有結點，叫做空樹。在圖結構中，不允許沒有頂點。在定義中，若V是頂點的集合，則強調了頂點集合V有窮非空。

3.線性表中，相鄰的資料元素之間具有線性關系，樹結構中，相鄰兩層的結點具有層次關系，而圖中，任意兩個頂點之間都可能有關系，頂點之間的邏輯關系用邊來表示，邊集可以為空。

各種圖定義

無向邊:若頂點vi到vj之間的邊沒有方向，則稱這條邊為無向邊，用無序偶對來表示。  例如 G1=(V1,{E1}) 頂點集合V1{A,B,C,D} 邊集合E1={(A,B)(B,C)(C,D)(D,A)(A,C)}

有向邊:若從頂點vi到vj的邊有方向，則稱這條邊為有向邊，也稱為弧

用有序偶<vi，vj>來表示，vi稱為弧尾，vj稱為弧頭。如果圖中任意兩個頂點之間的邊都是有向邊，則該圖為有向圖。

G2=(V2，{E2}) 其中頂點集合V2{A,B,C,D} 弧集合E2={<A,D><B,A><C.A><B,C>}

無向邊用()表示  有向邊用<>表示

在圖中，若不存在頂點到其自身的邊，且同一條邊不重複出現，則稱這樣的圖為簡單圖。

在無向圖中，如果任意兩個頂點之間都存在邊，則稱該圖為無向完全圖。

在有向圖中，如果任意兩個頂點之間都存在方向互為相反的兩條弧，則稱該圖為有向完全圖。

有很少條邊或弧的圖稱為稀疏圖

有些圖的邊或弧具有與它相關的數字，這種與圖的邊或弧相關的數叫做權

帶權的圖通常稱為圖

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

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

連通圖   

連通分量:無向圖中的極大連通子圖

1.要是子圖

2.子圖要是連通的

3.連通子圖含有極大頂點數

4.具有極大頂點數的連通子圖包含依附于這些頂點的所有邊

在有向圖G中，如果對于每一對vi，vj屬于V，vi不等于vj，從vi到vj和從vj到vi都存在路徑，則稱G是強連通圖。有向圖中的極大強連通子圖稱做有向圖的強連通分量。

      本文轉自潘闊 51CTO部落格，原文連結：http://blog.51cto.com/pankuo/1631338，如需轉載請自行聯系原作者