圖形結構(Python)

本單元簡報

https://drive.google.com/file/d/1W9bBSI_YTfR1bCoMFbnCc4I4PsRggAqt/view?usp=sharing

本單元影片

Python圖形結構的YouTube播放清單(https://youtube.com/playlist?list=PLOk9WKoJdjHaAmFo8b4HjkOTMGSXSRNxy&si=YiX4AC4w-ckHnvcI)

本單元目錄大綱

一、圖形資料結構與圖形走訪

二、實作圖形資料結構

三、使用深度優先進行圖的走訪

四、使用寬度優先進行圖的走訪

一、圖形資料結構與圖形走訪

圖形資料結構是由點與邊所組成，圖形資料結構廣泛應用於程式的實作，許多問題都可以轉換成圖形資料結構，例如：使用網路地圖搜尋最短路徑，可將地點轉換成圖形資料結構中的點，地點與地點間的距離轉換成邊的權重，最後使用最短路徑演算法就可以找出最短路徑。

在棋盤中要找出走到某一點是否有路徑可以到達，要花費幾步到達，也可以轉換成圖形資料結構，將棋盤中位置轉換成圖形結構中的點，棋子下一步可以到達的棋盤位置，這就是另一個點，若可以到達另一個點隱含兩點有邊相連，下一個點再找下一個可以到達的點，兩點又形成邊，如此直到走完棋盤所有點，或沒有點可以走，最後判斷是否可以到達目標點。以下介紹圖形資料結構的定義、程式實作與範例應用。

(一)簡介圖形資料結構

什麼是圖形資料結構

圖形資料結構的定義為由點與邊所組成，邊為連結圖形中兩點，可以有循環(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)：無向圖中任兩點都有邊相連。

(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。

圖形資料結構使用陣列表示有什麼優缺點？使用陣列表示圖形資料結構的優點是程式撰寫容易。那什麼情況下適合使用陣列表示圖形資料結構？

若圖形資料結構接近完整圖，就可以使用陣列進行圖形資料結構的建立，不會浪費太多空間，若圖形資料結構有許多的邊都不存在，使用陣列就會造成空間浪費，可以使用鏈結串列方式建立圖形資料結構，不會造成浪費太多空間，圖形中有邊存在才需要記錄在鏈結串列，不須使用陣列預留所有邊的空間，減少記憶體空間的使用。

(二)使用鏈結串列建立圖形資料結構

圖形資料結構也可以使用指標所建立鏈結串列陣列進行儲存，鏈結串列需要一個指標指向下一個元素，再把這樣的結構宣告為陣列。

如果要將下圖使用鏈結串列陣列方式建立圖形資料結構。

四、使用寬度優先進行圖的走訪

除了深度優先搜尋外，圖形資料結構另一個常用的走訪演算法為寬度優先搜尋，這兩個演算法都可以走訪所有有邊相連的節點，只是走訪的順序不相同而已，寬度優先搜尋使用佇列暫存下一個要走訪的節點，而深度優先搜尋使用堆疊儲存倒退回來時的下一個要走訪的節點。

以下範例使用寬度優先搜尋，從點0開始，依照未走訪過的節點中數字由小到大順序進行走訪，將點0加入到佇列中。

寬度優先搜尋是以佇列來實作，以發現點的先後順序來儲存點到佇列中，再依序取出進行走訪。甚至看起來與圖形無關的問題，也可以轉換成圖形，進行廣度優先搜尋找出答案來，例如：在迷宮中走到出口的最少步數，下棋時移到某一點的最少步數等，以下介紹一些廣度優先搜尋的範例。

(一)迷宮

給定最多100列100行的迷宮，數字1表示通道，數字0表示牆壁，請找出迷宮中指定的起始點到所有通道的最少步數，保證迷宮所有通道一定相連，請寫一個程式列出迷宮中每一個通道距離起始點的最少步數。

輸入說明

輸入正整數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，將這些相鄰點加入佇列，不斷重複上述動作直到佇列是空的為止，過程中更新最少步數的同時，要記錄最少步數到二維陣列，輸出此二維陣列就可以獲得結果。

(二)象棋馬的移動

給定最多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，將這些相鄰點加入佇列，不斷重複上述動作直到佇列是空的為止，過程中更新最少步數的同時，要記錄最少步數到二維陣列，輸出此二維陣列就可以獲得結果。

(三)有障礙物的馬

給定最多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決定是否無法到達，還是可以走到目標位置。