圖形結構(Python)
本單元目錄大綱
一、圖形資料結構與圖形走訪
二、實作圖形資料結構
三、使用深度優先進行圖的走訪
四、使用寬度優先進行圖的走訪
一、圖形資料結構與圖形走訪
圖形資料結構是由點與邊所組成，圖形資料結構廣泛應用於程式的實作，許多問題都可以轉換成圖形資料結構，例如：使用網路地圖搜尋最短路徑，可將地點轉換成圖形資料結構中的點，地點與地點間的距離轉換成邊的權重，最後使用最短路徑演算法就可以找出最短路徑。
在棋盤中要找出走到某一點是否有路徑可以到達，要花費幾步到達，也可以轉換成圖形資料結構，將棋盤中位置轉換成圖形結構中的點，棋子下一步可以到達的棋盤位置，這就是另一個點，若可以到達另一個點隱含兩點有邊相連，下一個點再找下一個可以到達的點，兩點又形成邊，如此直到走完棋盤所有點，或沒有點可以走，最後判斷是否可以到達目標點。以下介紹圖形資料結構的定義、程式實作與範例應用。
(一)簡介圖形資料結構
什麼是圖形資料結構
圖形資料結構的定義為由點與邊所組成，邊為連結圖形中兩點，可以有循環(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。
Python程式碼
圖形資料結構使用陣列表示有什麼優缺點？使用陣列表示圖形資料結構的優點是程式撰寫容易。那什麼情況下適合使用陣列表示圖形資料結構？
若圖形資料結構接近完整圖，就可以使用陣列進行圖形資料結構的建立，不會浪費太多空間，若圖形資料結構有許多的邊都不存在，使用陣列就會造成空間浪費，可以使用鏈結串列方式建立圖形資料結構，不會造成浪費太多空間，圖形中有邊存在才需要記錄在鏈結串列，不須使用陣列預留所有邊的空間，減少記憶體空間的使用。
(二)使用鏈結串列建立圖形資料結構
圖形資料結構也可以使用指標所建立鏈結串列陣列進行儲存，鏈結串列需要一個指標指向下一個元素，再把這樣的結構宣告為陣列。
如果要將下圖使用鏈結串列陣列方式建立圖形資料結構。
鏈結串列陣列head的示意圖如下。
但使用鏈結串列表示圖形資料結構的程式有些複雜，可不可以有其他方法取代，可以使用字典(dict)取代，使用數值(key)對應到串列(value)，雖然會浪費較多空間，但在程式碼撰寫上可以比較容易，也較容易閱讀，程式碼執行效率也不差。
Python程式碼
三、使用深度優先進行圖的走訪
在圖形的走訪過程中，以深度為優先進行走訪，稱作深度優先搜尋，如下圖，以下範例使用深度優先搜尋，從點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)解題想法
使用字典(dict)將節點名稱轉成節點編號，將圖形資料結構以另一個字典(dict)表示，最後使用深度優先搜尋，找出最長邊的個數。
(b)Python程式碼
(二)使用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)Python程式碼
四、使用寬度優先進行圖的走訪
除了深度優先搜尋外，圖形資料結構另一個常用的走訪演算法為寬度優先搜尋，這兩個演算法都可以走訪所有有邊相連的節點，只是走訪的順序不相同而已，寬度優先搜尋使用佇列暫存下一個要走訪的節點，而深度優先搜尋使用堆疊儲存倒退回來時的下一個要走訪的節點。
以下範例使用寬度優先搜尋，從點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)Python程式碼
(二)象棋馬的移動
給定最多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)Python程式碼
(三)有障礙物的馬
給定最多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)Python程式碼