數據結構與應用中的圖類型
已發表: 2022-11-25介紹
圖是包含節點和邊的非線性結構。 它可以包括由連接一對節點的邊所持有的一組有限或無限節點。 數據結構是任何編碼概念的重要組成部分； 因此，牢牢掌握數據結構中不同類型的圖可以幫助您解決複雜的現實世界問題。
在當今世界，數據就是力量。 因此，有效地組織數據以便於訪問對任何程序員來說都是必不可少的。 數據結構及其各種圖表的知識使您的編碼技能能夠針對現實世界的問題並有效地提供其解決方案。
學習數據科學以獲得超越競爭對手的優勢
讓我們來看看數據結構中常用的不同類型的圖，以及它們在現實生活中的應用。
數據結構中的圖類型
數據結構是所有語言的實用數據存儲標準，例如python圖數據結構或java圖數據結構。 掌握所有類型的圖應該是任何有志於研究數據結構的人的首要任務。 由於圖論在現實生活中有許多應用，因此它們在數據結構中變得至關重要。
數據結構中的各種圖類型如下：
1.空圖
顧名思義，空圖是空的； 換句話說，它是一個沒有邊的圖。 它僅由圖中的孤立頂點和空邊集組成。
2. 有限圖
如果邊和節點的數量由圖中的有限個數組成，則該圖稱為有限圖。
3.無限圖
如果一個圖中的節點數和邊數不能為有限數，則該圖稱為無限圖。 無限圖是不可數的，這意味著您無法計算此類圖中節點或邊的數量。
4. 簡單圖
當一對頂點之間只有一條邊時，稱圖是簡單圖。 因此，圖中兩個節點由一條邊連接，可以確定它們之間的關係。
5.多圖
如果一對節點與圖中的多條邊相連，則該圖稱為多圖。 多圖不包含自環。 多圖中可以存在兩種邊。 他們是：
平行邊
平行的邊，就像從一個源頭到同一目的地的兩條平行道路，被稱為平行邊。
環形
這是一條源頂點和目標頂點相同的邊。
檢查我們的美國 - 數據科學計劃
| 數據科學和商業分析專業證書課程 | 數據科學理學碩士 | 數據科學理學碩士 | 數據科學高級證書課程 |
| 數據科學執行 PG 計劃 | Python 編程訓練營 | 商業決策數據科學專業證書課程 | 數據科學高級課程 |
6.有向圖
如果兩個節點或頂點之間存在的所有邊都具有定義的方向，則稱該圖是有向的。 有向圖也稱為有向圖。 我們可以通過查看有向圖來確定起始和結束節點。 請記住，有向圖中的所有邊都必須是有向的才能稱為有向圖。
7. 無向圖
如果很難通過查看圖的邊來識別起始節點和結束節點，則稱該圖為無向圖。 就像有向圖一樣，邊必須是無向的才能稱為無向圖。
8.連通圖
連通圖是所有節點之間至少存在一條路徑的圖。 簡單來說，如果您從連通圖中的一個節點開始，您應該能夠訪問圖中存在的每個節點。 因此，每個節點至少應該有一條路徑。
9.斷開連接的圖
在這種類型的圖中，一對節點或頂點之間不存在邊。 因此，與連通圖不同，從任何頂點到達所有節點是不可能的。 如果任何一對頂點之間沒有路徑，則稱為不連通圖。
10. 完整圖
只有當每個節點之間存在邊時，圖才被認為是完整的，這意味著邊將連接圖中的所有頂點。 n 個頂點的完整圖表示為Kn ，圖中的邊數為nC2 。
11.循環圖
一張圖應該至少有一個循環組件才能被認為是循環圖。 相反，如果圖不包含任何循環，則認為它是無環圖。
12.正則圖
在正則圖中，所有頂點的度數應該相同。 節點的度可以定義為與其相連的節點數。 因此，在規則圖中，所有節點都應連接到相同數量的節點。
13.二分圖
對於二分圖，它應該滿足以下條件。
- 該圖應分為頂點集。
- 邊應該只在一組節點到另一側之間形成。 此規則防止同一組節點的兩個頂點之間的連接。
- 這兩個組之間不應有任何公共頂點。
遵循上述所有規則的圖應被視為二分圖。
14. 標記圖
圖中的邊可以被加權。 與邊緣關聯的權重可以理解為通過該邊緣的成本。 這些值可以基於固定參數並且可以在圖形之間改變。 現在，如果所有的邊都持有一些與之相關的權重，那麼該圖可以稱為標記圖。
15.有向無環圖
有向無環圖是有向圖和無環圖的組合，其中圖的有向邊不形成任何形式的循環。 相反，有向循環圖是具有形成循環的有向邊的圖。
圖在數據結構中的應用
圖在計算機科學中最突出的應用是計算流的表示。 圖的其他一些著名用例是：
1.谷歌地圖
在谷歌地圖中，圖形數據結構定義和計算交通系統。 當一條道路與另一條道路相遇並形成交叉路口時，它被認為是一個節點，而兩個這樣的節點之間的道路被視為一條邊。 因此，谷歌地圖使用圖形數據結構為您找到到達目的地的最短和最快的方式。
2.臉書
Facebook 使用無向圖來識別用戶和用戶的朋友。 每個用戶都被視為頂點，將他們作為朋友加入的連接是網絡的邊緣。 借助基於圖形數據結構的算法，Facebook 會建議“您可能認識的人”並顯示“共同的朋友”。
3.萬維網
萬維網是有向圖的一個例子。 這也是谷歌排名系統背後的基本思想。 在萬維網系統中，每個網站和網絡應用程序都被視為一個節點或頂點，從一個網站到另一個網站的鏈接被視為邊緣。
4. 操作系統
操作系統是資源分配圖的一個常用案例，它使用每個進程和資源作為節點或頂點。 邊緣出現在資源到分配的進程之間或從請求進程到請求的資源之間。 有時這個循環可能會形成一個無限循環，初始化死鎖。
5. 地圖系統
您的 GPS 是一種廣泛使用的圖形案例，可藉助該技術定位附近的餐館、商店和您選擇搜索的地點。
6.微軟Excel
Microsoft Excel 中使用有向無環圖或 DAG。
7. Dijkstra算法
Dijkstra 算法使用圖形數據結構來識別兩個節點之間的最短路徑，或者在某些情況下，識別兩個以上節點之間的最短路徑。
8. 飛行網絡：
計算優化的飛行網絡是圖數據結構的另一個現實應用。 如果將機場視為節點，將路線視為邊，則數據完全符合圖表的標準。 這就是為什麼在各種增強算法的幫助下，可以確定兩個機場或節點之間的最佳路線。
這些是圖形在數據結構中的各種應用，在全球範圍內用於各種應用程序和系統，以組織和維護它們的平穩運行，
開始你的數據科學家之旅
如果你想成為一名數據科學家並使用我們學到的各種圖表巧妙地處理數據，請查看 upGrad 上範圍廣泛的數據科學課程。 最受歡迎的課程之一是關於數據科學的 PG-IIITB 課程，這是一門適合有抱負和嶄露頭角的數據科學家入門的優秀課程！
這是課程提供的內容。
- 來自行業專家和導師的 360 度職業支持
- 行業項目的實踐經驗和詳細的案例研究，以衡量常規進展
- 與全球所有部門的數據科學專家建立聯繫
您還可以查看有關數據科學的所有其他upGrad 課程。