第二十七天（數據結構：圖）

圖：是一種非線性結構形式化的描述:   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);}}//輸入格式
ABCDEFG ->所有的頂點元素
AB3     ->邊以及權值
BC5
...
##-1退出

//你的圖里面最多可以容納的頂點個數
#define VMaxNum 1000//這個值代表一個無法到達的權值
#define VERYBIG 65535//弄的是鄰接矩陣//你現在需要一個圖的類型
typedef struct 
{char _V[VMaxNum];//頂點元素的數組int _R[VMaxNum][VMaxNum];//頂點與頂點之間的關系集合int _vexnum;//真正頂點的個數int _arcnum;//邊(關系線)的個數  無向的叫邊  有向的叫弧
}Graph;

#include "Graph.h"//建立鄰接矩陣
Graph * GraphInit(void)
{return (Graph *)calloc(1,sizeof(Graph));
}//獲取頂點元素的下標 -1表示失敗
int GetVIndex(Graph * g,char v)
{for(int i = 0;i < g ->_vexnum;i++){if(v == g ->_V[i])return i;}return -1;
}//從鍵盤獲取頂點元素以及邊
void GetGraph(Graph * g)
{if(!g)return;printf("請輸入所有的頂點元素:");scanf("%s",g ->_V);getchar();g ->_vexnum = strlen(g ->_V);//實際頂點個數為這么多//關系集合里面什么玩意兒都沒有 不能是0for(int i = 0;i < g ->_vexnum;i++){for(int j = 0;j < g ->_vexnum;j++){g ->_R[i][j] = VERYBIG;//用VERYBIG將關系集合初始化一遍}}char start,stop;int w;while(1){printf("請輸入邊和權值(AB2):");if(scanf("%c%c%d",&start,&stop,&w) != 3){printf("\t\t輸入有誤，請重新輸入\n");char buf[1024];fgets(buf,1024,stdin);continue;}getchar();//輸入成功在后面會多一個\n 你需要拿走if('#' == start || '#' == stop || -1 == w){break;}//printf("%c  %c  %d\n",start,stop,w);int start_index = GetVIndex(g,start);int stop_index = GetVIndex(g,stop);if(-1 == start_index || -1 == stop_index){printf("\n邊有問題，請重新輸入\n");}//為了避免重復if(g ->_R[start_index][stop_index] == VERYBIG)g ->_arcnum++;g ->_R[start_index][stop_index] = w;//這個東西代表的是start到stop有w遠printf("%d   %d\n",start_index,stop_index);g ->_R[stop_index][start_index] = w;//無向圖就可以多這一步    }
}//打印鄰接矩陣
void PrintGraph(Graph * g)
{if(!g)return;for(int i = 0;i < g ->_vexnum;i++){printf("\t%c",g ->_V[i]);}printf("\n");for(int i = 0;i < g ->_vexnum;i++){printf("%c",g ->_V[i]);for(int j = 0;j < g ->_vexnum;j++){if(g ->_R[i][j] == VERYBIG)printf("\t\\");elseprintf("\t%d",g ->_R[i][j]);}printf("\n");}
}//獲取v的第一個鄰接點 v這一行里面第一個不是VERYBIG的
//失敗返回-1
int GetFirstIndex(Graph * g,int v)
{for(int i = 0;i < g ->_vexnum;i++){if(g ->_R[v][i] != VERYBIG)return i;}return -1;
}
//獲取v的w的下一個鄰接點 v這一行里面w列后面第一個不是VERYBIG的
//失敗返回-1
int GetNextIndex(Graph * g,int v,int w)
{for(int i = w + 1;i < g ->_vexnum;i++){if(g ->_R[v][i] != VERYBIG)return i;}return -1;
}//遍歷的向量
int visit[VMaxNum];//visit[i]表示頂點V[i]是否被訪問 0表示沒有  1表示訪問過了//這里用的v是下標
static void DFS(Graph * g,int v)
{if(!g || visit[v])//已經訪問過就不用訪問了return;printf("%c ",g ->_V[v]);visit[v] = 1;for(int w = GetFirstIndex(g,v);w > -1;w = GetNextIndex(g,v,w)){if(visit[w] == 0){DFS(g,w);}}
}//DFS 深度優先 從v開始進行DFS  v是頂點
void DFS_search(Graph * g,char v)
{//初始化visitmemset(visit,0,g ->_vexnum *sizeof(visit[0]));printf("DFS:");//先弄一個遍v開始的DFSDFS(g,GetVIndex(g,v));printf("\n");//所有再遍歷來一遍for(int i = 0;i < g ->_vexnum;i++){if(visit[i] == 0){DFS(g,i);printf("\n");}}
}//請你實現BFS
static void BFS(Graph * g,int v)
{if(!g || visit[v])//圖不存在或者v被訪問過都無需訪問return;//隊列要存在ArrayQueue * qu = ArrayQueue_init(100);//將頂點入隊ArrayQueue_push(qu,v);visit[v] = 1;while(!ArrayQueue_empty(qu)){v = ArrayQueue_front(qu);printf("%c ",g ->_V[v]);ArrayQueue_pop(qu);//for(int i = GetFirstIndex(g,v);i > -1;i = GetNextIndex(g,v,i))for(int i = 0;i < g ->_vexnum;i++){if(g ->_R[v][i] != VERYBIG){if(visit[i] == 0) //這些鄰接點沒有被訪問你才需要去訪問{visit[i] = 1;ArrayQueue_push(qu,i);}}}      }ArrayQueue_destory(&qu,NULL);
}//BFS 廣度優先 從v開始進行BFS  v是頂點
void BFS_search(Graph * g,char v)
{//初始化visitmemset(visit,0,g ->_vexnum *sizeof(visit[0]));printf("BFS:");//先弄一個遍v開始的BFSBFS(g,GetVIndex(g,v));printf("\n");//所有再遍歷來一遍for(int i = 0;i < g ->_vexnum;i++)//防止孤島{if(visit[i] == 0){BFS(g,i);printf("\n");}  }}