图算法之个人整理总结

《图算法之个人整理总结》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、陈江勇整理2021-7-15图算法实例1.Dijkstra算法求最短路算法22.求所有点最短路的Dijkstra算法33.欧拉路径44.最大的流85.有向图的强连通分量和2-sat的判定问题106.求图中不含有割点（关结点）的块187.图的奇环的判断,是否为二分图的判断198.二分图的匹配209.prim算法求最小生成树2010.给有有向图最少加边使图中没有桥2111.套汇问题2412.差分系统2413.二分图加权匹配--KM算法3214.floyed算法36第37页陈江勇整理2021-7-151.Dij

2、kstra算法求最短路算法用堆来实现输入输出说明：N,M然后M条边即相应的边的长22125214#include#include#include#includeusingnamespacestd;#defineINFINT_MAX#definemaxn30000structNODE{intv;intweight;};intwt[maxn],heap[maxn*2],r,N,M;//wt[i]保存从开始节点到节点i的最短路，heap的

3、大小不确定boolvisit[maxn];//一般开到节点数目两到三倍。这是因为堆中会有相同的节点，但他们的权重vectorG[maxn];//不一样intcmp(inta,intb){returnwt[a]>wt[b];}intdijkstra(ints,intt){inti,u;for(i=0;i=0){u=heap[0];p

4、op_heap(heap,heap+r,cmp);第37页陈江勇整理2021-7-15r--;if(visit[u]){continue;}visit[u]=1;if(u==t){returnwt[t];}for(i=0;i

5、;push_heap(heap,heap+r,cmp);}}}return-1;}intmain(){NODEtemp;inti,A,B,c;scanf("%d%d",&N,&M);for(i=0;i

6、ints){inti,u,j,min;第37页陈江勇整理2021-7-15memset(visit,0,sizeof(visit));for(i=1;i<=F;i++){if(G[s][i])//存在着边{dist[i]=G[s][i];}else{dist[i]=INT_MAX;}}dist[s]=0;visit[s]=1;for(i=1;i<=F;i++){u=-1;min=INT_MAX;for(j=1;j<=F;j++){if(dist[j]

7、;u=j;}}if(u==-1){break;}visit[u]=1;for(j=1;j<=F;j++){if(G[u][j]&&!visit[j]&&dist[j]>dist[u]+G[u][j]){dist[j]=dist[u]+G[u][j];}}}}1.欧拉路径判断欧拉路径时要注意有向图无图的区别。第37页陈江勇整理2021-7-15以下是链表形式structNODE{intv,id;NODE*next;};voidpath(intu,intid){linkp;intvv,dd;while(adj

8、[u]){p=adj[u];vv=p->v;dd=p->id;adj[u]=p->next;deletep;path(vv,dd);}ans[top++]=id;}注意这边ans是反序存结果。SampleInput26alohaarachniddoggopherrattiger3oakmapleelmSampleOutputaloha.arachnid.dog.gopher.rat.tiger***#include