10種算法一文打盡!基本圖表算法的視覺化闡釋

2020-11-21 51CTO

10種算法一文打盡！基本圖表算法的視覺化闡釋

在社交媒體網絡、網頁和連結、GPS中位置和路線等真實場景中，圖表已成為一種強大的建模和捕獲數據手段，如果一組對象相互關聯，則可以用圖表來表示。

作者：讀芯術 來源： 讀芯術|2020-09-21 14:35

 

在社交媒體網絡、網頁和連結、GPS中位置和路線等真實場景中，圖表已成為一種強大的建模和捕獲數據手段，如果一組對象相互關聯，則可以用圖表來表示。

本文就將簡要解釋10個非常有助於分析和應用的基本圖表算法。

首先，圖表是什麼?

圖表由一組有限頂點或節點和一組連接這些頂點的邊組成，如果兩個頂點通過同一條邊互相連接，則稱之為鄰接。下面是一些與圖表相關的基本定義，可以參考圖中示例。

  • 順序：圖表中的頂點數
  • 大小：圖表中的邊數
  • 頂點度：入射到頂點的邊數
  • 孤立頂點：未連接到圖中任何其它頂點的頂點
  • 自循環：從頂點到自身的一條邊
  • 有向圖：圖中所有的邊都有方向，來表示起點和終點
  • 無向圖：圖的邊無方向
  • 加權圖：圖的邊有權值
  • 未加權圖：圖的邊無權值

圖1：圖表術語的可視化

1.廣度優先搜索

圖2 ：廣度優先搜索(BFS)遍歷動畫

遍歷或搜索是圖表上執行的基本操作之一。在廣度優先搜索(BFS)中，從特定某個頂點開始，在進入下一層的頂點前先探索它當前深度的所有相關信息。與樹不同，圖表可以包含循環(第一個和最後一個頂點是相同的路徑)。因此，必須跟蹤訪問過的頂點。在實現BFS時，應使用隊列數據結構。

圖2是一個示例圖的BFS遍歷的動畫，注意一下頂點如何被發現(黃色)和被訪問(紅色)。

應用：

  • 用於社交網絡搜索
  • 用於確定最短路徑和最小生成樹
  • 被搜尋引擎爬網程序用於構建網頁索引
  • 用於查找對等網絡(如BitTorrent)中的可用鄰近節點

2.深度優先搜索

圖3：為深度優先搜索(DFS)的遍歷動畫

在深度優先搜索(DFS)中，從某個特定頂點開始，回溯(backtracking)前，沿著每個分支儘可能搜索。DFS中，還需跟蹤訪問過的頂點。實現DFS時，使用堆棧數據結構來支持回溯。

圖3對圖2中使用的同一個示例圖進行DFS遍歷的動畫，注意它如何遍歷到深度和回溯。

應用：

  • 用於查找兩個頂點之間的路徑
  • 用於檢測圖中的循環
  • 用於拓撲排序
  • 用於解決只有一種解決方案的難題(例如迷宮)

3.最短路徑

圖4動畫顯示了從頂點1到頂點6的最短路徑

從一個頂點到另一個頂點的最短路徑是圖形中的路徑，因此應使移動邊的權重之和最小。圖4顯示了一個動畫，其中確定了圖中頂點1到頂點6的最短路徑。

算法：

  • Dijkstra的最短路徑算法
  • 貝爾曼福特(Bellman–Ford)算法

應用：

  • 用於網絡中最小延遲路徑問題的解決。
  • 用於在Google或Apple地圖等軟體中查找一個位置到另一位置的路線。
  • 用於抽象機器中，通過不同狀態之間的轉換來確定達到某一目標狀態的方法。例如，可以用來確定如何用最少走法贏得一場比賽。

4.循環檢測

圖5：一個循環

循環是指圖中第一個頂點和最後一個頂點相同的路徑。如果從一個頂點出發，沿著一條路徑，最後到達起始點，那麼這條路徑就是一個循環。循環檢測是檢測這些循環的過程。圖5展示了遍歷一個循環的動畫。

算法：

應用：

  • 用於基於消息的分布式算法
  • 用於使用集群上的分布式處理系統處理大規模圖表
  • 用於檢測並發系統中的僵局
  • 在加密應用程式中用於確定能夠將消息映射到相同加密值消息的密鑰

