二十八天（数据结构：图的补充）

图：是一种非线性结构形式化的描述:   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