图论常见的方法

最短路径迪杰克斯拉算法Floyd算法SpfaBellman-ford 最小生成树prim算法Kruskal算法 拓扑排序tarjan算法求割点

最短路径

算法之间的区别

迪杰克斯拉算法

int dijkstra(int k) { dis[1]=0; for(int m=2;m<=k;m++) dis[m]=1e9;//初始化dis数组 vis[1]=1; for(int n=1;n<=k;n++) { for(int m=1;m<=k;m++) { int minpath=1e9; if(!vis[m]&&dis[m]<minpath) { minpath=dis[m]; int mark=m; } } vis[mark]=1; for(int m=1;m<=k;m++) { if(!vis[m]&&dis[n]>dis[m]+[m][mark]) dis[n]=dis[m]+[m][mark]; } } }

Floyd算法

for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(e[i][j]>e[i][k]+e[k][j] ) e[i][j]=e[i][k]+e[k][j];

Spfa

ford的队列实现，已死。

Bellman-ford

求最短路径

for（int m=0;m<city;m++) for(int n=0;n<edge;n++) path[m]=min(path[n]+map[n][m],path[m])

求有无环

for(i=1;i<=enum;i++) //检查有无负权环 { if(d[edge[i].v]>dis[e[i].u]+edge[i].w) { flag = false;//存在负环 break; } }

最小生成树

prim算法

Kruskal算法

不形成环的前提下，按照边权重从小到大排序

struct node{ int x,y; int weight; }n[5000]; int parent[k]; int fatherfind(int k) { if(parent[k]==k) return parent[k]; else parent[k]=fatherfind(parent[k]); } int cmp(node a,node b) { return a.weight<b.weight; } sort(n,n+5000,cmp);//会按照weight大小从小到大排序 for（int m=0;m<n;m++) { int x=n[m].x; int y=n[m].y; if(fatherfind(x)!=fatherfind(y)) parent[fatherfind(x)]=y; }

拓扑排序

基本思路是：从入度或（出度）为0的点出发，一层层向上滚动，滚动一层则剔除该点，直到整个图全被遍历为止

int topo(int k) { for(m=1;m<=k;m++) { if(!indegree[m]) q.push(m); } while(!q.empty()) { int k=q.front(); q.pop(); for(int m=1;m<=k;m++) { if(indegree[m]==0) q.push(m); } } }

tarjan算法求割点

root节点，判断是否有两棵子树即可 非root节点，判断其子树与自身有无连接

int low[u]; int dfn[u]; void tarjan(int u,int from) { dfn[u]=low[u]=++idx;//更新时间戳 int child=0; for(int i=head[u];i!=0;i=e[i].next) { int nx=e[i].to; if(!dfn[nx])//如果未访问过 { tarjan(nx,from)//回溯 low[u]=min(low[u],low[nx]);//取最早碰到自己的那个 if(low[nx]>=dfn[u]&&u!=from)//不通过u，无法访问到其,则一定是割点 cut[u]=true; if(u==from) child++; } low[u]=min(low[u],low[nx]); } if(child>=2&&u==from)//root节点 cut[u]=true; }