用圖形解釋10種圖形算法

2020-12-12 51CTO

快速介紹10種基本圖形算法以及示例和可視化

在現實世界中，例如社交媒體網絡，網頁和連結以及GPS中的位置和路線，圖形已經成為一種強大的建模和捕獲數據的手段。 如果您有一組相互關聯的對象，則可以使用圖形來表示它們。

> Image by Author

在本文中，我將簡要說明10種基本圖形算法，這些算法對於分析及其應用非常有用。

首先，讓我們介紹一個圖表。

什麼是圖?

一個圖由一組有限的頂點或節點以及一組連接這些頂點的邊組成。 如果兩個頂點通過同一邊彼此連接，則它們稱為相鄰頂點。

下面給出一些與圖有關的基本定義。 您可以參考圖1的示例。

  • 順序：圖形中的頂點數
  • 大小：圖形中的邊數
  • 頂點度：入射到頂點的邊數
  • 孤立的頂點：未連接到圖中任何其他頂點的頂點
  • 自環：從頂點到自身的邊
  • 有向圖：所有邊都有一個方向的圖，該方向指示什麼是起始頂點，什麼是終止頂點
  • 無向圖：具有沒有方向的邊的圖
  • 加權圖：圖的邊緣具有權重
  • 未加權圖形：圖形的邊緣沒有權重

> Fig 1. Visualization of Terminology of Graphs (Image by Author)

1.廣度優先搜索

> Fig 2. Animation of BFS traversal of a graph (Image by Author)

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

圖2表示示例圖的BFS遍歷的動畫。 注意如何發現頂點(黃色)並訪問頂點(紅色)。

應用領域

  • 用於確定最短路徑和最小生成樹。
  • 搜尋引擎搜尋器用來構建網頁索引。
  • 用於在社交網絡上搜索。
  • 用於查找對等網絡(例如BitTorrent)中的可用鄰居節點。

2.深度優先搜索

> Fig 3. Animation of DFS traversal of a graph (Image by Author)

在深度優先搜索(DFS)中，我們從特定的頂點開始，並在回溯(回溯)之前沿每個分支進行儘可能的探索。 在DFS中，我們還必須跟蹤訪問的頂點。 在實現DFS時，我們使用堆棧數據結構來支持回溯。

圖3表示與圖2相同的示例圖的DFS遍歷的動畫。請注意，它如何遍歷深度和回溯。

應用領域

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

3.最短路徑

> Fig 4. Animation showing the shortest path from vertex 1 to vertex 6 (Image by Author)

從一個頂點到另一個頂點的最短路徑是圖形中的一條路徑，因此應移動的邊的權重之和最小。

圖4顯示了一個動畫，其中確定了圖形中從頂點1到頂點6的最短路徑。

演算法

  • Dijkstra最短路徑算法
  • Bellman–Ford算法

應用領域

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

> Image by Daniel Dino-Slofer from Pixabay

4.循環檢測

> Fig 5. A cycle (Image by Author)

循環是圖形中的第一個頂點和最後一個頂點相同的路徑。 如果我們從一個頂點開始，沿著一條路逕行進，然後在起始頂點處結束，那麼這條路徑就是一個循環。 循環檢測是檢測這些循環的過程。 圖5顯示了遍歷一個循環的動畫。

演算法

應用領域

  • 用於基於分布式消息的算法。
  • 用於在群集上使用分布式處理系統處理大規模圖形。
  • 用於檢測並發系統中的死鎖。
  • 在加密應用程式中用於確定消息的密鑰，該密鑰可以將該消息映射到相同的加密值。

5.最小生成樹

> Fig 6. Animation showing a minimum spanning tree (Image by Author)

最小生成樹是圖的邊緣的子集，該圖以最小的邊權重之和連接所有頂點，並且不包含循環。

圖6是一個動畫，顯示了獲取最小生成樹的過程。

演算法

應用領域

  • 用於構造樹以在計算機網絡中廣播。
  • 用於基於圖的聚類分析。
  • 用於圖像分割。
  • 用於將社會區域劃分為連續區域的社會地理區域的區域化。

6.牢固連接的組件

> Fig 7. Strongly connected components (Image by Author)

如果圖中的每個頂點均可從其他每個頂點到達，則稱該圖是牢固連接的。

