图的知识图的定义图的基本操作图的遍历图的性质图的应用图的定义图是由顶点和边组成有向边又叫弧简单图不存在自己指向自己和重复的边多重图存在对于无向图顶点的度是指该顶点边的条数对于有向图入度为指向该顶点的边数出度为该顶点发散出去的边数简单路径指路径中不重复有向图的路径也是有向的距离两个顶点的最短路径若没有路径则距离为无穷强连通在有向图中顶点1可以到达顶点2顶点2也可以到底顶点1这顶点1和顶点2强连通若任意两个顶点强连通则为强连通图n个顶点的强连通图最少有n条边生成子图是原图去掉一些边极大强连通子图包含尽可能多的顶点和边且为强连通生成树极小连通子图包含原图中全部顶点去掉一些边剩下n-1条边构成连通。在非连通图中连通分量的生成树构成了生成森林带权路径长度路径上所有边的权值和无向完全图任意两顶点都有边有向完全图任意两顶点都有双向弧有向树一个顶点入度为0其余入度为1图的存储(1). 邻接矩阵若a13为1则第一个顶点和第三个顶点有边或者代表第一个顶点指向第三个顶点的边带权图则矩阵元为权值无边为无穷。邻接矩阵的第i行的个数表示第i个节点的出度第i行第i列的个数和表示度(2). 邻接表法类似孩子表示法结构体数组每个顶点包含指向被连接顶点的指针链表如下(3). 十字链表法只能存有向图右指针可以找到所有出边左指针可以找到所有的出边 如下(4). 邻接多重表 邻接表 十字链表只能存无向图图的基本操作和上面第一、二图对应着看判断两个顶点是否存在边adjacent(G, x, y)邻接矩阵只用判断矩阵元邻接表需要依次判断x顶点所有相连的节点是否有y顶点。列出与某顶点邻接的所有顶点neighbors(G,x)邻接矩阵遍历该顶点所在的行或列即可邻接表可直接遍历该顶点的所有边但是有向图中找到入边邻接表需要遍历整个表。插入新顶点insertVertex(G, x)邻接矩阵增加新行和新列邻接表只用在数组中增加一条邻接链。删除顶点deleteVertex(G, x)邻接矩阵将该顶点的行和列标记为布尔0当其他操作时遇到布尔0跳过逻辑删除邻接表不仅删除该顶点的邻接链还要删除其他链上的对应边。添加边addEdge(G, x, y)邻接矩阵改变矩阵元邻接表中使用头插法插入该顶点的邻接链。删除边removeEdge(G, x, y)邻接矩阵改变矩阵元邻接表遍历该顶点邻接链找到对应边并删除。求某顶点的第一个邻接顶点firstNeighbor(G, x)邻接矩阵遍历行或列找到第一个1邻接表直接找该顶点邻接链的下一个指针。求某顶点的下一个邻接顶点nextneighbor(G, x, y)邻接矩阵继续遍历行或列邻接表找y顶点的下一个指针设置某边权值setEdgeValue(G, x, y)与判断是否有边类似。获取某边权值getEdgeValue(G, x, y)与判断是否有边类似。//邻接矩阵存储classMyGraph{public:intvertexCount;intedgeCount;vectorvectorintmatrix();MyGraph():vertexCount(0),edgeCount(0),matrix(vectorint(0,0),0){}~MyGraph(){}};图的遍历BFS广度优先遍历1相对于树的广度优先遍历图需要标记是否走过2对于同一个图邻接矩阵的表示唯一邻接表的表示不唯一遍历顺序不唯一3时间复杂度邻接矩阵O(n2)邻接表O(n)4广度优先生成森林由广度优先遍历的边生成树最终形成的森林voidBFS(MyGraph G,intx){queueintq;intvisitde[10]{0};//假设图有十个顶点visit(x);visited[x]1;q.push(x);while(!q.empty()){inttmpq.front();q.pop();//遍历该顶点的邻接顶点for(intifirstNeighbor(G,tmp);i0;inextNeighbor(G,tmp,i)){if(!visited[i]){visit(i);visited[i]1;q.push(i);}}}}DFS深度优先遍历1同样需要标记是否走过2对于同一个图邻接矩阵的表示唯一邻接表的表示不唯一遍历顺序不唯一3时间复杂度邻接矩阵O(n2)邻接表O(n)递归深度最大为O(n)4深度优先生成森林由深度优先遍历的边生成树最终形成的森林5有向图有时不能一次遍历完整个图需要遍历标记数组找到还没访问的顶点voidDFS(MyGraph G,intx){intvisited[10]{0};visit(x);visited[x]1;//遍历该顶点的邻接顶点for(intifirstNeighbor(G,x);i0;inextNeighbor(G,x,i)){if(!visited[i])DFS(G,i);}}图的性质邻接矩阵An[1][3]表示顶点1到顶点3长度为n的路径的数目BFS构成的生成树高度最低图的应用最小生成树由带权连通无向图形成的生成树边权值和最小。1Prim算法贪心依次将代价最小的新顶点纳入生成树2Kruskal算法每次选择权值最小的边连接两个顶点已经连过的不连最短路径1 BFS外部三个数组一个用来判断是否走过一个用来储存到该顶点的最短路径长度一个用来存储最短路径中该顶点的前一个顶点每次遍历更新数组。2 Dijkstra迪杰斯特拉外部三个数组一个用来判断该点是否找到最短路径初始false一个用来储存到该顶点的最短路径长度初始无穷一个用来存储最短路径中该顶点的前驱顶点。每次将路径长度数组中最小的固定为最优路径更新判断数组之后更新该顶点的附近顶点路径数组和前驱数组然后进行下一次循环直至找到所有顶点的最短路径。3Floyd动态规划思想外部两个二维数组一个邻接表来存最短路径一个用来存两个顶点的中转点当第一个顶点可以作为中转时遍历出最短路径数组当第一个和第二个顶点可以作为中转时遍历出最短路径数组…vectorintdijkstra(vectorvectorintG){//邻接表图intnG.size();//图有n个顶点vectorboolfinalMark(n,false);vectorintdist(n,0xffff);vectorintpath(n,-1);//初始化finalMark[0]true;dist[0]0;for(inti1;in;i)if(G[0][i]0xffff){//0xffff表示不能达到distG[0][i];path0;}for(inti1;in;i){intmn0xffff;intmnIdx0;for(intj1;jn;j)//找出final是false并且最小的distif(finalMark[j]falsedist[j]mn){mndist[j];mnIdxj;}finalMark[mnIdx]true;for(intj1;jn;j)//找以该最小点为中转时附近的点是否最优if(finalMark[j]falseG[mnIdx][j]dist[mnIdx]dist[j]){dist[j]G[mnIdx][j]dist[mnIdx];path[j]mnIdx;}}returndist;}vectorintfloyd(vectorvectorintG){//邻接表图intnG.size();//图有n个顶点vectorvectorintpath(n,vectorint(n,-1));for(intk0;kn;k)for(inti0;in;i)for(intj0;jn;j)if(G[i][j]G[i][k]G[k][j]){G[i][j]G[i][k]G[k][j];path[i][j]k;//G[i][k]也可能是通过其他中转点取得的最短路径从而实现多个中转点时最短}returnG;}DAG有向无环图描述表达式。中缀表达式可以用二叉树表示二叉树中可以剪去重复的子树形成有向无环图最大的减小节点数量。因为DAG表达式的每个叶子节点都不一样所以可以根据中缀表达式自底向上的设计结构看每层是否有能合并的。AOV网以顶点表示活动的DAG有向无环图。拓扑排序按入度排序。不断取出入度为0的顶点并删除出度的边。逆拓扑排序按出度排序DFS后序遍历可实现逆拓扑需要visited数组并且每个顶点都作为DFS起点AOE网以有向边表示活动顶点表示事件的DAG有向无环图。从开始源点到结束汇点的最长路径称为关键路径这条路径上的活动称为关键活动关键路径表示整个过程的最短时间 。时间余量为0的活动路径为关键路径。求时间余量1求所有事件最早发生时间拓扑排序开始为02求所有事件最迟发生时间逆拓扑排序将1的最后时间赋给结束倒推3求所有活动最早发生时间有向边的起始事件对应的最早时间4求所有活动最迟发生时间有向边指向事件的最迟时间减去活动时间5求所有活动的时间余量4-3。