• (??? )，Hello我是祐言QAQ
• 我的博客主頁：C/C++語言，Linux基礎(chǔ)，ARM開發(fā)板，軟件配置等領(lǐng)域博主🌍
• 快上🚘，一起學(xué)習(xí)，讓我們成為一個(gè)強(qiáng)大的攻城獅！
• 送給自己和讀者的一句雞湯🤔：集中起來的意志可以擊穿頑石!
• 作者水平很有限，如果發(fā)現(xiàn)錯(cuò)誤，可在評(píng)論區(qū)指正，感謝🙏

一、什么是圖

???????? 圖是一種由節(jié)點(diǎn)（頂點(diǎn)）和連接這些節(jié)點(diǎn)的邊構(gòu)成的非線性數(shù)據(jù)結(jié)構(gòu)。每個(gè)節(jié)點(diǎn)可以表示一個(gè)實(shí)體，而邊則表示節(jié)點(diǎn)之間的關(guān)系。圖的設(shè)計(jì)可以用于模擬現(xiàn)實(shí)世界中的各種復(fù)雜關(guān)系和連接，從社交網(wǎng)絡(luò)到通信網(wǎng)絡(luò)，都可以通過圖來更好地理解和分析。

二、圖的分類

????????圖可以根據(jù)多個(gè)維度進(jìn)行分類：

• 有向圖（Directed Graph）和無向圖（Undirected Graph）： 有向圖中的邊具有方向，表示從一個(gè)節(jié)點(diǎn)指向另一個(gè)節(jié)點(diǎn)的關(guān)系；而無向圖中的邊沒有方向，表示兩個(gè)節(jié)點(diǎn)之間的對(duì)等關(guān)系。

• 有權(quán)圖（Weighted Graph）和無權(quán)圖（Unweighted Graph）： 在有權(quán)圖中，每條邊都有一個(gè)權(quán)重，可以表示節(jié)點(diǎn)之間的某種度量，如距離、成本等；而在無權(quán)圖中，邊沒有權(quán)重，只表示連接關(guān)系。

• 簡(jiǎn)單圖和多重圖（Multigraph）： 簡(jiǎn)單圖中不存在自環(huán)和重復(fù)的邊；而多重圖允許自環(huán)和可能具有相同的邊。

三、圖的邊

????????圖的邊是連接節(jié)點(diǎn)的實(shí)體，它可以包含以下信息：

• 權(quán)重（Weight）： 如果是有權(quán)圖，每條邊都有一個(gè)權(quán)重，代表節(jié)點(diǎn)之間的某種度量。
• 方向： 在有向圖中，邊從一個(gè)節(jié)點(diǎn)指向另一個(gè)節(jié)點(diǎn)，有方向性；在無向圖中，邊沒有方向，表示雙向關(guān)系。
• 標(biāo)簽（Label）： 可以為邊添加標(biāo)簽，表示連接的類型或特性。

????????有些圖的邊或弧具有與它相關(guān)的數(shù)字，這種與圖的邊或弧相關(guān)的數(shù)叫做權(quán)，表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或花費(fèi)或時(shí)間。我們稱這種帶權(quán)的圖為網(wǎng)。如下圖所示，即為網(wǎng)。

?

四、圖的表達(dá)方式

????????圖可以使用不同的數(shù)據(jù)結(jié)構(gòu)來表示：

• 鄰接矩陣（Adjacency Matrix）： 使用二維數(shù)組表示圖的頂點(diǎn)之間的連接關(guān)系。矩陣的行和列分別代表頂點(diǎn)，矩陣元素表示邊的存在與否或權(quán)重。

????????????????????????????????????????????????????????圖中 1 表示相連接，0 表示不相連

• 鄰接表（Adjacency List）： 使用鏈表或數(shù)組表示圖的頂點(diǎn)以及與其相鄰的頂點(diǎn)。每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)列表，包含與之相連的頂點(diǎn)。

?

五、圖的遍歷

????????圖遍歷是訪問圖中所有節(jié)點(diǎn)的方法，有兩種主要方法：

• 深度優(yōu)先搜索（DFS）： 從起始節(jié)點(diǎn)開始，沿著一條路徑盡可能深入，直到無法繼續(xù)為止，然后回溯到之前的節(jié)點(diǎn)，繼續(xù)探索其他路徑。

