二十八天（數據結構：圖的補充）

圖：是一種非線性結構形式化的描述:   G={V,R}V:圖中各個頂點元素(如果這個圖代表的是地圖，這個頂點就是各個點的地址)R:關系集合，圖中頂點與頂點之間的關系(如果是地圖，這個關系集合可能就代表的是各個地點之間的距離)在頂點與頂點之間的關系上面加上一個權值(w),這種權值代表的意義可能會不一樣如果沒有權值，頂點與頂點之間可能只有是否能到達的情況，但是不知道到達它需要的"距離"圖是一個二元組：描述V(頂點的代號，我們需要一個"數組") 描述R(可能是兩點之間的距離，我們也需要一個"數組"去描述)圖分為兩種1 有向圖:關系是有方向的(你可以想象是一個單行道)有去不一定有來在畫圖的時候，關系是有箭頭指向的2 無向圖:關系是沒有方向的(你可以想象是小區的小道，你過去是走這一條，回來的時候也是走的這一條)有去一定有來在畫圖的時候，關系是沒有箭頭指向的網：帶權值的圖我們就叫網頂點的度：有出度也有入度如果圖是有向圖，這個頂點有出度不一定有入度，有入度不一定有出度如果圖是無向圖，這個頂點有出度一定有入度一般圖里面算度的數量的時候分別都要算入度和出度的數量出度：拓撲  --> 找一個沒有入度的頂點出發通過出度到達另外一個頂點，然后將這個點的入度全部刪除然后從下一個點繼續開始，如果最后能將圖里面的所有的頂點都遍歷一遍那個這個圖就叫拓撲有序，否則就叫拓撲無序入度：逆拓撲 -> 跟上面的是反的圖：里面主要要搞定一個叫路徑的問題1 最短路徑 --- 最短的那一條2 關鍵路徑 --- 在覆蓋所有的工作流程里面找最短的那些路徑這些路徑里面最長的那條路徑就叫關鍵路徑計算機里面描述圖圖是一個二元組，因此需要用至少兩個東西分別描述頂點元素集合，關系集合假設你的頂點是ABCDEFG -> 我們開一個char[]就可以描述了假設你的頂點是"長沙" "武漢"... -> char *[]描述假設你的關系集合為距離 -> int [][]我們有幾種方式去做圖的保存"數組表示法" -> 鄰接矩陣"鏈表表示法" -> 鄰接表(逆鄰接表) 十字鏈表 鄰接多重表鄰接矩陣：通過頂點元素數組和關系集合數組來描述通過畫圖可以看出，鄰接矩陣適合稠密圖鄰接表：通過頂點元素數組和關系鏈表來描述(有向圖無向圖都能做)十字鏈表：主要搞定有向圖(可以快速反應這個點的入度與出度)鄰接多重表:主要搞定無向圖(有去必有來，因此可以少建立很多的關系)通過畫圖可以看出，鏈表表示法適合稀松圖圖的遍歷1 深度優先DFS:樹里面的先序遍歷的擴展圖里面的任何一個頂點都可能是出發點從出發點開始，將其遍歷，然后以深度優先的方式繼續遍歷它的鄰接點(和它有直接關系的點在畫圖的時候有一根線和它連起來了，這個點就是它的鄰接點)鄰接點遍歷完畢繼續以深度優先遍歷它的鄰接點的鄰接點這個點有去也有可能有來，遍歷的時候就可能會遇到剛剛遍歷過點因此我們需要一個輔助向量來表明這個頂點是不是已經被遍歷過了char V[10];visit[10] -> visit[0]表示V[0]是不是已經被訪問 visit[1]表示V[1]是不是已經被訪問.....0沒有被遍歷，1表示遍歷過了if(visit[i] == 0){              訪問V[i]visit[i] = 1；//標記已經被訪問過DFS(V[i]的鄰接點) //以相同的規則去訪問這個鄰接點}訪問w;for(v = 從w第一個鄰接點開始;v鄰接點存在;v = w下一個鄰接點){if(visit[v] == 0){//訪問vvisit[v] == 1;DFS(v);}}2 廣度優先BFS:樹里面的層次遍歷的擴展利用隊列來進行每一層每一層的遍歷入隊訪問出隊訪問都可以從起點開始，將它入隊出隊，轉向它的下一輩(它所有的鄰接點(前面有可能已經被訪問過，訪問過的要排除))為了確保孤島也能被訪問，我們需要將每一個點都要以BFS的形式走一遍BFS(v){//將頂點入隊queue_push(v);while(隊列不為空){v = queue_front();queue_pop();for(i = v的所有鄰接點){if(visit[i] == 0) //這些鄰接點沒有被訪問你才需要去訪問{visit[i] = 1;queue_push(i);}}}}for(i < 頂點個數個數)//防止有孤島  所以每一個點都要試一次BFS{if(visit[i] == 0){BFS(i);}}圖里面最需要搞定的一件事情就是最短路徑有兩種經典的算法來解決這個問題1 弗洛伊德算法 ---- 將所有的可能都列舉出來，從中找出最優的那種可能這個算法效率有點低，但是夠簡單，核心思路就是我從A -> B在我遍歷的過程中發現，通過C點能優化A -> B的距離那么你的C點就是更好的途經點當我們將所有的C點都弄到手，最后留下來的那個C點就是最優解由于要遍歷所有的C點，因此效率較低如果比喻為吃飯，我把所有的東西都吃了，最后肯定飽2 迪杰斯特拉算法 ---- 貪心算法，像吃飯，我一邊吃一邊觀察我是不是飽了，我發現某一個時候我吃飽了，那么我就不需要再吃了我每次都吃那個最喜歡吃的，一直吃到飽為止，它可以過濾掉很多不必須要的可能A -> B，每次我都找更優的那個解，每次都是在待找的里面找最優的當我最后到達B的時候找到的這個更優解就變成了最優解它的核心思路就是每次都在待找序列里面找最優的，一直找下去，找到終點就結束了你得到的這個到終點的路徑一定是最優的去實現迪杰斯特拉算法的時候我們需要三個向量1 到某一個頂點的最優路徑有沒有求出來我們可以自己定義一個標識，一般是0表示沒有求出，1表示求出來了int s[n];n:頂點的個數  與頂點的下標一一對應s[0] == 0 -> V[0]還沒有求出來最短路徑s[0] == 1 -> V[0]求出來最短路徑如果你想要得到到v頂點的最優解，s[v] == 1初始化：只有起點到起點的最短路徑已經求出來了，其它的都還沒有求出來2 這個向量是表示到此頂點它的路徑有多長int d[n];n:頂點的個數  與頂點的下標一一對應d[0]里面的值代表的是起點(已知的起點)到我V[0]終點所需要的路徑的大小d[v]里面的值代表的是起點到我V[v]終點所需要的路徑的大小初始化：起點到這個頂點的直接距離假設起點是v0  終點為是v1d[v1] = R[v0][v1]3 這個向量是表示起到到各個頂點之間的路徑 --- 表示起點 -> 中間 -> 終點這一段路徑char p[][];每一行代表的是起點到我這個頂點走的路徑char p[0] : 起點到V[0]所要走過的路char p[v] : 起點到V[v]所要走過的路初始化：只有起點假設起點是v0  終點為是v1p[v1][0] = V[v0]    步驟：1 在沒有求出最短路徑的各個頂點里面找最小值,找到的這個最小值一定是起點到這個終點的最短路徑值s[n] == 0的時候的d[n]的最小值 -> 它的最小值為min  下標為minindex2 標記第1步找出來的那個最小值下標的s為1補齊到達點s[minindex] = 1 -> 說明 起點 到V[minindex]的最短路徑已經求出來了3 minindex去更新沒有求出最短路徑里面的路徑值如果發現通過minindex能夠縮短d[n],那么我就找出一個更優的解那么我就要把你更新循環著三步就會得到最優解保存路徑我們還有更簡單的方式 --- 保存它的前驅就可以了前驅有前驅....因此遞歸到起點就出全部的路徑


//需要三個向量
int Dijk_s[VMaxNum];//標記是不是求出最短路徑
int Dijk_d[VMaxNum];//最短路徑值
char Dijk_p[VMaxNum][VMaxNum];//路徑int qianqu[VMaxNum];//保存前驅節點//v0->w通過前驅給構建出來
void Printqianqu(Graph * g,int v0,int w)
{if(w == v0){printf("%c ",g ->_V[v0]);//打印起點return;}//先以相同的方式找它的前驅再打印Printqianqu(g,v0,qianqu[w]);printf("%c ",g ->_V[w]);
}//這個是我v0到各個頂點的最短路徑 如果你想要到某一個終點就傳進來，到這個終點就可以停下來了
static void Dijkstra_shixian(Graph * g,int v0)
{if(!g || v0 < 0 || v0 > g ->_vexnum)return;//初始化所有的向量for(int i = 0;i < g ->_vexnum;i++){Dijk_s[i] = (i == v0 ? 1 : 0);//除了起點其它的都是沒有求出來的Dijk_d[i] = g ->_R[v0][i];//初始化都是起點到這個點的直接距離Dijk_p[i][0] = g ->_V[v0];//初始化的時候只有起點}for(int n = 1;n < g ->_vexnum;n++)//弄n - 1次  所有的都會出來{//1 在沒有求出最短路徑的各個頂點里面找最小值,找到的這個最小值一定是起點到這個終點//的最短路徑值     int min_d = VERYBIG;//保存最小值int minindex = -1;//保存最小值的下標for(int i = 0;i < g ->_vexnum;i++){//s[n] == 0的時候的d[n]的最小值 -> 它的最小值為min  下標為minindexif(Dijk_s[i] == 0){if(min_d > Dijk_d[i])//找到一個更小的{min_d =  Dijk_d[i];                   minindex = i;}}}//2 標記第1步找出來的那個最小值下標的s為1Dijk_s[minindex] = 1;//補齊到達點Dijk_p[minindex][strlen(Dijk_p[minindex]) + 1] = 0;Dijk_p[minindex][strlen(Dijk_p[minindex])] = g ->_V[minindex];//char buf[3] = {0};//buf[0] = g ->_V[minindex];//strcat(Dijk_p[minindex],buf);//s[minindex] = 1 -> 說明 起點 到V[minindex]的最短路徑已經求出來了//3 minindex去更新沒有求出最短路徑里面的路徑值//如果發現通過minindex能夠縮短d[n],那么我就找出一個更優的解//那么我就要把你更新for(int i = 0;i < g ->_vexnum;i++){if(Dijk_s[i] == 0){if(Dijk_d[i] > min_d + g ->_R[minindex][i]){Dijk_d[i] = min_d + g ->_R[minindex][i];//更新更優的               strcpy(Dijk_p[i],Dijk_p[minindex]);//拷貝路徑qianqu[i] = minindex;//更新i的前驅節點}}}}//打印最短路徑值與路徑for(int i = 0;i < g ->_vexnum;i++){printf("%s : %d\n",Dijk_p[i],Dijk_d[i]);}//通過前驅打印出路徑for(int i = 0;i < g ->_vexnum;i++){printf("前驅:");Printqianqu(g,v0,i);printf("\n");}}void Dijkstra(Graph * g,char v0)
{Dijkstra_shixian(g,GetVIndex(g,v0));
}//弗洛伊德算法求最短路徑  可以在負權里面使用   迪杰斯特拉算法不能有負權
void Floyd(Graph * g)//由于一直要更新他們的關系  因此我們需要做一個備份
{int R[VMaxNum][VMaxNum];memcpy(R,g ->_R,sizeof(R));//如果從i到j能通過k更優，那么我就更新你，找到所有的k  剩下的就是最優//i -> j  R[i][j]for(int k = 0;k < g ->_vexnum;k++)//中間點{for(int i = 0;i < g ->_vexnum;i++)//起點{for(int j = 0;j < g ->_vexnum;j++)//終點{if(i == j)//自己到自己continue;if(R[i][j] > R[i][k] + R[k][j]){R[i][j] = R[i][k] + R[k][j];}}       }}for(int i = 0;i < g ->_vexnum;i++){for(int j = 0;j < g ->_vexnum;j++){if(R[i][j] == VERYBIG)printf("\\ ");elseprintf("%d ",R[i][j]);}printf("\n");}}

連通圖：無向圖：任意的兩點都是可以連通的(能到達，不一定得直連)，這種圖我們就叫連通圖有向圖: 強連通圖:任意的兩點都是可以連通的，你能到我，我也可以到你弱連通圖:任意的兩點(誰是起點都可以)都是可以連通的，我能到你就可以了連通分量：在一個圖里面，極大連通子圖為它的連通分量連通圖的連通分量只有一個--就是它自己一個圖最多有 頂點個數 個連通分量相鄰矩陣：描述一個點到另外一個點有多少情況能到的可能見圖//輸入格式
ABCDEFG ->所有的頂點元素
AB3     ->邊以及權值
BC5
...
##-1退出eg:
ABCDEFGHIJKLMN
AB12
AC16
AD7
AE21
BF5
CF6
CG3
DG5
EI15
EM11
FH4
GH9
GI27
HJ24
HL9
IL10
IK23
IM6
IN5
JL14
JK8
KN16
MN12
##-1