圖7顯示了一個示例圖，其中包含三個具有紅色，綠色和黃色的頂點的牢固連接的組件。

演算法

  • Kosaraju的算法
  • Tarjan的強連接組件算法

應用領域

  • 用於計算Dulmage–Mendelsohn分解，這是二部圖邊緣的分類。
  • 用於社交網絡中，以找到一群緊密聯繫並根據共同興趣提出建議的人。

> Image by Gerd Altmann from Pixabay

7.拓撲排序

> Fig 8. A topological ordering of vertices in a graph (Image by Author)

圖的拓撲排序是其頂點的線性排序，因此對於排序中的每個有向邊(u，v)，頂點u都位於v之前。

圖8顯示了頂點(1、2、3、5、4、6、7、8)的拓撲順序的示例。 您可以看到頂點5應該位於頂點2和3之後。類似地，頂點6應該位於頂點4和5之後。

演算法

應用領域

  • 用於指令調度。
  • 用於數據序列化。
  • 用於確定在makefile中執行的編譯任務的順序。
  • 用於解析連結器中的符號依賴性。

8.圖形著色

> Fig 9. Vertex colouring (Image by Author)

圖形著色可在確保某些條件的同時為圖形元素分配顏色。 頂點著色是最常用的圖形著色技術。 在頂點著色中，我們嘗試使用k種顏色為圖形的頂點著色，並且任何兩個相鄰的頂點都不應具有相同的顏色。 其他著色技術包括邊緣著色和面部著色。

圖的色數是為圖著色所需的最少顏色數。

圖9顯示了使用4種顏色的示例圖的頂點著色。

演算法

應用領域

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

> Image by TheAndrasBarta from Pixabay

9.最大流量

> Fig 10. Determining the maximum flow (Image by Author)

我們可以將圖建模為以邊權重為流量的流量網絡。 在最大流量問題中，我們必須找到一條可以獲得最大可能流量的流路。

圖10顯示了確定網絡的最大流量並確定最終流量值的動畫示例。

演算法

  • 福特-福克森算法
  • Edmonds–Karp算法
  • Dinic的算法

應用領域

  • 用於航空公司調度以調度飛行人員。
  • 用於圖像分割以查找圖像中的背景和前景。
  • 用於淘汰無法贏得足夠比賽來趕上其所在部門的領先者的棒球隊。

10.匹配

> Fig 11. Matching of a bipartite graph (Image by Author)

圖中的匹配項是一組沒有共同頂點的邊(即，沒有兩個邊共享共同的頂點)。 如果匹配包含儘可能多的與儘可能多的頂點匹配的邊，則該匹配稱為最大匹配。

圖11顯示了獲得二部圖與橙色和藍色表示的兩組頂點的完全匹配的動畫。

演算法

  • Hopcroft-Karp算法
  • 匈牙利算法
  •  開花算法

應用領域

  • 用於對接會以匹配新娘和新郎(穩定的婚姻問題)。
  • 用於確定頂點覆蓋率。
  • 在運輸理論中用於解決資源分配和出行優化中的問題。

最後的想法

我希望您覺得這篇文章對圖形算法進行簡單而概括的介紹很有用。 我很想聽聽您的想法。

非常感謝您的閱讀。

【責任編輯：

未麗燕

TEL：（010）68476606】

點讚 0

