1.? 什么是圖
圖由點(diǎn)和邊組成。
邊上有箭頭叫有向圖，沒(méi)箭頭叫無(wú)向圖。
邊上的數(shù)值叫做權(quán)重，有權(quán)重的圖叫有權(quán)圖。
有環(huán)形回路的圖叫做有環(huán)圖。
圖用于模擬不同的東西是如何連接的。
2.圖的表示
圖的表示方式先確定好，這關(guān)系到之后在實(shí)現(xiàn)遍歷算法的時(shí)候如何訪問(wèn)圖上的節(jié)點(diǎn)和權(quán)重等信息。
兩種表示方式：鄰接矩陣、鄰接表
以表示下面的圖為例，下圖是一個(gè)帶權(quán)值的有向圖，頂點(diǎn)為：V0-V5，邊上的數(shù)值為權(quán)重
?（1）鄰接矩陣
（2）連接表，在圖特別系數(shù)的情況下，鏈接表更有效
鄰接矩陣比較容易理解不再贅述，補(bǔ)充一個(gè)鏈接表的使用方法。
一種用數(shù)組實(shí)現(xiàn)鏈接表的方式（目前還不會(huì)其他方式，會(huì)了再補(bǔ)充。方法出處《啊哈！算法》）
用三個(gè)數(shù)組存放數(shù)據(jù)，用三個(gè)數(shù)組完成表示，分別為u、v、w，u中存放起點(diǎn)，v中存放終點(diǎn)，w中存放對(duì)u和v中對(duì)應(yīng)兩點(diǎn)的間路徑的權(quán)重。還有個(gè)fist和next數(shù)組，這兩個(gè)比較難理解。
如上圖所示，共有4個(gè)節(jié)點(diǎn)，5條邊，u、v、w三個(gè)數(shù)組存放起始點(diǎn)和權(quán)重值。
first數(shù)組存放數(shù)組下標(biāo)對(duì)應(yīng)的節(jié)點(diǎn)第一次出現(xiàn)的位置，以節(jié)點(diǎn)1為例，在first數(shù)組中對(duì)應(yīng)的下標(biāo)就是1，讀入第一條邊，節(jié)點(diǎn)1出現(xiàn)，出現(xiàn)在u數(shù)組中的下標(biāo)為1，因此fisrt[1]=1；在讀入第三條邊的時(shí)候，節(jié)點(diǎn)1再次出現(xiàn)，此時(shí)在u中的下標(biāo)為3，更新first數(shù)組，fisrt[1]=3。注意這里的順序是反的，u[1]相比u[3]要先讀入，卻成了第二次出現(xiàn)，個(gè)人認(rèn)為反過(guò)來(lái)也無(wú)所謂。
next數(shù)組存放下一個(gè)對(duì)應(yīng)u中下標(biāo)的節(jié)點(diǎn)的下條邊出現(xiàn)的位置，有點(diǎn)繞，還以1為例，在加入第一條邊是，還沒(méi)有下條邊，也就是頂點(diǎn)u[1]現(xiàn)在只有一條邊，在讀入第三條邊之后，u[3]=1，并不是頂點(diǎn)1的唯一一條邊，那么下一條在哪呢，就是未更新之前的first[1]=1，所以在更新first之前，先next[3] = first[1]，然后first[1]=3.
怎么用這五個(gè)數(shù)組遍歷一個(gè)表，數(shù)組創(chuàng)建完整之后如下：
u={1, 4, 1, 2, 1}
v={4, 3, 2, 4, 3}
w={9, 8, 5, 6, 7}
first = {5, 4, -1, 2}
next = {-1, -1, 1, -1, 3}
遍歷節(jié)點(diǎn)1的所有邊的代碼如下：
k = first[1];
while(k != -1){
??????? printf(“%d to %d weight is %d \n”, u[k], v[k], w[k]);
??????? k=next[k];
}
遍歷整張圖的所有邊的代碼如下：
for(int i= 0; i < n -1; ++i) {
k = first[i];
while(k != -1){
??? printf(“%d to %d weight is %d\n”, u[k], v[k], w[k]);
??? k=next[k];
}
}
3.圖的遍歷
廣度優(yōu)先遍歷（Breath First）
廣度優(yōu)先和深度優(yōu)先主要的區(qū)別在于遍歷的順序。廣度優(yōu)先以一個(gè)未被訪問(wèn)過(guò)的頂點(diǎn)為起始頂點(diǎn)，訪問(wèn)與其相鄰的所有頂點(diǎn)，然后再訪問(wèn)相鄰點(diǎn)的未被訪問(wèn)過(guò)的所有相鄰點(diǎn)，直到訪問(wèn)完所有頂點(diǎn)。
用《圖解算法》中的方式來(lái)解釋，就是先殺熟。中間的“你”想知道周圍認(rèn)識(shí)的人中誰(shuí)是代購(gòu)，假設(shè)關(guān)系越近買東西越便宜，先問(wèn)一遍關(guān)系最近的也就是途中的一度關(guān)系，然后再問(wèn)一度關(guān)系朋友的朋友，也就是二度關(guān)系，方式跟遍歷一度關(guān)系一致，問(wèn)一遍一度關(guān)系中每個(gè)節(jié)點(diǎn)的所有相鄰節(jié)點(diǎn)。
廣度優(yōu)先遍歷需要用到隊(duì)列，來(lái)存放已經(jīng)訪問(wèn)過(guò)的點(diǎn)和確定接下來(lái)要訪問(wèn)的點(diǎn)。
代碼鏈接：https://github.com/Victcode/AlgorithmsLearning/blob/main/AhaAlgorithm/graph_bfs.cpp
深度優(yōu)先遍歷（Depth Fisrt）
從一個(gè)未被訪問(wèn)過(guò)的節(jié)點(diǎn)開始，訪問(wèn)與它相連的節(jié)點(diǎn)，直到訪問(wèn)到某個(gè)節(jié)點(diǎn)沒(méi)有與它相連的節(jié)點(diǎn)，然后返回上一個(gè)節(jié)點(diǎn)，繼續(xù)訪問(wèn)與它相連的其他節(jié)點(diǎn)，直到圖中所有節(jié)點(diǎn)都被訪問(wèn)到。
還以下圖為例，從“你”開始，與三個(gè)節(jié)點(diǎn)相連，選擇其中一個(gè)小豬Clare，然后訪問(wèn)一個(gè)跟clare相連的節(jié)點(diǎn)Jonny，Jonny沒(méi)有相連節(jié)點(diǎn)，返回到Clare，訪問(wèn)跟Clare相連的還未被訪問(wèn)到的節(jié)點(diǎn)Thom，Thom沒(méi)有相連節(jié)點(diǎn)，返回到Clare，此時(shí)跟Clare相連的節(jié)點(diǎn)已經(jīng)全部被訪問(wèn)過(guò)，放回Clare的上一個(gè)節(jié)點(diǎn)“你”，“你”還有未被訪問(wèn)的相連節(jié)點(diǎn)Bob和Alice，繼續(xù)安照上述過(guò)程進(jìn)行訪問(wèn)。
由上述過(guò)程可知，算法實(shí)現(xiàn)用到了遞歸。
源碼鏈接：https://github.com/Victcode/AlgorithmsLearning/blob/main/AhaAlgorithm/graph_dfs.cpp
