什么是圖

涉及權(quán)重的圖，被稱為帶權(quán)圖(Weighted Graph)

圖的存儲(chǔ)方式有很多種，最常用的方式包括鄰接矩陣和鄰接表

鄰接矩陣

擁有n個(gè)頂點(diǎn)的圖，它所包含的連接數(shù)量最多是n×(n-1)個(gè)。因此，要表達(dá)各個(gè)頂點(diǎn)之間的關(guān)聯(lián)關(guān)系，最清晰易懂的方式是使用n×n的二維數(shù)組(矩陣)。

像這樣表達(dá)圖中頂點(diǎn)關(guān)聯(lián)關(guān)系的矩陣，就叫作鄰接矩陣

無向圖對(duì)應(yīng)的矩陣是一個(gè)對(duì)稱矩陣；

矩陣從左上到右下的一條對(duì)角線，其上的元素值必然是0

鄰接矩陣的優(yōu)點(diǎn)：簡(jiǎn)單直觀，可以快速查到一個(gè)頂點(diǎn)和另一頂點(diǎn)之間的關(guān)聯(lián)關(guān)系

鄰接矩陣的缺點(diǎn)：占用了太多的空間

鄰接表

為了解決鄰接矩陣占用空間的問題，人們想到了另一種圖的表示方法：鄰接表

圖的遍歷

遍歷圖的兩種主要方式：深度優(yōu)先遍歷簡(jiǎn)稱DFS(Depth First Search)，廣度優(yōu)先遍歷簡(jiǎn)稱BFS(Breadth First Search)

先深入探索，走到頭再回退尋找其他出路的遍歷方式，就叫作深度優(yōu)先遍歷(DFS)

樣一層一層由內(nèi)而外的遍歷方式，就叫作廣度優(yōu)先遍歷(BFS)

圖的最短路徑

迪杰斯特拉算法的原理：這個(gè)算法的本質(zhì)，是不斷刷新起點(diǎn)與其他各個(gè)頂點(diǎn)之間的“距離表”。

時(shí)間復(fù)雜度可以優(yōu)化到O(elogn)

迪杰斯特拉算法的主要目標(biāo)，是求出圖中頂點(diǎn)A到頂點(diǎn)B的最短路徑，但也順便得到了一個(gè)有價(jià)值的副產(chǎn)品，就是求出了從頂點(diǎn)A到其他所有頂點(diǎn)的最短路徑，因此，迪杰斯特拉算法被稱為圖的單源最短路徑算法。

圖的多源最短路徑

弗洛伊德算法，專門用于尋找圖的多源最短路徑。

小結(jié)

圖是一種多對(duì)多的數(shù)據(jù)結(jié)構(gòu)，最基本的單元是頂點(diǎn)，頂點(diǎn)之間由邊關(guān)聯(lián)；

無權(quán)圖的邊沒有權(quán)重概念；帶權(quán)圖的每一條邊擁有自己的權(quán)重；

無向圖的頂點(diǎn)關(guān)聯(lián)是對(duì)稱的；有向圖的頂點(diǎn)關(guān)聯(lián)不完全對(duì)稱，頂點(diǎn)A觸達(dá)頂點(diǎn)B，頂點(diǎn)B未必觸達(dá)頂點(diǎn)A；

圖的主要存儲(chǔ)方式包括鄰接矩陣和鄰接表/逆鄰接表；

圖的遍歷方式，分為深度優(yōu)先遍歷和廣度優(yōu)先遍歷；

尋找圖的單源最短路徑，可以使用迪杰斯特拉（Dijkstra）算法；尋找圖的多源最短路徑，可以使用弗洛伊德（Floyd）算法