圖形結構(C++)
本單元目錄大綱
一、圖形資料結構與圖形走訪
二、實作圖形資料結構
三、使用深度優先進行圖的走訪
四、使用寬度優先進行圖的走訪
一、圖形資料結構與圖形走訪
圖形資料結構是由點與邊所組成,圖形資料結構廣泛應用於程式的實作,許多問題都可以轉換成圖形資料結構,例如:使用網路地圖搜尋最短路徑,可將地點轉換成圖形資料結構中的點,地點與地點間的距離轉換成邊的權重,最後使用最短路徑演算法就可以找出最短路徑。
在棋盤中要找出走到某一點是否有路徑可以到達,要花費幾步到達,也可以轉換成圖形資料結構,將棋盤中位置轉換成圖形結構中的點,棋子下一步可以到達的棋盤位置,這就是另一個點,若可以到達另一個點隱含兩點有邊相連,下一個點再找下一個可以到達的點,兩點又形成邊,如此直到走完棋盤所有點,或沒有點可以走,最後判斷是否可以到達目標點。以下介紹圖形資料結構的定義、程式實作與範例應用。
(一)簡介圖形資料結構
什麼是圖形資料結構
圖形資料結構的定義為由點與邊所組成,邊為連結圖形中兩點,可以有循環(cycle),也可以有點不跟其他點相連,樹狀資料結構是圖形資料結構的特例。
圖形資料結構分成有向圖與無向圖,有向圖就是單行道的意思,假設點1與點2,只允許點1連結到點2,不允許點2回到點1,通常使用箭頭的邊表示有向圖,無向圖是指邊允許雙向通行,通常使用沒有箭頭的邊表示。
(二)圖形資料結構的名詞定義
介紹一些圖形資料結構的名詞定義,以下圖為範例進行說明。
(1)點(node):圖形中的點,上圖中有點1、點2、點3、點4與點5。。
(2)邊(edge):兩個點之間可以有邊相連,上圖中的邊有(1,2)、(1,3)、(1,4)、(2,3)、(2,4)、(2,5)六個邊。
(3)路徑(path):兩點之間可以由許多邊連接起來,上圖中的點1與點4的連接,可以由點1連接到點3的邊(1,3),點3再連接到點2的邊(3,2),點2再連接到點4的邊(2,4),這樣就是一個連接點1到點4的路徑。
(4)路徑長度(path length):一個路徑所包含的邊的個數。
(5)簡單路徑(simple path):一個路徑的起點與終點外,其餘點都不能相同。
(6)循環(cycle):是簡單路徑,且路徑的起點與終點相同。
(7)子圖(subgraph):G2是G1的子圖,G2的出現過的點與邊,G1也有相同的點與邊。
(8)完整圖(complete graph)
無向的完整圖,每個點都有一個邊與其他點相連,n個點無向的完整圖,邊的數量需達到(n(n-1))/2個邊,如下圖。
有向的完整圖,每個點都有一個邊與其他點相連,且雙向要能連通,n個點有向的完整圖,邊的數量需達到n*(n-1)個邊,如下圖。
(9)連通(connected):無向圖中任兩點都有邊相連。
(10)強連通(strongly connected):有向圖中任兩點都有邊相連,且雙向皆可連通,雙向可連通是指圖上任兩點點i與點j,點i可以連到點j,且點j也可以連到點i。下圖為強連通圖。
(11)分支度(degree):無向圖中連接到該頂點的邊的個數稱作分支度,下圖的點1的分支度為3,點3分支度為2,點5分支度為1。
(12)入分支度(in degree)與出分支度(out degree)
有向圖中進入該頂點的邊個數稱作入分支度,離開該頂點的邊個數稱作出分支度。點1的入分支度為3,出分支度為2,分支度為5,而點4的出分支度為1,入分支度為0,分支度為1。
二、實作圖形資料結構
實作圖形資料結構的程式碼讓讀者可以更加瞭解圖形資料結構,並介紹圖形資料結構的走訪,如何利用程式走過每個節點。
(一)使用陣列建立圖形資料結構
可以使用陣列建立圖形資料結構,如下圖形資料結構範例,本範例圖形結構有5個節點,可以使用5x5的陣列儲存下圖。
若有邊相連,則陣列元素值改為1,否則陣列元素值改為0。由下表可知無向圖一定是對稱陣列,因為點x可以連到點y,點y一定可以連回點x。
有向圖也可以使用陣列建立圖形資料結構,如下圖形資料結構範例,本範例圖形結構有4個節點,可以使用4x4的陣列儲存下圖。
若有邊相連,則陣列元素值改為1,否則陣列元素值改為0。
C++程式碼
圖形資料結構使用陣列表示有什麼優缺點?使用陣列表示圖形資料結構的優點是程式撰寫容易。那什麼情況下適合使用陣列表示圖形資料結構?
若圖形資料結構接近完整圖,就可以使用陣列進行圖形資料結構的建立,不會浪費太多空間,若圖形資料結構有許多的邊都不存在,使用陣列就會造成空間浪費,可以使用deque陣列方式建立圖形資料結構,不會造成浪費太多空間,圖形中有邊存在才需要記錄在deque陣列,不須使用陣列預留所有邊的空間,減少記憶體空間的使用。
(二)使用deque陣列建立圖形資料結構
圖形資料結構也可以使用指標所建立鏈結串列陣列進行儲存,鏈結串列需要一個指標指向下一個元素,再把這樣的結構宣告為陣列,圖形資料結構的結構宣告如下。結構陣列head中每個元素都是鏈結串列,可以串接多個點。
如果要將下圖使用鏈結串列陣列方式建立圖形資料結構。
鏈結串列陣列head的示意圖如下。
但使用鏈結串列陣列表示圖形資料結構的程式有些複雜,可不可以有其他方法取代,可以使用deque陣列取代,雖然會浪費較多空間,但使用deque陣列取代鏈結串列陣列head,在程式碼撰寫上可以比較容易,也較容易閱讀,程式碼執行效率也不差。
C++程式碼
三、使用深度優先進行圖的走訪
在圖形的走訪過程中,以深度為優先進行走訪,稱作深度優先搜尋,如下圖,以下範例使用深度優先搜尋,從點0開始,依照未走訪過的節點中數字由小到大順序進行走訪。
(1)點0中有邊連接的點有點1、點2與點3,則點1數字最小,則由點0走訪到點1。
(2)接著點1中有邊連接的點有點0、點2、點3與點4,因為點0已經走訪過,所以下一個點先選點2,則由點1走訪到點2。
(3)接著點2中有邊連接的點有點0、點1與點3,因為點0與點1已經走訪過,所以下一個點先選點3,則由點2走訪到點3。
(4)接著點3中有邊連接的點有點0、點1與點2,點0、點1與點2都已經走訪過,所以倒退回點2。
(5)點2的所有點也都走訪過,所以倒退回點1。
(6)接著點1中有邊連接的點有點0、點2、點3與點4,因為點0、點2與點3已經走訪過,所以下一個點先選點4,則由點1走訪到點4。
(7)接著點4中有邊連接的點只有點1,因為點1已經走訪過,所以倒退回點1。
(8)接著點1中有邊連接的點有點0、點2、點3與點4,已經都走訪過,所以倒退回點0,程式結束。
深度優先搜尋是以遞迴呼叫的方式來實作,最近走訪的點要優先走訪,需要使用堆疊來暫存最近使用過的點,遞迴呼叫過程中會自動使用系統堆疊,就不需要自行撰寫堆疊程式,讓程式更加簡潔。找出圖形中的最長路徑長度,是否有循環(cycle)在圖形中,那些點可以連通等訊息都可以使用深度優先搜尋來完成,甚至看起來與圖形無關的問題,也可以轉換成圖形,進行深度優先搜尋找出答案來,以下介紹一些深度優先搜尋的範例。
(一)使用DFS求最長路徑長度
給定最多200個節點以內的無向圖,每個節點名稱都是英文字串組成,且節點名稱皆不相同,節點與節點之間可能有邊相連,求可以連接的最長路徑的邊的個數。
輸入說明
輸入正整數n,表示圖形中有n個點,接著下一行輸入m表示有m個邊,接下來有m行,每個邊輸入兩個節點名稱,表示有邊連接這兩個節點,最後一行輸入起始點的節點名稱。
輸出說明
輸出最長路徑的長度。
範例輸入
5
4
ax bx
bx cx
dx cx
cx ex
ax
範例輸出
3
(a)解題想法
使用map將節點名稱轉成節點編號,將節點編號加入deque陣列中,將圖形資料結構以deque陣列表示,最後使用深度優先搜尋,找出最長邊的個數。
(b)程式碼
(c)程式結果預覽
按下「執行->編譯並執行」,結果顯示在螢幕如下。
(二)使用DFS偵測是否有迴圈
給定最多26個節點以內的有向圖,每個節點名稱都是英文大寫字母,且節點名稱皆不相同,節點與節點之間可能有邊相連,求是否已經形成循環。
輸入說明
輸入正整數n,表示圖形中有n個邊,接著的n行,每行輸入兩個英文大寫字母,假設兩個英文大寫字母為A與B,表示有一個由A到B的有向邊。
輸出說明
若圖中有循環,則輸出「形成循環」,否則輸出「沒有形成循環」。
範例輸入
3
A D
D B
B C
4
A B
B C
C B
D F
範例輸出
沒有形成循環
形成循環
(a)解題想法
先將節點名稱減去大寫字母A轉成節點編號,將節點編號加入deque陣列中,將圖形資料結構以deque陣列表示,最後將所有點都使用深度優先搜尋,找出是否會回到起始點。
(b)程式碼
(c)程式結果預覽
按下「執行->編譯並執行」,結果顯示在螢幕如下。
四、使用寬度優先進行圖的走訪
除了深度優先搜尋外,圖形資料結構另一個常用的走訪演算法為寬度優先搜尋,這兩個演算法都可以走訪所有有邊相連的節點,只是走訪的順序不相同而已,寬度優先搜尋使用佇列暫存下一個要走訪的節點,而深度優先搜尋使用堆疊儲存倒退回來時的下一個要走訪的節點。
以下範例使用寬度優先搜尋,從點0開始,依照未走訪過的節點中數字由小到大順序進行走訪,將點0加入到佇列中。
寬度優先搜尋是以佇列來實作,以發現點的先後順序來儲存點到佇列中,再依序取出進行走訪。甚至看起來與圖形無關的問題,也可以轉換成圖形,進行廣度優先搜尋找出答案來,例如:在迷宮中走到出口的最少步數,下棋時移到某一點的最少步數等,以下介紹一些廣度優先搜尋的範例。
(一)迷宮
給定最多100列100行的迷宮,數字1表示通道,數字0表示牆壁,請找出迷宮中指定的起始點到所有通道的最少步數,保證迷宮所有通道一定相連,請寫一個程式列出迷宮中每一個通道距離起始點的最少步數。
舉例如下,以下為5列6行的迷宮,1表示通道,0表示牆,若設定第3列第4行為起始點,請計算到達迷宮所有通道的最少步數。
輸入說明
輸入正整數r與c,表示迷宮中有r列與c行,接著輸入r行,每行有c個數字,每個數字不是0就是1,1表示迷宮的通道,0表示牆壁,接著輸入起始點座標的列數與行數。
輸出說明
請輸出r列c行個數字,顯示迷宮所有點所到達的最少步數,且起始點的步數設定為1,牆壁部分以0表示,顯示結果請參考範例輸出。
範例輸入
5 6
0 1 1 1 1 0
0 0 1 1 0 0
0 1 1 1 0 0
1 1 1 1 0 1
1 1 1 1 1 1
3 4
範例輸出
0 5 4 3 4 0
0 0 3 2 0 0
0 3 2 1 0 0
5 4 3 2 0 6
6 5 4 3 4 5
(a)解題想法
使用寬度優先搜尋,先將起始點設定最少步數為1,將起始點加入佇列,從佇列中取出最前面的元素,考慮這元素相鄰的點,若相鄰點是通道,且未走訪過與未超出邊界,則將這些相鄰點的步數設定為取出點的步數加1,將這些相鄰點加入佇列,不斷重複上述動作直到佇列是空的為止,過程中更新最少步數的同時,要記錄最少步數到二維陣列,輸出此二維陣列就可以獲得結果。
(b)程式碼
(c)程式結果預覽
按下「執行->編譯並執行」,結果顯示在螢幕如下。
(二)象棋馬的移動
給定最多20列20行的棋盤,請找出棋盤上所指定馬的位置到棋盤上所有點的最少步數,請寫一個程式列出棋盤上每一個點的最少步數。象棋的馬走法如下。
輸入說明
輸入正整數r與c,表示棋盤中有r列與c行,接著輸入兩個整數sr與sc表示馬起始位置的列數與行數。
輸出說明
請輸出r列c行個數字,顯示棋盤中所有點所到達的最少步數,且起始點的步數設定為1,顯示結果請參考範例輸出。
範例輸入
10 10 4 6
範例輸出
5 4 3 4 3 4 3 4 3 4
4 3 4 5 2 3 2 5 4 3
5 4 3 2 3 4 3 2 3 4
4 3 4 3 4 1 4 3 4 3
5 4 3 2 3 4 3 2 3 4
4 3 4 5 2 3 2 5 4 3
5 4 3 4 3 4 3 4 3 4
4 5 4 3 4 3 4 3 4 5
5 4 5 4 5 4 5 4 5 4
6 5 4 5 4 5 4 5 4 5
(a)解題想法
使用寬度優先搜尋,先將起始點設定最少步數為1,將起始點加入佇列,從佇列中取出最前面的元素,考慮這元素相鄰的點,若相鄰點未走訪過與未超出邊界,則將這些相鄰點的步數設定為取出點的步數加1,將這些相鄰點加入佇列,不斷重複上述動作直到佇列是空的為止,過程中更新最少步數的同時,要記錄最少步數到二維陣列,輸出此二維陣列就可以獲得結果。
(b)程式碼
(三)有障礙物的馬
給定最多500列500行的棋盤,棋盤左上角座標為(0,0),右下角座標為(499,499),棋盤上的馬不能走到障礙物的點,且有拐馬腳的限制,例如若障礙物出現在下圖A的位置,則馬不能走向點1與點2;若障礙物出現在下圖B的位置,則馬不能走向點3與點4;若障礙物出現在下圖C的位置,則馬不能走向點5與點6;若障礙物出現在下圖D的位置,則馬不能走向點7與點8,這樣的限制稱作拐馬腳。請找出棋盤上所指定馬的起始位置到目標位置,是否有路徑到達,若有路徑可以到達,請輸出最少步數,若沒有路徑到達,請輸出「無法到達」。
下圖有三個障礙物,座標為(1,3)、(2,3)與(3,3),起始點為(1,2),目標點為(3,6),若起始點的步數為1,則起始點到達目標點最少步數為5。
下圖有四個障礙物,座標為(1,3)、(2,0)、(2,1)與(2,2),起始點為(1,2),目標點為(3,6),起始點無法到達目標點。
輸入說明
輸入正整數n,表示棋盤上有幾個障礙物,接著輸入n行,每行兩個數字代表障礙物座標的列數與行數,接著輸入兩個整數sr與sc表示馬起始位置的列數與行數,最後輸入兩個整數tr與tc表示馬目標位置的列數與行數。
輸出說明
請輸出到達目標位置的最少步數,起始點的步數為1,若無法到達請輸出「無法到達」。
範例輸入
第一組測資
3
1 3
2 3
3 3
1 2
3 6
第二組測資
4
1 3
2 0
2 1
2 2
1 2
3 6
範例輸出
第一組測資結果
5
第二組測資結果
無法到達
(a)解題想法
先定義一個二維陣列chess表示棋盤每個點的狀態,若陣列chess元素值為1,表示障礙物,若陣列chess元素值為999,表示目標位置,若陣列chess元素值為2,表示已經走過,若陣列chess元素值為0,表示還未走過。使用寬度優先搜尋,先將起始點設定最少步數為1,將起始點加入佇列,從佇列中取出最前面的元素,考慮這元素相鄰的點,若相鄰點沒有拐馬腳,且未走訪過與未超出邊界,則將這些相鄰點的步數設定為取出點的步數加1,將這些相鄰點加入佇列,不斷重複上述動作直到找到目標點座標或佇列是空的為止,過程中使用變數minstep紀錄目前最少步數,先設定為很大的數字,例如:9999999,若走到目標位置則將最少步數儲存到變數minstep,清空佇列,跳出寬度優先搜尋,最後根據minstep決定是否無法到達,還是可以走到目標位置。
(b)程式碼
(c)程式結果預覽
按下「執行->編譯並執行」,結果顯示在螢幕如下。
範例練習1 d191: uva11352 - Crazy King
BFS 繞過障礙物,從來源到目的地 計算最少步數
範例練習2 APCS201910 第3題闖關路線
BFS
範例練習3 練習題439 - Knight Moves
BFS
範例練習4 i793: pC. WAKUWAKU 尋找興奮源
BFS
範例練習5 uva10603 – Fill
BFS,使用priority queue每次找出倒水量最少的node,node紀錄三個杯子的水量,與倒水量,v[][]記錄前兩個杯子水量,有沒有使用過,為了避免重複拜訪
範例練習6 UVa 572 Oil Deposits
DFS
範例練習7 APCS 10503第4題血緣關係
樹狀結構與DFS
範例練習8 b093: G. 丁丁共和國
使用deque建立順向與逆向adjacency list,並使用DFS演算法找出可以最深的深度,使用vector將國名轉成數字編號
範例練習9 uva-10763 - Foreign Exchange
建圖與DFS
以下為本單元影片