資料結構之

圖

1. 圖的定義

圖（graph） 是由一些點（vertex） 和這些點之間的連線（edge） 所組成的；其中，點通常稱為頂點（vertex），而點到點之間的連線通常稱之為邊或者弧（edge）。通常記為G=（V,E）；

要注意的是：線性表可以是空表，樹可以是空樹，圖不可以是空圖，圖可以沒有邊，但是至少要有一個頂點。

2. 圖的組成

圖由兩種類型的元素組成，頂點和邊，有時候，有向圖的邊也稱為弧。

• 頂點代表對象，邊則建立起對象之間的關系或關聯。
• 入度就是進入該頂點邊的數目，出度就是離開這個頂點邊的數目，有向圖的度就是入度加出度。
• 邊是頂點之間的邏輯關系表示，邊集可以是空的

3. 圖的分類

• 有向圖和無向圖。

  

  • 有向圖中，邊是由兩個頂點組成的有序對，具有特定的方向。形象地說，有向圖可以由頂點和帶方向的箭頭所組成的圈繪制出來。
  • 無向圖中，邊是沒有方向的，是以，無向圖的邊就直接用線段來代替箭頭表示
• 完全圖

  

  • 完全圖如果任意兩個頂點之間都存在邊叫完全圖，而有向的邊叫有向完全圖。
  • 當一個圖接近完全圖時，則稱它為稠密圖（Dense Graph），而當一個圖含有較少的邊時，則稱它為稀疏圖。
• 連通圖

  

  • 無向圖中，兩頂點有路徑存在，就稱為連通的。若圖中任意兩頂點都連通，同此圖為連通圖。
• 無權圖和帶權圖

  

  • 對圖中的邊賦予具有一定意義的數值(路程、費用等等)的圖稱為帶權圖

4. 圖的存儲結構

• 鄰接矩陣

  

  • 鄰接矩陣用兩個數組儲存資料。一個一維數組存儲圖中頂點資訊，一個二維數組（鄰接矩陣）存儲圖中邊的資訊。
  • 頂點v1 和頂點v3 之間存在一條邊， 則稱頂點v1 和3 互為鄰接點。
  • 有向圖鄰接矩陣

    

  • 無向圖鄰接矩陣

    

  • 0 表示這兩個頂點之間沒有邊，1 表示有邊
  • 對應行非0元素的個數是出度；對應列非0元素的個數是入度
  • 優點： 可以快速判斷兩個頂點之間是否存在邊，可以快速添加邊或者删除邊。
  • 缺點： 由于存在n個頂點的圖需要n*n個數組元素進行存儲，當圖為稀疏圖時，使用鄰接矩陣存儲方法将會出現大量0元素，這會造成極大的空間浪費。
  • 實作代碼

5. 深度優先搜尋

• 深度優先搜尋在搜尋過程中每當通路到某一個頂點後，需要遞歸地通路此頂點的所有未通路過的相鄰頂點。因而，這種搜尋将盡可能深地持續探索，直到無法繼續為止。

6. 廣度優先搜尋

• 廣度優先搜尋在進一步探索圖中的頂點之前，先通路目前頂點的所有鄰接頂點。

最小生成樹

• Kruskal 算法

  

  • 此算法可以稱為“加邊法”，初始最小生成樹邊數為0，每疊代一次就選擇一條滿足條件的最小代價邊，加入到最小生成樹的邊集合裡。
• Prim 算法

  

  • 此算法可以稱為“加點法”，每次疊代選擇代價最小的邊對應的點，加入到最小生成樹中。算法從某一個頂點A開始，逐漸長大覆寫整個連通網的所有頂點。