5.最小生成樹

圖6.顯示最小生成樹的動畫

最小生成樹是圖表邊的子集，它連接所有邊權值最小和的頂點，不包含任何循環。圖6是一個獲得最小生成樹過程的動畫。

算法：

應用：

  • 用於在計算機網絡中構建廣播樹
  • 用於基於圖表的聚類分析
  • 用於圖像分割
  • 用於社會地理領域的區域化，將區域劃分為相鄰區域。

6.強連通分量

圖7：強連通分量

如果圖表中的每個頂點都能通過其他頂點到達，那麼這個圖就是強連通的。圖7包含三個強連接分量，頂點分別用紅色、綠色和黃色表示。

算法：

應用：

  • 用於計算Dulmage Mendelsohn分解，是二分圖表邊的一種分類。
  • 用於社交網絡中，根據共同愛好，發現並推薦具有密切聯繫的人。

7.拓撲排序

圖8：圖中頂點的拓撲排序

圖表的拓撲排序是對其頂點進行線性排序，因此對於排序中的每條有向邊(u, v)，頂點u都在v之前。圖8顯示了頂點(1、2、3、5、4、6、7、8)的拓撲排序示例。可以看到，頂點5應在頂點2和3之後。同樣，頂點6應該在頂點4和5之後。

算法：

應用：

  • 用於指令調度
  • 用於數據序列化
  • 用於確定要在生成文件中執行的編譯任務的順序
  • 用於解析連結器中的符號依賴關係

8.圖著色

圖9：頂點著色

圖著色指的是在保證一定條件下給圖的元素分配顏色，頂點著色是最常用的圖形著色技術。在頂點著色中，我們嘗試用k種顏色給圖的頂點著色，任何兩個相鄰的頂點顏色都不相同。其他著色技術包括邊緣著色和面部著色。圖的色數是為圖著色所需顏色的最小數目。圖9顯示了用4種顏色為頂點著色。

算法：

應用：

  • 用於制定時間表
  • 用於分配移動無線電頻率
  • 用於建模和求解數獨遊戲
  • 用於檢查圖是否為二部圖
  • 用於在相鄰國家或州的地圖上用不同顏色著色

9.最大流量

圖10：確定最大流量

可以將一個圖建模為以邊權值作為流量容量的流網絡。在最大流量問題中，必須找到能獲得最大可能流量速率的流動路徑。圖10是一個確定網絡的最大流量和最終流量值的動畫示例。

算法：

  • Ford-Fulkerson算法
  • Edmonds–Karp算法
  • Dinic算法

應用：

  • 用於航空公司調度，安排航班機組人員。
  • 用於圖像分割，查找圖像中的背景和前景。
  • 用來淘汰那些無法贏得比賽、無法與當前隊伍優秀者相匹敵的隊員。

10.匹配

圖11：二部圖匹配

圖表中的匹配是一組沒有共同頂點的邊(也就是說，任何兩條都沒有共同頂點)。如果一個匹配包含儘可能多頂點匹配的邊的最大數量，那麼這個匹配被稱為最大匹配。圖11顯示了獲得二部圖的完全匹配動畫，該二部圖有兩組頂點，分別用橙色和藍色表示。

算法：

  • 霍普克洛夫特-卡普(Hopcroft–Karp)算法
  • 匈牙利(Hungarian)算法
  • 開花算法

應用：

  • 用於為新娘和新郎牽線搭橋(婚姻的穩定問題)
  • 用於確定頂點覆蓋率
  • 用於交通理論中解決出行資源配置和優化問題

這10種基本圖表算法應用廣泛，你get了嗎?

本文轉載自微信公眾號「讀芯術」，可以通過以下二維碼關注。轉載本文請聯繫讀芯術公眾號。

【編輯推薦】

【責任編輯：

武曉燕

TEL：（010）68476606】

點讚 0

