Embedded Files
圖形資料結構是由點與邊所組成，許多問題都可以轉換成圖形資料結構，例如：使用地圖搜尋最短路徑，可將地點轉換成圖形資料結構中的點，地點與地點間的距離轉換成邊的權重，最後使用最短路徑演算法就可以找出最短路徑。
在棋盤中要找出走到某一點是否有路徑可以到達，要花費幾步到達，也可以轉換成圖形資料結構，將棋盤中位置轉換成圖形結構中的點，棋子下一步可以到達的棋盤位置，這就是另一個點，若可以到達另一個點，隱含兩點有邊相連。下一個點再找下一個可以到達的點，兩點又形成邊，如此直到走完棋盤所有點，或沒有點可以走，最後判斷是否可以到達目標點。
以下介紹圖形資料結構的定義、程式實作與範例應用。
10-1 簡介圖形資料結構
10-1-1什麼是圖形資料結構
圖形資料結構的定義為由點與邊所組成，邊為連結圖形中兩點，可以有循環(cycle)，也可以有點不跟其他點相連，而樹狀資料結構也是圖形資料結構，樹狀資料結構是圖形資料結構的特例。
圖形資料結構分成有向圖與無向圖，有向圖就是單行道的意思，假設點1與點2，只允許點1連結到點2，不允許點2回到點1，通常使用箭頭的邊表示有向圖，無向圖是指邊允許雙向通行，通常使用沒有箭頭的邊表示。
10-1-2圖形資料結構的名詞定義
介紹一些圖形資料結構的名詞定義，以下圖為範例進行說明。
(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。
10-2 實作圖形資料結構
實作圖形資料結構的程式碼讓讀者可以更加瞭解圖形資料結構，並介紹圖形資料結構的走訪，如何利用程式走訪每個節點。
10-2-1使用陣列建立圖形資料結構
可以使用陣列表示圖形資料結構，如下圖形資料結構範例，本範例圖形結構有5個節點，可以使用5x5的陣列儲存下圖。
若有邊相連，則陣列元素值改為1，否則陣列元素值改為0。由下表可知無向圖一定是對稱陣列，因為點x可以連到點y，點y一定可以連回點x。
有向圖也可以使用陣列表示圖形資料結構，如下圖形資料結構範例，本範例圖形結構有4個節點，可以使用4x4的陣列儲存下圖。
若有邊相連，則陣列元素值改為1，否則陣列元素值改為0。
10-2-1使用陣列建立圖形資料結構.py
第2行：宣告陣列G為二維整數陣列，有100列與100行的元素，每個元素都是0。
第3行：不斷輸入一個數字到變數line。
第4行：將變數line轉換成整數儲存到變數n，表示有幾個邊要輸入。
第5到11行：使用迴圈執行n次，每次輸入兩個數字表示邊的兩個頂點到變數a與b(第6到8行)。設定G[a][b]為1，表示點a可以到點b，設定G[b][a]為1，表示點b可以到點a(第9到10行)。
圖形資料結構使用陣列表示有什麼優缺點？使用陣列表示圖形資料結構的優點是程式撰寫容易。那什麼情況下適合使用陣列表示圖形資料結構？
假設圖形資料結構如下，圖形資料結構只有5個節點，只有3個邊。
若以陣列表示圖形資料結構，如下，只有6元素數值為1，其他元素數值為0，數值為0的元素其實可以不用儲存。
發現出現許多空間的浪費，若圖形資料結構接近完整圖，就可以使用陣列儲存圖形資料結構，不會浪費太多空間；若圖形資料結構有許多的邊都不存在，使用陣列就會造成空間浪費，可以使用字典方式建立圖形資料結構，不會造成浪費太多空間。圖形中有邊存在才需要記錄在字典對應的串列內，不須使用陣列預留所有邊的空間，使用較少記憶體空間。
10-2-2使用字典建立圖形資料結構
圖形資料結構也可以儲存在字典對應串列內，舉例說明如下。
如果要將上圖用字典對應串列表示，結果如下。
字典G的鍵值「0」所對應值為串列為「1、2與3」；字典G的鍵值「1」所對應值為串列為「0、2、3與4」；字典G的鍵值「2」所對應值為串列為「0與1」；字典G的鍵值「3」所對應值為串列為「0與1」；字典G的鍵值「4」所對應值為串列為「1」。
(10-2-2使用字典建立圖形資料結構.py)
第1行：匯入系統函式庫sys。
第2行：宣告陣列G為字典。
第3行：不斷輸入一個數字到變數line。
第4行：將變數line轉換成整數儲存到變數n，表示有幾個邊要輸入。
第5到16行：使用迴圈變數i，由0到n-1，每次遞增1，迴圈執行n次，每次輸入兩個整數到變數a與b，表示邊的兩個頂點 (第6到8行)。如果字典G包含鍵值a，則將b加入到G[a]的最後，表示點a可以到點b (第9到10行)，否則建立新的鍵值a對應到串列，該串列有一個元素b(第11到12行)，表示點a可以到點b。如果字典G包含鍵值b，將a加入到G[b]的最後，表示點b可以到點a (第13到14行)，否則建立新的鍵值b對應到串列，該串列有一個元素a，表示點b可以到點a(第15到16行)。
10-3使用深度優先進行圖的走訪
在圖形的走訪過程中，以深度為優先進行走訪，稱作深度優先搜尋(Depth-First Search，縮寫DFS)，如下圖。以下範例使用深度優先搜尋，從點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)在圖形中，那些點可以連通等訊息都可以使用深度優先搜尋來完成，甚至看起來與圖形無關的問題，也可以轉換成圖形，進行深度優先搜尋找到答案，以下介紹一些深度優先搜尋的範例。
10-3-1使用DFS求最長路徑長度
給定最多200個節點以內的無向圖，但不會形成環，每個節點名稱都是英文字串組成，且任兩個節點的名稱不會相同，節點與節點之間可能有邊相連，求可以連接最長路徑邊的個數。
輸入說明
輸入正整數m，表示有m個邊，接下來有m行，每個邊輸入兩個節點名稱，表示有邊連接這兩個節點，最後一行輸入起始點的節點名稱。
輸出說明
輸出最長路徑的長度。
範例輸入
4
ax bx
bx cx
dx cx
cx ex
ax
範例輸出
3
深度優先搜尋的程式實作想法
使用字典(dict)將節點名稱轉成節點編號，將邊的節點編號加入圖形資料結構中，圖形資料結構以字典表示，最後使用深度優先搜尋，找出最長邊的個數。
(10-3-1使用DFS求最長路徑長度.py)
(a)程式碼與解說
第1到2行：宣告G與City為空字典。
第3行：宣告陣列v為一維整數陣列，有210個元素，每個元素初始化為0。
第4行：初始化變數md為0。
第5到8行：定義getCityIndex函式，將節點名稱轉成數字，使用字串p為輸入，將節點名稱p轉換成節點編號。若p不是字典City的鍵值，則設定字典City的鍵值p，所對應的值為字典City的長度(第6到7行)。回傳字典City以p為鍵值的對應值(第8行)。
第9到18行：定義DFS函式進行深度優先搜尋，輸入參數x表示目前的節點編號，與參數level表示此節點距離起始節點經過了幾個邊了。
第10行：宣告md為全域變數。
第11到18行：使用迴圈讀取節點編號x的所有邊可以連結出去的節點，迴圈變數i由0到G[x]的長度減1，每次遞增1，若變數level大於變數md，則設定變數md為變數level，變數md設定為目前最長路徑的邊數(第13行)。設定變數target為G[x][i]，G[x][i]表示讀取G[x]的第i個元素，變數target設定為能由節點編號x連結出去的節點G[x][i]，若v[target]等於1，表示已經拜訪過，則使用指令continue跳到迴圈的開頭，變數i遞增1，繼續迴圈；否則(v[target]不等於1)，設定v[target]為1(第17行)。使用遞迴呼叫DFS，以下一個節點編號target，與到達節點編號target的邊個數level+1為輸入參數(第18行)。
第19行：輸入邊的個數到變數m。
第20到31行：輸入測試資料，使用字典建立圖形資料結構。迴圈跑m次，每次輸入兩個節點名稱字串到變數a與b(第21行)。將字串a輸入getCityIndex轉成節點編號儲存到變數a (第22行)，將字串b輸入getCityIndex轉成節點編號儲存到變數b (第23行)。如果字典G包含鍵值a，則，將b加入到G[a]的最後，表示點a可以到點b (第24到25行)，否則建立新的鍵值a對應到串列，該串列有一個元素b，表示點a可以到點b(第26到27行)。如果字典G包含鍵值b，將a加入到G[b]的最後，表示點b可以到點a (第28到29行)，否則建立新的鍵值b對應到串列，該串列有一個元素a，表示點b可以到點a(第30到31行)。
第32行：輸入字串到字典City查詢節點編號，儲存到變數start。
第33行：使用DFS做走訪，輸入start與0，表示從start開始，且階層開始為0。
第34行：輸出變數md到螢幕上。
(b)程式結果預覽
輸入以下測試資料。
4
ax bx
bx cx
dx cx
cx ex
ax
執行結果顯示在螢幕如下。
3
(c)程式效率分析
執行第5到7行getCityIndex函式的演算法效率為O(log(n))，因為dict物件的找尋鍵值是否存在的執行效率為O(log(n))，n為節點個數，程式第22到23行呼叫getCityIndex函式約2*m次，m是圖形中邊的個數，演算法效率是O(m*log(n))。
第24到31行字典G最多n個元素，n為節點個數，找尋鍵值是否存在的執行效率為O(log(n))，外層迴圈最多執行m次，演算法效率是O(m*log(n))。
第19到31行總共執行效率為O(m*log(n))。
第33行呼叫函式DFS執行深度優先搜尋，使用字典實作圖形資料結構，第9到18行需不斷搜尋每個邊最多兩次，因為無向圖，每個邊有2個方向，演算法效率為O(n+m)，n為節點個數，m是圖形中邊的個數。
但本範例節點名稱為字串，需先經由dict物件節點名稱轉換為節點編號才能建立圖形結構，反而花了更多時間，整個程式效率為O(m*log(n))。
10-3-2使用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
範例輸出
沒有形成循環
形成循環
深度優先搜尋的程式實作想法
先將節點名稱轉換成節點編號，將節點編號加入圖形資料結構的字典，最後所有點都使用深度優先搜尋，找出是否會回到起始點。
(10-3-2使用DFS偵測是否有迴圈.py)
(a)程式碼與解說
第2到3行：宣告陣列G與City為空字典。
第4行：宣告陣列V為串列，有27個元素，初始化每一個元素都是0。
第5行：初始化變數isLoop為False。
第6到9行：定義getCityIndex函式，將節點名稱轉成數字，使用字串p為輸入，將節點名稱p轉換成節點編號。若p不是字典City的鍵值，則設定字典City[p]，所對應的值為字典City的長度(第7到8行)。回傳字典City以p為鍵值的對應值(第9行)。
第10到20行：定義DFS函式進行深度優先搜尋，輸入參數x表示目前的節點編號，與參數start表示起始節點。
第11行：宣告isLoop為全域變數。
第12到20行：若x是字典G的鍵，則迴圈變數target為G[x]串列內每一個元素，若target等於start，則設定變數isLoop為True，使用return敘述回到上一層。若v[target]等於1，表示已經拜訪過，則使用指令continue跳到迴圈的開頭；否則(v[target]不等於1)設定v[target]為1(第18行)。使用遞迴呼叫DFS，以下一個節點編號target，與到達節點編號start為參數(第19行)，設定v[target]為0(第20行)。
第22到38行：使用迴圈從標準輸入裝置(鍵盤)不斷輸入測試資料到變數line，清空字典G(第23行)，宣告陣列V為串列，有27個元素，初始化每一個元素都是0(第24行)，變數n參考到變數line轉成整數的數值(第25行)。使用迴圈執行n次，每次輸入兩個節點名稱到變數a與變數b，使用函式getCityIndex將節點名稱變數a轉換成節點編號，變數a重新參考到此節點編號，使用函式getCityIndex將節點名稱變數b轉換成節點編號，變數b重新參考到此節點編號。若變數a在字典內，則將變數b加入到串列G[a] ，表示點a可以到點b(第30到31行)；否則建立G[a]對應的串列，該串列有一個元素b，表示點a可以到點b(第32到33行)。
第34到36行：使用迴圈取出字典G的所有鍵到變數item，呼叫函式DFS，以item與item為參數。若isLoop為true，表示已經找到循環，就不用繼續找下去，中斷迴圈(第36行)。
第37到38行：若isLoop為true，則輸出「形成循環」，否則輸出「沒有形成循環」。
(b)程式執行結果
輸入以下測試資料。
3
A D
D B
B C
4
A B
B C
C B
D F
執行結果顯示在螢幕如下。
沒有形成循環
形成循環
(c程式效率分析
此程式第10到20行是深度優先搜尋演算法，使用字典實作圖形資料結構。第13到20行需不斷搜尋每個點連出去的邊最多一次，演算法效率為O(n+m)，n是圖形中點的個數，m是圖形中邊的個數。第34到36行因為每個節點若有邊可以連出去，就需要執行DFS深度優先搜尋演算法，所以整個程式演算法效率最差為O(n*(n+m))，n是圖形中點的個數，m是圖形中邊的個數。
10-4使用寬度優先進行圖的走訪
除了深度優先搜尋外，圖形資料結構另一個常用的走訪演算法為寬度優先搜尋(Breadth-First Search，縮寫BFS)，這兩個演算法都可以走訪所有有邊相連的節點，只是走訪的順序不相同而已，寬度優先搜尋使用佇列暫存下一個要走訪的節點，而深度優先搜尋使用堆疊儲存倒退回來時的下一個要走訪的節點。
以下範例使用寬度優先搜尋，從點0開始，依照未走訪過的節點中數字由小到大順序進行走訪，將點0加入到佇列中。
寬度優先搜尋是以佇列來實作，以發現點的先後順序來儲存點到佇列中，再依序取出進行走訪。甚至看起來與圖形無關的問題，也可以轉換成圖形，進行廣度優先搜尋找出答案來，例如：在迷宮中走到出口的最少步數，下棋時移到某一點的最少步數等，以下介紹一些廣度優先搜尋的範例。
10-4-1迷宮
給定最多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
範例輸出
054340
003200
032100
543206
654345
寬度優先搜尋的程式實作想法
使用寬度優先搜尋，先將起始點設定最少步數為1，將起始點加入佇列，從佇列中取出最前面的元素，考慮這元素相鄰的點，若相鄰點是通道，且未走訪過與未超出邊界，則將這些相鄰點的步數設定為取出點的步數加1，將這些相鄰點加入佇列，不斷重複上述動作直到佇列是空的為止，過程中更新最少步數的同時，要記錄最少步數到二維陣列，輸出此二維陣列就可以獲得結果。
(10-4-1迷宮.py)
(a)程式碼與解說
第1到5行：宣告一個Point結構，有三個元素，分別是列座標r與行座標c，與最少步數dis。
第7到9行：宣告與定義bound函式，輸入row、col、nr與nc，判斷點座標是否超出邊界，若點在邊界內則回傳1，否則回傳0。
第11行：宣告map為二維整數陣列有101列與101行，陣列內每一個元素初始化為0，用於儲存迷宮的節點狀態。
第12行：宣告val為二維整數陣列有101列與101行，陣列內每一個元素初始化為0，用於儲存最少步數。
第13行：宣告gor為整數陣列有4個元素，用於儲存相鄰點列值的差距。
第14行：宣告goc為整數陣列有4個元素，用於儲存相鄰點行值的差距。
第15行：宣告myq為儲存Point物件的串列。
第16到19行：輸入迷宮的列數與行數到變數line，使用字串方法split，切割成兩個列數與行數字串，最後回傳給變數r與變數c，變數r參考到列數，變數c參考到行數。
第20到24行：輸入迷宮的節點狀態，迴圈變數i由1到r，每次遞增1，迴圈執行r次，使用函式input輸入一整行元素到變數line(第21行)，使用字串方法split，切割成串列，變數list參考到此串列(第22行)。使用內層迴圈j由0到c-1，將串列list[j]轉換成整數，儲存到map[i][j+1] (第23到24行)。
第25到28行：輸入迷宮的起始點座標到變數line(第25行)，使用字串方法split，切割成起始點的列座標與行座標到變數sr與變數sc(第26行)。使用函式int將字串變數sr轉換為整數，變數sr重新參考到此整數(第27行)。使用函式int將字串變數sc轉換為整數，變數sc重新參考到此整數(第28行)。
第29行：新增Point類別的物件，設定r為sr、c為sc與dis為1，變數myp參考到此物件。
第30行：設定起始點的步數為1，相當於設定陣列val[myp.r][myp.c]為1。
第31行：將myp加入佇列myq。
第32到42行：若佇列myq的個數大於0，則取出佇列myq的最前面的元素到nextp(第33行)，刪除佇列myq的最前面的元素(第34行)。
第35到42行：使用迴圈變數i，由0到3，每次遞增1，用於計算相鄰點的列座標與行座標，相鄰點的列座標為nextp.r+gor[i]，相鄰點的行座標為nextp.c+goc[i]，使用函式bound判斷是否超出邊界，且是否該點的陣列map等於1，表示相鄰點是通道，且是否該點的陣列val等於0，表示還沒有走過(第36行)。
第37行：設定該點的陣列val的數值為nextp.dis+1。
第38到42行：儲存相鄰點到佇列myq，變數tmp參考到一個Point物件(第38行)，設定tmp.r為nextp.r+gor[i] (第39行)，設定tmp.c為nextp.c+goc[i] (第40行)，設定tmp.dis為nextp.dis+1(第41行)，將tmp加入佇列myq。
第44到47行：使用巢狀迴圈顯示二維陣列val到螢幕，外層迴圈變數i，由0到r-1，每次遞增1，內層迴圈變數j，由0到c-1，每次遞增1，每次顯示val[i+1][j+1]到螢幕。輸出一列後顯示換行(第47行)。
(b)程式執行結果
輸入以下測試資料。
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
執行結果顯示在螢幕如下。
054340
003200
032100
543206
654345
(c)程式效率分析
執行第29到42行的寬度優先搜尋演算法，每個通道的節點都會被加入佇列與從佇列取出，最多通道的個數為r*c，r為迷宮的列數，c為迷宮的行數，所以寬度優先搜尋演算法效率最差為O(r*c)
第20到24行輸入迷宮的狀態，其程式效率為O(r*c)
第44到47行顯示最少步數結果，其程式效率也是O(r*c)，所以整個程式的效率為O(r*c)。
10-4-2象棋馬的移動
(10-4-2象棋馬的移動.py)
給定最多20列20行的棋盤，請找出棋盤上所指定馬的位置到棋盤上所有點的最少步數，請寫一個程式列出棋盤上每一個點的最少步數。象棋的馬走法如下。
輸入說明
輸入正整數r與c，表示棋盤中有r列與c行，接著輸入兩個整數sr與sc表示馬起始位置的列數與行數。
輸出說明
請輸出r列c行個數字，顯示棋盤中到達所有點的最少步數，且起始點的步數設定為1，顯示結果請參考範例輸出。
範例輸入
10 10 4 6
範例輸出
5434343434
4345232543
5432343234
4343414343
5432343234
4345232543
5434343434
4543434345
5454545454
6545454545
寬度優先搜尋的程式實作想法
使用寬度優先搜尋，先將起始點設定最少步數為1，將起始點加入佇列，從佇列中取出最前面的元素，考慮這元素相鄰的點。若相鄰點未走訪過與未超出邊界，則將這些相鄰點的步數設定為取出點的步數加1，將這些相鄰點加入佇列，不斷重複上述動作直到佇列是空的為止，過程中更新最少步數的同時，記錄最少步數到二維陣列，輸出此二維陣列就可以獲得結果。
(a)程式碼與解說
第1到5行：宣告一個Point結構，有三個元素，分別是列座標r與行座標c，與最少步數step。
第7到9行：宣告與定義bound函式，輸入row、col、nr與nc，判斷點座標是否超出邊界，若點在邊界內則回傳1，否則回傳0。
第11行：宣告chess為二維整數陣列有21列與21行，陣列內每一個元素初始化為0，用於儲存棋盤起始點到每個點的步數。
第12行：宣告gor為整數陣列有8個元素，用於儲存馬走到相鄰點列值的差距。
第13行：宣告goc為整數陣列有8個元素，用於儲存馬走到相鄰點行值的差距。
第14行：宣告myq為儲存Point物件的串列。
第15到19行：使用input函式輸入四個數字，使用字串方法split，切割成四個數字，分別輸入棋盤的列數與行數到變數r與c，輸入起始點的列座標與行座標到變數sr與sc。使用函式int將字串變數r轉換為整數，變數r重新參考到此整數(第16行)。使用函式int將字串變數c轉換為整數，變數c重新參考到此整數(第17行)。使用函式int將字串變數sr轉換為整數，變數sr重新參考到此整數(第18行)。使用函式int將字串變數sc轉換為整數，變數sc重新參考到此整數(第19行)。
第20行：設定chess[sr][sc]為1，表示起始點只要一步就可以到達。
第21行：新增Point類別的物件，設定r為sr、c為sc與step為1，變數myp參考到此物件。
第22行：將myp加入佇列myq。
第23到33行：若佇列myq的個數大於0，則取出佇列myq的最前面的元素到nextp(第24行)，刪除佇列myq的最前面的元素(第25行)。
第26到33行：使用迴圈變數i，由0到7，每次遞增1，用於計算相鄰點的列座標與行座標，相鄰點的列座標為nextp.r+gor[i]，相鄰點的行座標為nextp.c+goc[i]，使用函式bound判斷是否超出邊界，且陣列chess的該點數值是否等於0，表示還沒有走過(第27行)。
第28行：設定該點的陣列chess的數值為nextp.step+1。
第29到33行：儲存相鄰點到佇列myq，變數tmp參考到一個Point物件(第29行)，設定tmp.r為nextp.r+gor[i] (第30行)，設定tmp.c為nextp.c+goc[i] (第31行)，設定tmp.step為nextp.step+1(第32行)，將tmp加入佇列myq。
第34到37行：使用巢狀迴圈顯示二維陣列chess到螢幕，外層迴圈變數i，由0到r-1，每次遞增1，內層迴圈變數j，由0到c-1，每次遞增1，每次顯示chess[i+1][j+1]到螢幕。輸出一列後顯示換行(第37行)。
(b)程式執行結果
輸入以下測試資料。
10 10 4 6
執行結果顯示在螢幕如下。
5434343434
4345232543
5432343234
4343414343
5432343234
4345232543
5434343434
4543434345
5454545454
6545454545
(c)程式效率分析
執行第27到33行的寬度優先搜尋演算法，棋盤上每個點都會被加入佇列，再從佇列取出，點個數為r*c，r為棋盤的列數，c為棋盤的行數，所以寬度優先搜尋演算法效率最差為O(r*c)
第34到37行顯示最少步數結果，其程式效率也是O(r*c)，所以整個程式的效率為O(r*c)。
Page updated
Google Sites
Report abuse