傳智播客旗下品牌:|||||

全國咨詢/投訴熱線:400-618-4000

圖論及其應用[大數據培訓]

更新時間:2019年10月16日15時36分 來源:傳智播客 瀏覽次數:

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

一筆畫問題

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

圖論算法1


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

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

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

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

圖論算法2

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

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

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

圖的基本概念

一個圖(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):從圖的某一頂點出發,訪遍圖中的其余頂點,且每個頂點僅被訪問一次。圖的遍歷算法是各種圖的操作的基礎,有深度優先搜索算法和廣度優先搜索算法。采用的數據結構是(正)鄰接鏈表。[推薦了解大數據培訓課程]


廣度優先搜索算法

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

圖論算法3

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

深度優先搜索算法

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

圖論算法4

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

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


猜你喜歡

Spark與Hadoop有哪些區別?

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

javaee

python

web

ui

cloud

test

c

netmarket

pm

Linux

movies

robot

uids

北京校區

    14天免費試學

    基礎班入門課程限時免費

    申請試學名額

    15天免費試學

    基礎班入門課程限時免費

    申請試學名額

    15天免費試學

    基礎班入門課程限時免費

    申請試學名額

    15天免費試學

    基礎班入門課程限時免費

    申請試學名額

    20天免費試學

    基礎班入門課程限時免費

    申請試學名額

    8天免費試學

    基礎班入門課程限時免費

    申請試學名額

    20天免費試學

    基礎班入門課程限時免費

    申請試學名額

    5天免費試學

    基礎班入門課程限時免費

    申請試學名額

    0天免費試學

    基礎班入門課程限時免費

    申請試學名額

    12天免費試學

    基礎班入門課程限時免費

    申請試學名額

    5天免費試學

    基礎班入門課程限時免費

    申請試學名額

    5天免費試學

    基礎班入門課程限時免費

    申請試學名額

    10天免費試學

    基礎班入門課程限時免費

    申請試學名額
    有做网赚的吗 中华网赚 北京28预测 全球彩票开户 2019免费网赚资源 2019调查网赚 2019国外网赚 网赚平台哪个赚钱快点 2019哪些网赚是真的 千万时网赚平台是骗子吗