相關焦點

  • 用圖形解釋10種圖形算法
    快速介紹10種基本圖形算法以及示例和可視化在現實世界中，例如社交媒體網絡，網頁和連結以及GPS中的位置和路線，圖形已經成為一種強大的建模和捕獲數據的手段。 如果您有一組相互關聯的對象，則可以使用圖形來表示它們。
  • 程式設計師必備的幾種常見排序算法和搜索算法總結
    本文轉載自【微信公眾號：趣談前端，ID:beautifulFront】經微信公眾號授權轉載，如需轉載與原文作者聯繫前言最近為了鞏固一下自己的算法基礎,又把算法書裡的基本算法刷了一遍, 特地總結一下前端工程師需要了解的排序算法和搜索算法知識,雖然還有很多高深算法需要了解
  • 圖的最短路徑算法-Floyd算法-弗洛伊德算法
    Floyd算法又稱為插點法，是一種利用動態規劃的思想尋找給定的加權圖中多源點之間最短路徑的算法 在計算機科學中，Floyd-Warshall算法是一種在具有正或負邊緣權重（但沒有負周期）的加權圖中找到最短路徑的算法。算法的單個執行將找到所有頂點對之間的最短路徑的長度（加權）。
  • 參加頂級科技公司面試前需要掌握的10個基本算法 - 讀芯術
    來源: https://leetcode.com/problemset/all/網站上有數百種不同的算法問題，這意味著你需要耗費大量的時間和精力，才能在十分鐘內識別出問題的常見模式並編寫有效的解決方案defsolution(num1, num2):n1, n2 =0, 0m1, m2 =10**(len(num1)-1), 10**(len(num2)-1)for i in num1:n1 += (
  • 新算法助新型基本粒子發現
    俄羅斯科研人員利用一種新算法，把粒子從其他質子碎片中分離出來，從而發現了一種新型基本粒子。 新算法由俄羅斯高等經濟學校大型數據分析方法實驗室的工作人員編寫，使用了機器學習方法，在此基礎上使用俄羅斯最大網際網路公司yandex的算法記錄了新粒子。研發人員提出了一種新解決方法，可以不用記錄粒子全部的分裂而只記錄下科學家感興趣的一組分裂。最後發現了4個激發粒子。
  • 機器學習算法之K-means算法
    K-means舉例shi'li1 K-means算法簡介k-means算法是一種聚類算法，所謂聚類，即根據相似性原則，將具有較高相似度的數據對象劃分至同一類簇，將具有較高相異度的數據對象劃分至不同類簇。
  • SEO算法:巴郎深談石榴算法與算法對策
    前言每一套SEO算法的出臺都是在提升用戶體驗，石榴算法就是重點針對低質量廣告頁面而誕生的-SEO算法目錄( 4867 字)01.上線時間與宗旨02.石榴算法的意義03.石榴算法的誕生04.SEO從業人員如何應對石榴算法最後的話01
  • 一文概覽密碼學發展史、基本原理與常見算法
    小編：記得關注哦 來源：以太坊愛好者 原文標題：一文概覽密碼學發展史、基本原理與常見算法 原文標題：《科普 | 從數學到物理學：加密算法簡介》 撰文：George Moraetes
  • C語言入門級教程:基礎數據類型與基本算法,學編程從此刻開始!
    今天帶大家了解一下學C語言必備的基本數據類型和基本算法，適合剛學C以及零基礎的小夥伴！ 話不多說，我們一起來學習吧~ 數據類型 ● 基本類型 基本類型就是我們在使用C語言時最基礎的數據類型，包括整形（短整型，基本整型，長整型）、字符型、浮點型（單、雙精度）以及枚舉類型。
  • 論算法的法律規制
    2020年引起社會廣泛關注的外賣算法系統，一些網際網路平臺利用算法設置外賣騎手的配送時間，送餐時間被壓縮得越來越短，對外賣騎手的生命健康造成嚴重威脅。而且，這個算法系統採用自動化的機器決策，騎手很難理解和提出抗議。從法律的角度看，算法從幾個方面挑戰了法律的一些基本原則。首先，算法黑箱可能挑戰人類決策的知情權與自主決策。
  • TransE算法
    算法思想核心思想: 把三元組轉化成低維向量，這個向量我們叫做embedding向量，變成向量之後就可以用很多數學方法進行進一步的處理原始的數據是三元組形式(h, r, t)，希望找到某種算法能把h，r，t分別轉換為向量，類似[0.01,
  • Github標星42K+超火的幾份算法筆記寶典,刷新了我對算法的新認知
    &(邏輯與)、| (邏輯或)和^(異或)五種字符組成的字符串express再給定一個布爾值desired.返回express能有多少種組合方式，可以達到desired的結果。給定一個字符串數組strs[]，在strs中有些位置為null,但在不為null的位置上，其字符串是按照字典順序由小到大依次出現的。
  • ...媒體算法解析:Facebook、YouTube、Twitter如何利用算法推薦內容?
    首先，本文並不打算列出算法內部的確切的計算原理，而是將重點放在囊括當前主流社交媒體算法的主要特點。其次，文中所展示的圖表並不是算法的可視化，它們更多地是展示某些決定性問題，而不是算法方程式。本文作者為Ste Davies，由騰訊媒體研究院編譯。你可以遵循這篇文章來迭代自身內容，以確保能在各大平臺獲得最大的影響。
  • 陳根:算法下的選擇讓渡,你被算法裹挾了嗎?
    但不論是大數據還是人工智慧，都依託算法而存在，我們正在走進的數字世界本質上則是數據驅動的算法應用。當算法充斥於我們的生活，又在細微處改變著我們對信息的接收、對產品的需求以及情緒與狀態時，卻少有人關心算法最終會對我們產生的影響。
  • 30.深入淺出介紹史上最偉大的加密算法:RSA算法
    聽上去好像有些不可思議，但真就存在這樣的加密方式，這就是史上最偉大的加密算法：RSA算法。一個簡單的示例我們先用一個簡單的示例來演示一下RSA算法的加密過程。如此看來，RSA算法不是非常容易破解嗎？其實RSA算法的真正奧秘不在於你不知道怎麼破解，而是你明明知道怎麼破解，可就是破解不了。
  • 全球主流社交媒體算法解析:Facebook、YouTube、Twitter等平臺如何...
    話雖如此，據報導，截止2018年10月，平均推文長度仍然只有35個字符。我們對Twitter算法了解多少？通過將這些因素輸入到算法中，能夠為每個用戶生成個性化的新聞信息流，使用戶能夠獲得自己所需的交流對話，這些對話能幫助他們更具成效，並走向成功。知識圖表和計劃中的興趣圖表將改變LinkedIn算法2016年，LinkedIn發布了一篇詳細介紹其「知識圖表」的帖子，該內容基於用戶的職位，職務，技能，公司，地理位置，學校等。
  • 你不得不看的最重要的算法類型
    算法： 算法是解決問題的分步過程。一個好的算法應該在時間和空間上進行優化。不同類型的問題需要以最優化的方式解決不同類型的算法技術。世界上有很多類型的算法，但是本文將討論您必須知道的最重要和最基本的算法。
  • 床長人工智慧教程pdf下載網校——洗牌算法
    在深入討論之前，必須先定義出一個基本概念究竟洗牌算法的本質是什麼？也就是說，什麼樣的洗牌結果是正確的？雲風曾經有一篇博文，專門討論了這個問題，他也給出了一個比較確切的定義，在經過洗牌函數後，如果能夠保證每一個數據出現在所有位置的概率是相等的，那麼這種算法是符合要求的。
  • 從經典算法題看時間複雜度
    下面我將通過一些較為經典的算法題聊一聊幾種常見的時間複雜度。什麼是時間複雜度？算法的時間複雜度（Time complexity）是一個函數，用於定性描述算法的運行時間。提出時間複雜度的目的是：分析與比較完成同一個任務而設計的不同算法。
  • 構建GNN 的「統一場」:從與 WL 算法、組合優化算法的聯繫看 GNN...
    在第 2 章中，我們看到 GNN 不能使用基本的參數和具體的示例來區分某些圖。在第 3 章中，我們介紹了 GNN 和 WL 算法之間的聯繫。在第 4 章中，我們根據 GNN 與分布式局部算法的聯繫，介紹了 GNN 可以/不可以求解的組合優化問題。在第 5 章中，我們將 GNN、WL 算法，以及分布式局部算法之間的關係總結為「XS 一致性」（XS correspondence）。