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

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

一筆畫問(wèn)題

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

這個(gè)問(wèn)題的要求：在穿過(guò)每座橋僅一次的情況下穿過(guò)這個(gè)城市

1. 每座橋：意味著所有橋都被穿過(guò)

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

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

對(duì)于圖中的每一個(gè)頂點(diǎn)，它相連的邊的數(shù)量定義為它的度(Degree)

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

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

圖的基本概念

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

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

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

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

圖的遍歷

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

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

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

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

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

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

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

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

猜你喜歡

什么是Docker？有什么特點(diǎn)？

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

冒泡排序算法[動(dòng)圖介紹]