首頁技術文章正文

圖論算法介紹[大數據培訓]

更新時間:2019-10-16 來源:黑馬程序員 瀏覽量:

圖論算法在計算機科學中扮演著很重要的角色,它提供了對很多問題都有效的一種簡單而系統(tǒng)的建模方式。很多問題都可以轉化為圖論問題,然后用圖論的基本算法加以解決。

一筆畫問題

圖論的起源可以追溯到大數學家歐拉誕生的那個年代。當時哥尼斯堡城有一個著名的七橋問題,就是每座橋恰好走過一遍并回到原出發(fā)點,然而沒有人成功過。下圖是哥尼斯堡的簡化圖。


1571210855807_圖論1.jpg


這個問題的要求:在穿過每座橋僅一次的情況下穿過這個城市

1. 每座橋:意味著所有橋都被穿過

2. 只穿過一次:意味著每座橋不能被穿越兩次及以上

歐拉沒有試圖去解決這個問題,而是去證明其不可解決。首先,把每一塊連通的陸地作為一個頂點,每一座橋當成圖的一條邊,那么就可以把哥尼斯堡的七座橋抽象成下面的圖。【推薦里了解黑馬程序員大數據培訓課程

1571210888542_圖論2.jpg


對于圖中的每一個頂點,它相連的邊的數量定義為它的度(Degree)

定理:如果一個圖能夠從一個頂點出發(fā),每條邊不重復地遍歷回到這個頂點,那么每一頂點的度必須是偶數。

哥尼斯堡抽象的圖中,存在多個頂點的度為奇數,所以這個圖無法從一個頂點出發(fā),遍歷每條邊各一次然后回到這個頂點。

圖的基本概念

一個圖(G)定義為一個偶對(V,E) ,記為G=(V,E) 。其中: V是頂點(Vertex)的非空有限集合,記為V(G);E是無序集V&V的一個子集,記為E(G) ,其元素是圖的弧(Arc)。

弧(Arc) :表示兩個頂點v和w之間存在一個關系,用頂點偶對表示。通常根據圖的頂點偶對將圖分為有向圖和無向圖。

有向圖(Digraph):若圖G的關系集合E(G)中,頂點偶對的v和w之間是有序的,稱圖G是有向圖。

無向圖(Undigraph): 若圖G的關系集合E(G)中,頂點偶對的v和w之間是無序的,稱圖G是無向圖。

圖的遍歷

圖的遍歷(Travering Graph):從圖的某一頂點出發(fā),訪遍圖中的其余頂點,且每個頂點僅被訪問一次。圖的遍歷算法是各種圖的操作的基礎,有深度優(yōu)先搜索算法和廣度優(yōu)先搜索算法。采用的數據結構是(正)鄰接鏈表。

廣度優(yōu)先搜索算法

廣度優(yōu)先搜索(Breadth-First Search,簡稱BFS)就像水波一樣逐漸向外擴展搜索,它先要盡可能“廣”地訪問每個節(jié)點所直接連接的其他節(jié)點。

1571210916095_圖論3.jpg


例如從A出發(fā),先訪問直接和A相連的節(jié)點B和C,然后看看有哪些節(jié)點和已經訪問過的節(jié)點相連,如D和E與B相連,F、G和H與C相連,然后訪問D、E等節(jié)點,直到把所有節(jié)點都訪問過一遍為止。

深度優(yōu)先搜索算法

深度優(yōu)先搜索(Depth-First Search,簡稱DFS)就像一條路走到黑的搜索,它先要盡可能“深”地訪問每個節(jié)點。

1571210928214_圖論3.jpg


例如從A出發(fā),隨便找一個相連的節(jié)點,比如B,然后從B出發(fā)到下一個節(jié)點,比如E,再從E出發(fā)到下一個節(jié)點I,直到找不到更遠的節(jié)點,在往回找,看看中間是否有尚未訪問的節(jié)點,如此也可以訪問所有的節(jié)點。

深度優(yōu)先搜索算法和廣度優(yōu)先搜索算法都可以保證訪問到全部節(jié)點,但是不論采用哪種方法,都應該用一個小本本記錄已經訪問過的節(jié)點,避免同一個節(jié)點訪問多次獲這漏掉某個節(jié)點,這個小本本就是鄰接鏈表。

猜你喜歡

什么是數據庫?數據庫有什么特點?

Spring Security框架視頻教程[黑馬程序員]

分享到:
在線咨詢 我要報名
和我們在線交談!