《NOIP图的基础算法.ppt》由会员分享，可在线阅读，更多相关《NOIP图的基础算法.ppt（76页珍藏版）》请在三一办公上搜索。
1、NOIP 图的常用算法简介,石门中学江涛 2,目 录,图的表示邻接矩阵、邻接链表、图的遍历最小生成树算法 Prim算法、Kruskal算法最短路径算法Dijkstra算法、Bellman_Ford算法及SPFA算法、Floyd算法,目 录,图的表示邻接矩阵、邻接链表、图的遍历最小生成树算法 Prim算法、Kruskal算法最短路径算法Dijkstra算法、Bellman_Ford算法及SPFA算法、Floyd算法,顶点给点编号为连续的整数把顶点存放在数组中边邻接矩阵布尔值(或边权值)-TRUE 有边FALSE 无边空间复杂度O(|V|2),图的表示-邻接矩阵,边邻接链表每一个顶点有一个所有与之
2、相邻的链表每一条边2 个（对无向图）要在两个顶点的链表中都加入空间复杂度O(|E|)对稀疏图这种方式比较好,图的表示-邻接链表,图的邻接链表的Pascal和C+实现 具体参见NOIP基础数据结构ppt,图的表示-C/P语言程序实现,图的深度优先(Depth-First)遍历:邻接链表、C+,图的表示-图的遍历,/图的一般结构 struct graph_node;struct AdjList int id;AdjList*next;int n_nodes,S_index=0;graph_node nodes maxN;int visited maxN;AdjList*adj maxN;,标识项点
3、有没有访问过,每个顶点都有邻接链表,邻接链表的节点数据结构,图的深度优先(Depth-First)遍历:邻接链表、C+,图的表示-图的遍历,置每个点标识为“未访问”,从所有未被访问的点k出发，调用DFS(k),void search()int k;for(k=0;kn_nodes;k+)visitedk=0;for(k=0;kn_nodes;k+)if(!visitedk)DFS(k);,置被访问节点的“时间”-次序,访问k的所有相邻的节点,void DFS(int k)/从k出发搜索 AdjList*j;visitedk=+S_index;for(j=adjk;j!=NULL;j=j-nex
4、t)if(!visitedj-id)DFS(j-id);,图的深度优先(Depth-First)遍历:邻接链表、Pascal,图的表示-图的遍历,/图的一般结构 type graph_node=record end;type AdjList=record id:integer;next:AdjList;end;var n_nodes,S_i:integer;nodes:array1.maxN of graph_node;visited:array1.maxNof integer;adj:array1.maxN of AdjList;,标识项点有没有访问过,每个顶点都有邻接链表,邻接链表的节点数
5、据结构,图的深度优先(Depth-First)遍历:邻接链表、Pascal,图的表示-图的遍历,置每个点标识为“未访问”,从所有未被访问的点k出发，调用DFS(k),procedure search();begin k:integer;for k:=1 to n_nodes do visitedk:=0;for k:=1 to n_nodes do if visitedk0 then DFS(k);end;,置被访问节点的“时间”-次序,访问k的所有相邻的节点,procedure DFS(k:integer);begin/从k出发搜索 var j:AdjList;begin inc(S_i);
6、visitedk:=S_i;j:=adjk;while(jNULL)do begin if visitedj.id0 then DFS(j.id);j:=j.next;end;end;,图的宽度优先(Breadth-First)遍历:邻接链表、C+,图的表示-图的遍历,/图的一般结构 struct graph_node;struct AdjList int id;AdjList*next;int n_nodes,S_index=0;graph_node nodes maxN;int visited maxN;AdjList*adj maxN;,标识项点有没有访问过,每个顶点都有邻接链表,邻接链
7、表的节点数据结构,图的宽度优先(Breadth-First)遍历:邻接链表、C+,图的表示-图的遍历,置每个点标识为“未访问”,从所有未被访问的点k出发，调用BFS(k),void search()int k;for(k=0;kn_nodes;k+)visitedk=0;for(k=0;kn_nodes;k+)if(!visitedk)BFS(k);,图的宽度优先(Breadth-First)遍历:邻接链表、C+,图的表示-图的遍历,int q maxN;void BFS(int k)int front,back;q0=k;front=back=0;for(;fronnext)if(!visi
8、tedj-id)q+back=j-id;visitedj-id=+S_index;,BFS用的队列，一般全局,Front=back,队列不空,访问k的所有相邻的节点,图的宽度优先(Breadth-First)遍历实例示意:,图的表示-图的遍历,目 录,图的表示邻接矩阵、邻接链表、图的遍历最小生成树算法 Prim算法、Kruskal算法最短路径算法Dijkstra算法、Bellman_Ford算法及SPFA算法、Floyd算法,图的遍历:邻接链表时间复杂度分析每一个顶点访问一次每条边访问两次无向图每条边出现在两个链表中O(|V|+|E|)O(|V|2)对 稠密图|E|V|2 O(|V|)对 稀疏
9、图|E|V|对稀疏图邻接链表的效果非常好！,图的表示-图的遍历,生成树：一个|V|个点的图，取其中|V|-1条边，并连接所有的顶点，则组成原图的一个生成树。属性：|v|-1条边、连通、无环。最小生成树：加权图的最小生成树是一棵生成树，其所有边的权值之和不会大于其它任何生成树。简单讲：找出连接所有点的最低成本路线,最小生成树(MST)-定义,红边连接了所有顶点,所以构成一棵生成树权和=1+2+4+4+7+8+9,局域网(net)RQNOJ 某局域网内有n(n=100)台计算机，由于建网时工作人员的疏忽，现在网内存在回路，造成网络卡的现象。我们用f(i,j)表示i,j之间连接的畅通程度(f(i,j
10、)=1000)，f(i,j)值越小表示i,j之间连接越通畅，f(i,j)为0表示i,j之间无网线连接。现在我们需要除去一些连线，使得网络中没有回路，并且被除去网线的f(i,j)最大，请求出这个最大值。,最小生成树(MST)-实例一,环属性：一棵生成树上，增加一条边e，再删除e所在环上的最大边，会得到另一棵“更好”的生成树(如果e不是最大边),最小生成树(MST)-算法原理,9,4,剪切属性：在图中，剪切将顶点划分成两个不相交集合。交叉边为地些顶点在两个不同集合的边。对于任何一个剪切，各条最小的交叉边都属于某个MST，且每个MST中都包含一条最小交叉边。,最小生成树(MST)-算法原理,7,4,
11、9,最小边原则：图中权值最小的边(如果唯一的话)一定在最小生成树上。唯一性：一棵生成树上，如果各边的权都不相同，则最小生成树是唯一的。反之不然。思考：怎样图G判断只有一个MST？,最小生成树(MST)-算法原理,算法描述1：MST_Prim(G,r)(1)将G剪切成两个集合A、B，A中只有一个点r(2)取最小权的交叉边(x,y)，xB,yB(3)将y加入A(4)如果已经加了n-1条边，结束。否则，转(3)算法证明：根据剪切属性 图(?),最小生成树(MST)-Prim算法,算法要点：每次求最小权交叉边时，如果都重新计算，则显然要枚举(x,y)-xA,yB。O(n2)时间复杂度。其实每次A中只是
12、增加一个新顶点v，最多有交叉边(v,y)，修改量只有与v有边的顶点，为O(n)。只需记录下B中的每个元素y与A所有元素中最小权边，则求最小值最多为O(n)-有时可以用“堆”优化。,最小生成树(MST)-Prim算法,算法描述2：MST_Prim(G,r)/从任意点r出发，生长成一MST for i=1 to n do disi/初始化每点到A集合的最小值 inAi false/设顶点不在A中disr 0/将r设为0（或-），准备取出for i=1 to n do v get-min()/取dis?中最小的值c和顶点v,inA v true/v放入A中 sum sum+c/c加入MST的总和中
13、updata(v)/枚举交叉边(v,B),改进dis,最小生成树(MST)-Prim算法,算法描述3：MST_Kruskal(G)(1)将G所有条边按权从小到大排序；图mst开始为空(2)从小到大次序取边(x,y)(3)若加入边(x,y)，mst就有环，则放弃此边，转(2)(4)将边(x,y)加入mst，如果已经加了n-1条边，结束。否则，转(2)算法证明：根据剪切属性 图(?),最小生成树(MST)-Kruskal算法,算法要点：Kruskal算法的最难点在于怎样判断加入边(x,y)后是否形成了环。问题可化为：判断边(x,y)的两个顶点x,y在图（实际是森林）mst中最否已经连通。如果已经连
14、通，加入边将形成环；否则，不形成环。并查集：连通点集之类问题，有高效算法-并查集。,最小生成树(MST)-Kruskal算法,并查集：并查集详细内容可参见有关文章。下面是Pascal段：/初始化，使每个集合只一个元素。for i:=1 to n do f i:=i;/查找x所在类的“根”-代表，并压缩路径function find_set(x:longint):longint;begin if fxx then fx:=find_set(fx);exit(fx);end;/合并两个集合。x,y为两集合的“根”procedure union(x,y:longint);begin fx:=y;en
15、d;,最小生成树(MST)-Kruskal算法,并查集：并查集详细内容可参见有关文章。下面是C+片段：/初始化，使每个集合只一个元素。for(i=1;i=n;i+)f i=i;/查找x所在类的“根”-代表，并压缩路径int find_set(int x)if(fx!=x)fx=find_set(fx);return(fx);/合并两个集合。x,y为两集合的“根”void union(int x,y)fx=y;,最小生成树(MST)-Kruskal算法,算法描述4：MST_Kruskal(G)for i=1 to n do fi i;/初始化并查集 sort(e,e+m);/边按大小排序c 0;
16、/取边的计数器for i=1 to m do/从小到大取边 v find_set(ei.v);/左端点所在连通块“根”u find_set(ei.u);/右端点所在连通块“根”if(v!=u)/如果不在同一连通块 union(v,u);/合并两连通块 sum+=gvu;/加入这条边的权 if(+c=n-1)break;/if 取了n-1条边，结束,最小生成树(MST)-Kruskal算法,时间复杂度分析Prim算法普通的方法 O(|V|2)Prim算法中用“堆”方法 O(|E|+|V|)*log|V|)-对稀疏图较好Kruskal算法 O(|E|*log|E|+|N|*A(|V|)-对稀疏图较
17、好,最小生成树(MST)-时间复杂度,1、平面上有N(=3000)个点，求连通它们的最小生成树，用什么算法比较好？2、要判断一条边是否可以在一棵MST上，怎样做比较好？3、平面上有K个水源（井），N个居民供水点，怎样用最少的管道使这N个居民点都能用连接到水源。注：边只能水源、居民点之间直接相连。,最小生成树(MST)-思考题,maintain 有一个无向图，有N个点，有w条边。但是一开始，所有的边都是被破坏了的，即不可用。接下来每一天可以修复一条边。注意：两个点之间可能有多条边。现在的问题是：每一天修复完一条边后，无向图中的任意两个结点都可以连通了吗？如果还不可以输出-1，如果可以了，你从已经
18、修复的边中，选择一些边，使得这些边的总长度最小，输出最小值。,最小生成树(MST)-实例二,输入格式：第一行:两个整数：N，W。N(1=N=200)、W(1=W=6000).第2.W+1行:三个整数x,y,d.表示该天修复的边，该边是从结点x到结点y,长度是d.输出格式：每读入一条边，如果还不可以输出-1;如果可以了，你从已经修复的边中，选择一些边，使得这些边的总长度最小，输出最小值。,最小生成树(MST)-实例二,样例输入：4 61 2 101 3 83 2 31 4 31 3 62 1 2,最小生成树(MST)-实例二,样例输出：-1(4号点无法连接到其他点)-1(4号点无法连接到其他点)
19、-1(4号点无法连接到其他点)14(修2,3,4三边)12(修3,4,5三边)8(修3,4,6三边),2,1,4,3,10,8,3,3,分析：每读入一条边，做一次MST。最好：M*N*N=24,000,000 超1s动态维护树1、构成第一棵MST 2、读入边e(a,b,c)，BFS找 e.a,e.b 所在路径，取其中边最大的x,如果 x.c e.c，删除边x,加入边e.M*N 1,200,000简化算法？由于每次只保留N-1条边，每次重新做Kruskal算法：M*N*logN 9,600,000 大致可行。更可省略排序，用插入法即可：M*N*3 3,600,000,最小生成树(MST)-实例二
20、,目 录,图的表示邻接矩阵、邻接链表、图的遍历最小生成树算法 Prim算法、Kruskal算法最短路径算法Dijkstra算法、Bellman_Ford算法及SPFA算法、Floyd算法,最短路径：对在权图G=(V,E),从一个源点s到汇点t有很多路径，其中路径上权和最少的路径，称从s到t的最短路径。简单讲：找出连接两个给定点的最低成本路径单源最短路径问题：求从源点s到其它所有点的最短路径问题。令人惊讶的是，“单源单汇”与“单源多汇”两个问题的算法复杂度是一样的，有向、无向图也一样。统称单源最短路径问题。,最短路径(ShortestPath)-定义,三角形性质 设源点s到点x、y的最短路径长度
21、为disx、disy。x与y之间的距离是lenxy，则有下面的“三角形定理”：disx+lenxy=disy 松驰 若在处理过程中，有两点x、y出现不符合“三角形定理”，则可改进一下松驰：if(disx+lenxy disy)disy=disx+lenxy;,最短路径(ShortestPath)-属性,X,Y,S,如果边没有负权的，我们可以用类似Prim算法的贪心算法Dijkstra算法。算法描述1：SP_Dijkstra(G,s)(1)将G中顶点分成两个集合A、B，A集合中由已经求出最短路径的顶点组成，B集合是其它顶点。开始时A中只有一个点s(2)从B集合中取一个当前最短的顶点v(3)把v加
22、入A集合，并对v相连的顶点试做“松驰”(4)如果|A|=|V|，结束。否则转(2),最短路径-Dijkstra算法,算法描述图示：边权=0,如果disv disx，则x永远不会松驰v，故v点确定下来。,最短路径-Dijkstra算法,S,X,V,disv,disx,A集合,B集合,第一步，初始化,所有顶点距离置,源点置 0,最短路径-Dijkstra算法,第二步，取出S，松驰相邻点,松驰S的相邻顶点,最短路径-Dijkstra算法,源点,红箭头表示方案前趋点,S放入A集合,取最近的顶点x,最短路径-Dijkstra算法,第三步,由对u松驰,由x对y松驰,最短路径-Dijkstra算法,第四步,
23、A=s,x,选B中最近的点y,最短路径-Dijkstra算法,第五步,A=s,x,y,选B中最近点 u,最短路径-Dijkstra算法,第六步,A=s,x,y,u,最后选择 v,最短路径-Dijkstra算法,第七步,A=s,x,y,u,红色箭头记录的是最短路径的前趋点。,最短路径-Dijkstra算法,第八步,算法描述2：SP_Dijkstra(G,s)/求单源s到其它点的最短距离 for i=1 to n do disi/初始化每点到s距离 inAi false/设顶点不在A中diss 0/将diss设为0，准备取出for i=1 to n do v get-min()/取dis?中最小的
24、值c和顶点v,inA v true/v放入A中 sum sum+c/c加入MST的总和中 updata(v)/检查(v,B),松驰dis?,最短路径-Dijkstra算法,与prim不相同点,cooking Bessie喜欢为在外面的奶牛做晚餐，Bessie按响铃给他们一个信号叫他们进来就可以了。晚餐将在T(1=T=1,000,000)毫秒完成，而且Bessie强调那些想吃她晚餐的奶牛必须准时到。这些牛在F(1=F=500)各不同的草地标号为1F用P(1=P=10,000)个双向的小路连接。Bessie在第1个草地，给出一头牛走每一条小路所用的时间，问多少个草地上的奶牛可以在T毫秒内到Bess
25、ie 所在的草地，假设多头牛可以共享一条路。,最短路径-实例一,如果边有负权的话，Dijkstra算法是错误的。这里需要不断迭代地做“松驰”，直到无“松驰”为止。算法描述3：SP_Bellman(G,s)(1)初始化每点到s点的最短距离为(2)取所有边(x,y)，看x能否对y松驰。(3)如果没有任何松驰，则结束break。(4)如果松驰次数N，转(2)(5)否则，图中有“负圈”。,最短路径-Bellman-ford算法,算法说明：Bellman-ford算法N次迭代就可以判断图中是否有“负环”。取所有边有两种方法：(1)扫描每一点的邻接链表(2)用有序点对(x,y)记录边时，可直接取边。但要请
26、注意对无向图，要注意(y,x)也要松驰。对于求s到某点t的最短距离，可能因为其它地方有“负环”而出现问题，要预处理。,最短路径-Bellman-ford算法,算法描述4：SP_Bellman(G,s)/求单源s到其它点的最短距离 for i=1 to n do disi/初始化每点到s距离diss 0/将diss设为0for i=1 to n do/最多迭代n rel=false;/是否有松驰标志 for 每条边(x,y)/取图的每一条边 if(disx+lenxydisy)/不满足三角形性质 disy=disx+lenxy;/松驰disy rel=true;if rel=false retu
27、rn 0;/没有一次松驰，则结束return-1;/迭代了n次，有负圈,最短路径-Bellman-ford算法,虫洞(Wormholes)在一个神秘岛上，有N(1=N=500)个洞口，标号1.N，它们之间有M(1=M=2500)条通道相连。神秘的是另外还有W(1=W=200)条传说中的时间虫洞-当到达通道的另一端洞口时，竟然可以比进入的时间要早！你当然想进行这样的时间之旅，希望从一个洞口s出发，经过几个通道，在比出发早些时候的时间回到洞口s。也许还能碰到自己,hehe 根据给定的地图，请判断能否实现这样的愿望。,最短路径-实例二,输入格式：第一行：一个整数 F(1=F=5)，表示共有F组数据。
28、（多组数据测试）每组数据：第1行：三个整数 N M W 第2至M+1行:每行三个整数(S,E,T),表示在S与E洞口之间有一个双向通道，通过需要T(0=T=10,000)秒。第M+2至M+W+1行:每行三个整数(S,E,T),表示在S与E洞口之间有一个单向通道，从S到E可以回到之前T(0=T=10,000)秒。输出格式：共1.F行，每行对应一组数据，如果可以实现愿望输出YES,否则输出NO.,最短路径-实例二,输入样例(wormhole.in):23 3 11 2 21 3 42 3 13 1 33 2 11 2 32 3 43 1 8,最短路径-实例二,输出样例(wormhole.out):
29、NOYES,1,2,3,3,图2,4,8,1,2,3,2,4,1,3,图1,分析 首先，把无向边改成两个有向边，这样整个问题成在有向图中求负环问题。N*(M+W)=500*（2500+200）2,000,000 显然，用Bellman算法不超时。本题要注意的是，两点之间可能有多条边，不能用邻接矩阵记录。参考程序参考程序_虫洞.doc,最短路径-实例二,对迭代的改进：SPFA算法 Bellman-ford算法中，每次都要检查所有的边。这个看起来比较浪费，对于边(x,y)，如果上一次disx没有改变，则本次的检查显然是多余的。我们每次只要从上次刚被“松驰”过的点x，来看看x能不能松驰其它点即可。S
30、PFA算法中用BFS中的队列来存放刚被“松驰”过的点。由于顶点个数为|V|，队列如果用数组的话显然要用“循环队列”使用空间。,最短路径-SPFA算法,算法描述5：SP_SPFA(G,s)/求单源s到其它点的最短距离 for i=1 to n do disi;visi false;/初始化每点到s距离,不在队列diss 0;/将diss设为0viss true;count 1;/s放入队列head 0;tail 0;q0=s;/队列头尾指针while(count0)do v qhead;/队头节点v for 每条边(v,i)/与v相连的每一条边 if(disv+lenvidisi)/不满足三角形
31、性质 disi disv+lenvi;/松驰disi if(visi=false)/不在队列，则加入队列 visi true;count+1;tail+1;qtail=i;visv false;head+1;count-1;/v出队列,最短路径-SPFA算法,SPFA算法的思考 对有向图，s到t的最短路问题仍然有负环影响。无向图呢？怎样判断图上负环？,最短路径-SPFA算法,求每对节点之间最短距离问题：例如，求一个图的直径，即所有最短路径中最长的。如果多次调用单源最短路径算法，效果并不好。特别是对有负边的图。如果无负环，则有简单的Floyd-warshell算法。这是动态规划算法。,最短路径-
32、Floyd算法,动态规划算法定义d i,j,k 为路径中间只允许经过节点1k的情况下i到j的最短路距离它有两种情况最短路经过点k，di,j,k=di,k,k-1+dk,j,k-1最短路不经过点k，di,j,k=di,j,k-1 综合起来，状态转移方程为 di,j,k=min di,k,k-1+dk,j,k-1,di,j,k-1 边界条件 di,j,0=lenij（不存在的边权可为）,最短路径-Floyd算法,算法描述6：SP_Floyd(G)/求每对节点的最短距离 for i=1 to n do for j=1 to n do disi,j lenij;/初始化边界条件for k=1 to n
33、 do/K放在最外层，数组少一维 for i=1 to n do for j=1 to n do if(disi,k+diskjdisi,j)/状态转移 disi,j disik+diskj;,最短路径-Floyd算法,Floyd算法的思考Floyd算法怎样记录下最短路径？Floyd算法怎样判断负环？求图中的最小环问题。,最短路径-Floyd算法,Dijkstra单源 非负 O(|V|2)对稠密图好可用“堆”优化 O(|E|*log|V|)对稀疏图较好Bellman-Ford单源 无负环 O(|V|*|E|)可先用Dijkstra预处理优化SPFA用更新队列优化,时间复杂度平均好，但不确定。F
34、loyd全源 无负环 O(|V|2)思考：有多源问题类吗？如果边权只有0,1(或0,1,2,3,4)，能否优化算法？,最短路径-算法比较,最短路径-实例三,butter 农夫John发现做出全威斯康辛州最甜的黄油的方法：糖。把糖放在一片牧场上，他知道N只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。农夫John可以训练这些奶牛，让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声，以至他可以在晚上挤奶。农夫John知道每只奶牛都在各自喜欢的牧场（一个牧场不一定只有一头牛）。给出各头牛所在的牧场和牧场间的路线，找出使所有牛到达的路程和最短的牧场（他将把糖放在那）,最短路径-
35、实例三,输入格式 第一行:三个数，奶牛数N（1=N=500）,牧场数P（2=P=800），牧场间道路数C(1=C=1450)第二行到第N+1行:1 到 N 头奶牛所在的牧场号 第N+2行到第N+C+1行：每行有三个数,相连的牧场A、B，两牧场间距离D（1=D=255），当然,连接是双向的.输出格式 一行:输出奶牛必须行走的最小的距离和,最短路径-实例三,输入样例3 4 52341 2 11 3 52 3 72 4 33 4 5输出样例8 说明：放在4号牧场最优,样例图形 P2 P1-1-C1|5 7 3|C3 C2-5-P3 P4,最短路径-实例三,分析 若用Floyd算法预处理，显然P3=8
36、0035*108要超时。边比较少，可枚举每一点为源，再用Dijkstra算法+堆优化来处理:P*C*logP=800*1450*log8001.2*107 不超时 参考程序见附件参考程序101.doc 用SPFA算法平均来说效果最好，试用一下。参考程序见附件参考程序102.doc,最短路径-实例三,总结堆优化的Dijkstra不能处理负边的情况，而SPFA则可以堆优化的Dijkstra时间复杂度稳定，而SPFA的时间复杂度不稳定。SPFA的实现比堆优化的Dijkstra简单，平均速度也较快。实际运用中，我们一般根据题目的各种条件来选择这2种算法中的一种。,图遍历拓展问题有向无环图的拓扑排序连通
37、块有向图的强连通分量关键节点、桥欧拉路（一笔画）问题工程图的关键路径差分约束系统,图-图的补充基础算法,图的遍历:欧拉路问题结论1：无向图存在欧拉回路的充要条件是：图是连通的。图中所有点的度均为偶数。结论2：无向图欧拉路存在的充要条件：图是连通的。图中有且仅有2个度数为奇数的点，并且这两个点一定是这条欧拉路的起点和终点。,图-图的补充基础算法,图的遍历:欧拉路问题结论3：有向图G，存在欧拉回路的充要条件是：基图（原有向边改为无向边后所得的无向图）连通所有点的出度和入度相同结论4：有向图G，存在欧拉路的充要条件是：基图连通有且仅有一个点入度比出度大1，且这个点是欧拉路的终点有且仅有一个点入度比出
38、度小1，且这个点是欧拉路的起点其他所有的点入度和出度相等,图-图的补充基础算法,图的遍历:一笔画问题程序下面是用邻接矩阵写的程序。用邻接链表的程序 或 两点之间有多条边的程序 要适当修改取边与删边处理。void DFS(int v)/递归写法visitedv=true;for(int i=0;in;i+)if(gvi)gvi=giv=false;DFS(i);ans ansI+=v;,图-图的补充基础算法,图的遍历:一笔画问题程序void trave(int v)/非递归写法int i;visitedv=true;que 0=v;while(queI=0)v=que queI;if(get_next(v,i)/取v的相邻边(v,i)gvi=giv=0;visitedi=true;que+queI=i;/访问点进栈 else ans ansI+=que queI-;/出栈，放入答案队列,图-图的补充基础算法,updata,剪切原理等图加两个圈程序用不同的底色分段Mst的图示,