相關焦點

  • Android圖形鎖不安全 黑客試五次就可以破解
    目前Android用戶有40%使用圖形鎖，比起PIN密碼和文本密碼，他們更喜歡圖形鎖。蘭卡斯特大學（Lancaster University）、中國西北大學、英國巴斯大學（University of Bath）的研究人員在報告中指出，只需要嘗試5次黑客就可以破解圖形鎖進入手機。事實上，你使用的圖形越複雜越容易破解。
  • 不可能圖形的啟示
    不可能圖形解釋：（別稱：錯覺圖片、二維圖形） 是指在現實世界中，不可能客觀存在的事物，僅會在二維世界存在的一種圖形；不可能圖形是由人的視覺系統瞬間意識地對一個二維圖形的三維投射而形成的光學錯覺，在三維空間中它不可能存在。
  • 是什麼阻礙了圖形資料庫的擴展?
    資料庫技術能夠快速分析相關度高的數據點以及其之間的聯繫，圖形資料庫便是其中之一。但由於圖形數據本身性質特殊，其在架構方面還面臨諸多挑戰。那麼，圖形資料庫是否能夠擴展呢？本文將全面分析可能阻礙圖形資料庫擴展的兩個挑戰，並討論當前可用的解決方案。什麼是"圖形資料庫的可擴展性"？
  • 圖形創意的表現方式你知道幾種?
    圖形創意的表現方式你知道幾種？眾所周知，圖形創意在視覺傳達方面非常具有優越性，因為圖形的生動性，識別性，直觀性以及幽默性能夠給人帶來強烈的視覺感受，圖形創意還有一個優勢，則是國際性，如果說文字和語言是有國界的，那麼圖形是不受地域文化年齡限制的。這也從側面反映了圖形設計的重要性。
  • 圖形推理概述
    根據圖形外觀的某些特徵，將其細化為幾類，每類對應少數相關規律。圖形推理的分類特徵如下：單純簡約結構圖形，是指基本由粗細均勻的線條組成，極少出現色塊或陰影的圖形。這類圖形結構相對簡單，構成圖形的元素種類一般不會太多，圖形間常存在明顯的差異性。
  • 圖形設計八大表現手法!妙不可言
    文/李玉霞 隨著讀圖時代的到來，圖形逐漸成為人們溝通交流的一 種視覺語言形式。 圖形從狹義上解釋就是指形象、色彩、質感、量感等因素及它們之間的組織構成關係。圖形設計為了便於形象的傳播，易於消費者理解記憶，要求圖形創意的形式必須簡潔、明快、富有感染力。
  • 揭開圖形設計的面紗!圖形創意方法
    文/紀娜 首先，何為圖形創意？圖形創意一般是指設計師為了達到其設計目的，而對對象圖形作的一種處理，這類處理總結起來不外乎兩種：①在不改變其對象屬性的前提下進行變形，使其符合設計主題的要求。圖形創意沒有太大的思維跨越，只需對對象圖形作一些處理，例如：適當提煉、誇張、單純化或添加、歸納、構成等等。②為達到設計目的，不擇手段、無中生有地創造出不合常理和邏輯的圖形。我們天馬行空，只要握住主題這根線，可任圖形任意幻化、變異，創造出奇異的視覺效果。
  • 中班數學教案《圖形王國》
    一、活動目標：1、讓幼兒認識圓形、三角形、正方形 、長方形，能夠區分幾何圖形。2、能夠用幾何圖形拼組成圖畫。④教師：幼兒摸出圖形問：這是什麼，他是什麼形狀的，並說出常生活中有哪些圖形是圓形、三角形、正方形、長方形。（PPT）教師小結：剛我們在這個魔術箱裡都摸出了什麼圖形。
  • 訊飛輸入法新增圖形顏文字
    實不相瞞，隨著智慧型手機普及，由另一種「符號」組成的顏文字更成為了表情界的弄潮兒。日前，訊飛輸入法Android V10.0.2版新增圖形顏文字，成為網絡表情包的擔當。早在2015年，訊飛輸入法聯合B站開啟「顏文字の補全計劃」，促進顏文字的大發展。現在打開訊飛輸入法的表情，不僅有琳琅滿目的顏文字，還支持自定義顏文字等，展示出高超的「顏藝」。
  • 圖形創意設計技法!巧用聯想
    文/向素傑 現代圖形設計往往通過對沒有特殊意義的要素，進行發掘、轉換、結合，以超現實的視覺意象與心理聯想，創作岀新穎、生動、獨特的視覺形式，使圖形看起來更加富於激情和張力。進行圖形創意需要在短的時間內抓住事物的本質，能揭露客觀事物本質的、內在的聯繫，而且要在此基礎上產生新穎的、前所未有的思維成果。
  • 手繪|用頭腦風暴做圖形創意,真香
    圖形創意是視覺傳達基礎科目，也是海報、包裝等科目不可獲取的創意表現手法。很多高校在視傳的手繪考題中，關於圖形創意的考題層出不窮，並樂此不疲。由此可見，圖形創意對於視傳考研黨來說是必須掌握以及熟練運用的上岸利器！知道了圖形創意的重要性之後，我們到底應該怎樣去練習呢？
  • 不止於美:淺析信息圖形設計
    信息圖形由信息和圖形兩個詞語組成，它被稱之為「信息圖形」（Infographics或Information Graphics）。信息圖形最初是用在報紙、雜誌、新聞等媒體刊登的一般圖解。圖解這個詞在國內外使用了多年，它只是為了充分利用信息，而將這些信息進行功能性的整理。有時候，信息圖形也會運用符合各種文化習慣的比喻等手法，以不同的形式來表達。
  • 案例賞析:日本靜岡縣富士山世界遺產中心解釋展示圖形
    日本靜岡縣富士山世界遺產中心解釋展示圖形
  • 圖形創意設計方法!無中生有
    新奇是圖形設計引人注目的方法，是不可忽視的圖形創意規律。有新奇感的圖形使主題得到深化與升華、引人入勝。在當今這個快節奏、信息爆炸的社會中，明確、直觀的圖形以及視覺衝擊力不僅能夠使信息傳遞更為有效、快速，而且具備一定的欣賞價值，在給人們帶來視覺享受的同時還能夠引發受眾群體的心理共鳴，其中傳遞的信息量甚至已經超過了圖形創意本身。
  • 盤點英語中表示「圖形「的詞彙
    英語中表示「圖形」的單詞很多，如何才能將這些近義詞的具體內在 含義和用法搞清楚?下面我們一一做些解釋： 　　1.Figure 　　figure通常指幾何圖形或圖案;此外書中的插圖不管是什麼圖都可以用 figure表示： 　　Figure 5 is the schematic diagram of a d/a converter. (圖5是數/模轉換器的原理圖 ) 　　2.
  • 用圖形,讓PPT更有型
    製作PPT時，經常需要用到圖形，那如何讓圖形更出彩，更有型呢？第一招：設置透明度左下圖是從SmartArt中插入的，具有透明效果的圖形。第一步：選擇【插入】選項中的【SmartArt】，在打開的【選擇SmartArt圖形】對話框中找到【關係】中的【基本維恩圖】；第二步：選擇圖形，將圖形成比例縮小，選中當中的圓形，打開【格式】選項卡中的【形狀填充】，選擇【其他填充顏色】，在打開的【顏色】對話框中選擇顏色，並設置透明度，本例設置為45%，單擊【確定】即可實現透明效果
  • 大班數學教案:分析圖形特徵
    活動準備： 　　1、教具：課件圖形特徵表格，幾何圖形若干。（附後） 　　2、學具：每人一張記錄表格。每人一個普通幾何圖形、一個背後貼有半個心形的幾何圖形、筆 　　3、環境：布置尋寶地。 　　活動過程： 　　流程：交流圖形特徵  學看圖示分析圖形特徵  給特定圖形記錄特徵  分析圖形特徵尋找標誌 　　1、以小天使來到班上送禮物，尋找最幸運小朋友引題。 　　（1） 引：讓我們用最熱烈的掌聲來歡迎小客人吧！
  • 小學數學:平面圖形的複習,圖形特點,計算公式
    小學數學裡學過的平面圖形主要有長方形、正方形、平行四邊形、梯形、三角形、圓形、圓環、扇形等。下面我就對這些平面圖形進行分析、歸納。並製作了相應的導圖，便於複習、記憶。平面圖形1、長方形（1）特點：長方形的對邊相等，4個角都是直角的四邊形。
  • 圖形創意設計「六字訣」!
    文/鄭國喜 在圖形設計中，如何從圖形的 影像、圖形的疊加關係、圖形的放置方式、圖形的切割變化、圖形的邏輯關係等方面進行變化，使圖形成為整個設計作品的「點睛之筆」。這就要求圖形設計要應符合以下五項基本要求：①典型性，即個性，變化以後的形與其他圖形有明顯的區別，這類圖形便於品牌個性的塑造與消費者記憶的形成。
  • 圖形創意表現手法!扣人心弦
    拼置同構是將兩個以上的物形各取部分拼合成一個新形象的圖形構建方式。②置換同構。置換同構又稱替代同構，指在保持原形的基本特徵基礎上，物體中的某一部分被其他物形素材所替代的一種圖形構造形式，從而產生具有新意的形象。③置入同構。