iT邦幫忙

2021 iThome 鐵人賽

DAY 27
0
自我挑戰組

從0開始啃Introduction of algorithms心得與記錄系列 第 27

Day-27 圖論(Graph)基本概念

圖(Graph)的表示

圖(Graph)

圖,是一種記錄節點和節點之間關連的表示法。對於圖https://chart.googleapis.com/chart?cht=tx&chl=G%3D(V%2CE),表示https://chart.googleapis.com/chart?cht=tx&chl=G是由https://chart.googleapis.com/chart?cht=tx&chl=V集合和https://chart.googleapis.com/chart?cht=tx&chl=E集合共同構成的集合,https://chart.googleapis.com/chart?cht=tx&chl=V集合中的元素為圖中的節點,故又稱點集合。https://chart.googleapis.com/chart?cht=tx&chl=E表示節點和節點之間的邊所構成的集合,每一個邊可以當作純量或是向量,故又稱為邊集合。

圖,可以用兩種方式是表示,一種方法類似前面Hash table中Chaining的表示法,每一個slot中含有一個鏈結串列,這個方法稱為鄰接串列(Adjacency list)表示,另一種方法為使用鄰接矩陣(Adjacency Matrix)來表示。

而節點和節點之間,我們可以根據其走訪的性質,定義他是有向圖(Directed),還是無向圖(Undirected),也就是節點和節點之間的邊,是以線段來表示,還是以向量來表示。

對於圖https://chart.googleapis.com/chart?cht=tx&chl=G%3D(V%2CE),使用鄰接串列表示法包含有https://chart.googleapis.com/chart?cht=tx&chl=V條串列的陣列https://chart.googleapis.com/chart?cht=tx&chl=Adj所構成,陣列中每一個元素中有一條串列。對於每一個屬於https://chart.googleapis.com/chart?cht=tx&chl=V集合的https://chart.googleapis.com/chart?cht=tx&chl=u節點,https://chart.googleapis.com/chart?cht=tx&chl=Adj%5Bu%5D包含所有與節點https://chart.googleapis.com/chart?cht=tx&chl=u有邊相連的節點,或是可以稱為https://chart.googleapis.com/chart?cht=tx&chl=u的鄰居,而鄰接矩陣也是使用差不多的概念,給定一個無向圖,我們可以以下面兩種方式進行表示

在圖(a)中,我們可以知道點集合為https://chart.googleapis.com/chart?cht=tx&chl=V%20%3D%20%5Cbegin%7BBmatrix%7D1%2C2%2C3%2C4%2C5%5Cend%7BBmatrix%7D, 邊集合https://chart.googleapis.com/chart?cht=tx&chl=E%20%3D%20%5Cbegin%7BBmatrix%7D(1%2C2)%2C(1%2C5)%2C(2%2C3)%2C(2%2C4)%2C(2%2C5)%2C(3%2C2)%2C(3%2C4)...%5Cend%7BBmatrix%7D,如果在實務上,我們直接使用https://chart.googleapis.com/chart?cht=tx&chl=E集合來尋找和1節點有關連的所有節點,我們就必須遍歷整個https://chart.googleapis.com/chart?cht=tx&chl=E集合,需要線性時間,因此我們會使用上面提及的鄰接串列法或是鄰接矩陣法來進行處理。

我們可以對鄰接串列表示法做出一點修改,為每一條邊加上權重,那麼,所產生出的圖就是權重圖。我們可以將權重儲存在鏈結串列中的每一個節點當中,當作是一個節點的屬性。而這種表示法具有一些可靠性與安全性在一些系統應用中,像是輸入錯誤或是系統崩潰等等,也具有一定的方便修改性,可以進行一些簡單的修改就讓他支援其他圖的形式與操作。

鄰接串鍊有幾個缺點,那就是我們無法快速的判斷一條邊是否為圖中的邊,且和鄰接矩陣相比,每一個節點需要更多的儲存空間,包含一個整數,和下一個節點位置的指標。

而鄰接矩陣的優點在於矩陣中每一個元素都只需要1 bit就可以表示,只需奧表示有沒有節點就可以了,但是也有一個缺點,當發生很多元素,但卻很少邊的情況,會浪費掉許多空間。

當圖的規模較小時,我們會優先使用鄰接矩陣。

圖的表示


上圖A,B,C等節點,我們會稱為圖的節點或是頂點(Vertex or Node),節點與節點之間相連的稱為邊,這個範例中,邊是屬於沒有方向的,因此,這是一張無向圖。邊上的數字表示權重。


上面這張圖,如果以鄰接矩陣的方式表示,可以表示成下面這個樣子

int map[5][5]=
{ {0,0,1,1,1}
  {0,0,0,0,1}
  {1,0,0,0,1}
  {1,0,0,0,0}
  {1,1,1,0,0}
};

說明: 以第一行{0,0,1,1,1}為例子,表示0這個節點,和2,3,4節點有存在邊的關係。其實我們可以指細觀察,上面這個二為矩陣其實存在一種對稱關係,以方陣的對角線為對稱軸,這個性質可以使我們使用一些技巧,花費更少的空間,去記住節點和邊之間的關係。


以這個圖為例子,我們可以使用鄰接矩陣,來表示這個具有權重的圖

int map[5][5] =
{ {0,1,6,INT_MAX,INT_MAX}
  {1,0,4,3,1}
  {6,4,0,1,INT_MAX}
  {INT_MAX,3,1,0,1}
  {INT_MAX,1,INT_MAX,1,0}
};

說明: 以第一行{0,1,6,INT_MAX,INT_MAX}為例,表示0這個節點和其他節點之間的權重,如果不存在,則以一個標示符號作為表示。

如果以串列的形式,則為以下

struct edge {
    int id;
    int weight;
    struct node *next;
};
struct map[5]

參考資料:Introduction to algorithms 3rd, 北一女資訊集訓


上一篇
Day-26 Hash Table-開放定址(Open Addressing)
下一篇
Day-28 Breadth-First Search(BFS), 廣度優先搜尋
系列文
從0開始啃Introduction of algorithms心得與記錄30

尚未有邦友留言

立即登入留言