一、何謂圖形 What is Graph?
如果你單純的把 Graph 這個字英翻中的話,可以翻作「圖」或者「圖形」。
但是這邊指的並不是圖像、圖片,如果我們真的想要表示圖片或者影像的話,通常會用:Image、Picture、Photo 這樣的字。 Graph 在演算法裡面算是一個蠻特定的關鍵字,可以用來表達 Object 之間的關聯、關係。 一個 Graph 會由數個點 ( vertex ) 和數條邊 ( edge ) 所構成。e.g.
至於點的形狀 ( 畫圓的、方的、空心、實心... )、大小、顏色;或者邊的粗細、長短、畫直線畫曲線這都是無所謂的。只要你畫出來的圖形 ( Graph ) 可以用來正確表達物體之間的關聯、關係就可以了!
所以今天不論你想怎麼畫,都是無所謂的只要它們能正確的表達點跟點之間的關係就好。e.g.
像上面的這三個圖代表的都是同樣的連接關係,我們稱作:「同構 ( Isomorphism )」。
同構的圖形擁有相同的資訊,不管選哪一種來表示都是可以的!所以我們就會選一個清楚易懂的。 另外,圖形還可以分成有向圖跟無向圖兩種。 有向圖 ( Directed Graph ) 即圖形中的每一個邊 ( edge ) 都有帶一個方向性,就像開車的時候遇到單行道一樣,只允許你朝某一個方向開;而無向圖 ( Undirected Graph ) 跟有向圖的特性剛好相反,即圖形中的每一個邊 ( edge ) 都不存在方向性,你可以任意的在兩個點上來回穿梭。如下圖所示: Ok, 那在對圖形有一個基本的概念以後,為什麼我們需要圖形? 它會被用在那些地方? 就如同一開始講的,「圖形」可以用來表達物體之間的關係,所以圖形還蠻常用在計算機網路上面。我們可以幫每一個 Vertex 取一個代號,像是:Host、Router、DNS Server、Proxy、CDN...;然後也可以幫每一個 edge 加上一個權重 ( weights ) 用來表示連線的 Cost,如此一來就可以很清楚的表達一個網路拓樸,並且我們就可以應用圖形演算法來解決一些問題 ( e.g. 找 A點到B點成本最低的路徑 )。 其實在計算機科學領域還有其他蠻多狀況會用「圖形」來解,所以在計算機科學的課程裡有一個專門的 Topic 就叫做「圖論」,就是專門在探討這一個部分。 接下來 Jason 會跟各位介紹兩個最經典的圖形演算法:「深度優先搜尋法」跟「廣度優先搜尋法」。 至於其他經典的圖形演算法像是:Dijkstra's Algorithm 還是 A* Algorithm,就看 Jason 之後有沒有空再另外寫一篇來討論吧! 二、深度優先搜尋法 Depth-first Search
深度優先搜尋法,是一種用來遍尋圖形的演算法。
另外如果你稍微思考一下,應該不難發現我們在「資料結構」中提到的「樹」其實是可以被視為是一種圖的。所以接著我們會討論到的「圖形演算法」基本上都可以套到「樹」來使用。 深度優先搜尋法的做法是:由樹根 ( 或圖的某一點當成根 ) 開始探尋,先探尋邊 ( edge ) 上未搜尋的一節點 ( vertex or node ) ,並盡可能深的搜索,直到該節點的所有邊上節點都已探尋;就回溯 ( backtracking ) 到前一個節點,重覆探尋未搜尋的節點,直到找到目的節點或遍尋全部節點。 這個演算法算蠻簡單也蠻直覺的,在 Coding 上我們可以用遞迴的方式來實作:
Depth-first Search
而這個演算法也有一些比較有趣的應用,像是可以用來製作迷宮跟走訪迷宮。( 想到以前大一程式課,期中考有一題就是要做老鼠走迷宮 xD 三、廣度優先搜尋法 Breadth-first Search
廣度優先搜尋法,也是一種用來遍尋圖形的演算法。
基本上就跟前面提到的深度優先搜尋法是一個相對的概念,廣度優先搜尋法會走遍距離起點最近之處,優先讓 BFS Tree 變得寬廣,而這個遍歷順序能夠解決許多圖論問題! 那就廢話不多說,直接上張 GIF 來看它到底是怎麼遍歷一個 Tree 的:
基本上這個演算法在實作的時候,就是靠 Queue 來完成。
當 (1) 走訪到 (2) 的時候會先將 (2) 存在 queue 裡面,然後看看 (1) 還有沒有子節點;發現還有子節點 (3) 然後走訪到 (3) ,接著一樣將 (3) 存到 queue 再回頭看看 (1) 有沒有子節點;發現沒有了,於是就從 queue 裡面提取一個節點出來當作起點周而復始,直到 queue 裡面完全都沒有節點後結束。 BFS 演算法的流程: 依照編號順序不斷找出尚未遍歷的點當作起點,然後:
Breadth-first Search
前面介紹的這兩種搜尋演算法,屬於「盲目搜索方法」又叫作「非啟發式搜索」,是一種無信息搜索,一般而言只適用於求解比較簡單的問題,盲目搜索通常是按預定的搜索策略進行搜索,而不會考慮到問題本身的特性。
所以當今天你很清楚你求解問題的特性,就蠻有可能不會採用這兩個方法來做了! 不過前面介紹的這兩個真的算是非常經典的圖形演算法,甚至有很多解題的策略就是沿著這個演算法去做延伸的,所以說還是必須要會的! Ok, 那今天的這篇就寫到這邊吧 :")
0 評論
發表回覆。 |
Jason Chen人不光是生來就擁有一切,而是靠他從學習中得到的一切來造就自己。- 歌德 文章分類
全部
封存檔
九月 2023
|