第二十七天（数据结构：图）

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