圖論及其應(yīng)用[大數(shù)據(jù)培訓(xùn)]

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

一筆畫問題

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

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

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

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

歐拉沒有試圖去解決這個問題，而是去證明其不可解決。首先，把每一塊連通的陸地作為一個頂點，每一座橋當(dāng)成圖的一條邊，那么就可以把哥尼斯堡的七座橋抽象成下面的圖。

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

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

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

圖的基本概念

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

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

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

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

圖的遍歷

圖的遍歷(Travering Graph)：從圖的某一頂點出發(fā)，訪遍圖中的其余頂點，且每個頂點僅被訪問一次。圖的遍歷算法是各種圖的操作的基礎(chǔ)，有深度優(yōu)先搜索算法和廣度優(yōu)先搜索算法。采用的數(shù)據(jù)結(jié)構(gòu)是(正)鄰接鏈表。[推薦了解大數(shù)據(jù)培訓(xùn)課程]

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

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

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

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

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

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

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

猜你喜歡

什么是Docker？有什么特點？

Spark與Hadoop有哪些區(qū)別？

冒泡排序算法[動圖介紹]