1.遍歷思路

• 訪問頂點(diǎn)v；
• 從v的未被訪問的鄰接點(diǎn)中選取一個(gè)頂點(diǎn)w，從w出發(fā)進(jìn)行深度優(yōu)先遍歷；
• 重復(fù)上述兩步，直至圖中所有和v有路徑相通的頂點(diǎn)都被訪問到。

2.列舉

????????按深度優(yōu)先遍歷就是：A B C D E F G H(此時(shí)這條線路已經(jīng)走到盡頭，可是還有一個(gè)I頂點(diǎn)沒有遍歷，所以回到G，發(fā)現(xiàn)G的鄰接點(diǎn)都遍歷過了，再回到F，發(fā)現(xiàn)F的鄰接點(diǎn)也都遍歷過了，直到D頂點(diǎn)，發(fā)現(xiàn)I這個(gè)頂點(diǎn)沒有遍歷，所以把I再遍歷，繼續(xù)回溯，最終回到起點(diǎn)A。

??????

• 廣度優(yōu)先搜索（BFS）： 從起始節(jié)點(diǎn)開始，先訪問所有與其直接相鄰的節(jié)點(diǎn)，然后逐層向外擴(kuò)展，確保先訪問離起始節(jié)點(diǎn)近的節(jié)點(diǎn)。

1.遍歷思路

• 從圖中某個(gè)頂點(diǎn)V0出發(fā)，并訪問此頂點(diǎn)；
• 從V0出發(fā)，訪問V0的各個(gè)未曾訪問的鄰接點(diǎn)W1，W2，…,Wk;然后,依次從W1,W2,…,Wk出發(fā)訪問各自未被訪問的鄰接點(diǎn)；
• 重復(fù)步驟2，直到全部頂點(diǎn)都被訪問為止。

2.列舉?

六、圖的算法

????????圖的算法是一個(gè)重要的主題，包括最短路徑、連通性、最大流、最小生成樹等問題。比如Dijkstra算法可以用于尋找圖中的最短路徑，Kruskal算法和Prim算法可以用于求解最小生成樹問題。這些算法的選擇和應(yīng)用取決于圖的特性和問題的需求。

七、適用說明

????????圖的應(yīng)用范圍廣泛，包括但不限于：

• 社交網(wǎng)絡(luò)分析： 用于分析人際關(guān)系、社區(qū)發(fā)現(xiàn)、信息傳播等。
• 路線規(guī)劃： 幫助找到最短路徑、最優(yōu)路線，應(yīng)用于導(dǎo)航和交通規(guī)劃。
• 計(jì)算機(jī)網(wǎng)絡(luò)： 描述計(jì)算機(jī)之間的連接、拓?fù)浣Y(jié)構(gòu)，用于網(wǎng)絡(luò)設(shè)計(jì)和分析。
• 編譯器： 用于構(gòu)建控制流圖、數(shù)據(jù)依賴圖，進(jìn)行代碼優(yōu)化和分析。

????????圖還可以用于生物信息學(xué)（比如在蛋白質(zhì)相互作用網(wǎng)中尋找功能模塊）、物聯(lián)網(wǎng)（比如在設(shè)備間建立最優(yōu)的通信路徑）等領(lǐng)域。

????????總之，圖是一個(gè)強(qiáng)大的數(shù)據(jù)結(jié)構(gòu)，能夠捕捉和表示各種實(shí)體之間的關(guān)系，為解決各種復(fù)雜問題提供了有效的工具。不同類型的圖和圖遍歷算法可以根據(jù)問題的性質(zhì)和需求來選擇使用。

????????更多C語言、Linux系統(tǒng)、ARM板實(shí)戰(zhàn)和數(shù)據(jù)結(jié)構(gòu)相關(guān)文章，關(guān)注專欄：

? ?手撕C語言

? ? ? ? ? ? 玩轉(zhuǎn)linux

????????????????????腳踢數(shù)據(jù)結(jié)構(gòu)

?? ? ? ? ? ? ? ? ?? ? ? ? ? 6818（ARM）開發(fā)板實(shí)戰(zhàn)

📢寫在最后

• 今天的分享就到這啦~
• 覺得博主寫的還不錯(cuò)的煩勞?一鍵三連喔~
• 🎉感謝關(guān)注🎉