Spark有向無環圖檢測的示例分析

這篇文章給大家介紹Spark有向無環圖檢測的示例分析，內容非常詳細，感興趣的小伙伴們可以參考借鑒，希望對大家能有所幫助。

Spark背景介紹

Apache Spark 是專為大規模數據處理而設計的快速通用的計算引擎。Spark 是一種與 Hadoop 相似的開源集群計算環境，擁有Hadoop MapReduce所具有的優點；但不同于MapReduce的是——Job中間輸出結果可以保存在內存中，從而不再需要讀寫HDFS，因此Spark能更好地適用于數據挖掘與機器學習等需要迭代的MapReduce的算法。

RDD，全稱為Resilient Distributed Datasets，中文翻譯彈性分布式數據集，是一個容錯的、并行的數據結構，可以讓用戶顯式地將數據存儲到磁盤和內存中，并能控制數據的分區。RDD是Spark的靈魂，一個RDD代表一個可以被分區的只讀數據集。RDD內部可以有許多分區(partitions)，每個分區又擁有大量的記錄(records)。

RDD之間的依賴關系是靠有向無環圖（DAG）表達的，下面看下有向無環圖的基本理論和算法。

有向無環圖（DAG）

在圖論中，邊沒有方向的圖稱為無向圖，如果邊有方向稱為有向圖。在無向圖的基礎上，任何頂點都無法經過若干條邊回到該點，則這個圖就沒有環路，稱為有向無環圖（DAG圖），如下圖所示，4->6->1->2是一個路徑，4->6->5也是一條路徑，并且圖中不存在頂點經過若干條邊后能回到該點，可以得出下圖為DAG。

入度

入度是圖論算法中重要的概念之一。它通常指有向圖中某點作為圖中邊的終點的次數之和，也就是項點的入邊條數稱為該項點的入度。如上圖所示，頂點4的入度為0.

出度

對應于入度，頂點的出邊條數稱為該頂點的出度。如上圖所示，頂點3的入度為2.

DAG應用的另一個例子

在一些任務安排和調度的問題里。不同的問題或者任務之間又一些依賴的關系，有的任務需要在某些任務完成之后才能做。就像一些學校的教學課程安排。設置某一門課程需要依賴于一個前置的課程，只有學生學習了前置課程之后才能取學習該課程。如果將一門課程當做一個節點，從它引出一個指針指向后序依賴它的課程。就可能有一個類似這樣的圖：

Algorithms課指向Theoretical CS，意思是選修后者需要先修完Algorithms這門課，Artificial Intelligence依賴Theoretical CS，Machine learning 依賴Artificial Intelligence，Neural Networks依賴Machine learning這門課，這稱為一條路徑。

還可以看到，上圖中入度為0的節點有 Introduction to CS，這個節點在有向圖遍歷中具有重要意義，下面會說到。

如果上圖有環，還正確嗎？

如上所示，如果Machine learning再指向Theoretical CS，意思是選修Theoretical CS的同學需要先修Machine learning，這個就和原來的路徑Artificial Intelligence依賴Theoretical CS，Machine learning 依賴Artificial Intelligence，違背！，并且也不合常理，Theoretical CS是一門基礎性的理論課，怎么可能選修它之前要先修完machine learning呢？所以不能有環路，這個圖是不正確的。所以，這個圖必須為有向無環圖！

有向圖如何檢測有、無環？

那么，如何檢測一個有向圖是否是DAG呢？

有向圖的環檢測，首先對照著無向圖的環檢測來理解，在無向圖中，我們要檢測一個圖中間是否存在環，需要通過深度優先或廣度優先的方式，對訪問過的元素做標記。如果再次碰到前面訪問過的元素，則說明可能存在環。只做標記，在有向圖中檢測環路的辦法可行嗎？

如下圖所示，深度優先遍歷方法，已經遍歷了節點2和6，并marked了，現在遍歷節點1的另一條邊，依次遍歷3,4,5,6，因為6已經遍歷，所以說形成了環路，但是實際上并沒有，因此，與實際不符合，只對訪問過的元素做標記判斷有無環路是錯誤的。

感覺是要加條件，加什么條件？ 如果我們加一個數組保存當前節點是否位于遞歸棧onStack中，就可以排除上面的問題，因為2,6被標記后，依次遞歸出棧，然后到1，深度遍歷1的另一條邊（3->4->5->6），所以6此時不在onStack上，第一次被檢測到，所以沒有環路。

因此，有向圖的無環檢測，需要同時借助兩個限制條件：

1. 對訪問過的元素做標記

2. 當前節點是否位于遞歸棧onStack中
   

在上圖的基礎上，增加節點7和8，如下圖所示，可以預見，按照深度優先搜索到節點4時，會找到子節點5，節點5的其中一個邊找到7，找到8，找到4,節點4此時已經位于onStack中，所以構成環路，是有環圖。

關于Spark有向無環圖檢測的示例分析就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。