[关闭]
@myecho 2017-03-19T10:22:36.000000Z 字数 3854 阅读 674

图论模板

图论

1.队列实现的最短路算法,参考算法竞赛入门手册

  1. #include <utility>
  2. #include <functional>
  3. typedef pair<int, int> pii;
  4. priority_queue<pii, vector<pii>, greater<pii> >q; //默认是less的
  5. //这里使用了greater是因为pair类型有自己的排序规则，先比较第一维，相等时比较第二维，因此需要push(make_pair(d[i], i)) 另外还需要给出container的类型，当自定义排序规则的时候
  6. 当然也可以自定义排序规则
  7. struct cmp {
  8.   bool operator () (const pair<int,int> i, const pair<int,int> j) {
  9.     return i.first < j.first;
  10.   }
  11. };
  12. 取出pair节点时需要判断节点是否被解决掉了,此时可利用u.first!=d[x]优化掉visited数组。
  13. bool done[MAXN];
  14. for (int i =0; i < n; i++) d[i] = (i == 0 ? 0 : INF);
  15. memset(done, 0, sizeof(done));
  16. q.push(make_pair(d[0], 0));
  17. while (!q.empty()) {
  18.     pii u = q.top();q.pop();
  19.     int x = u.second;
  20.     if (done[x]) continue;
  21.     done[x] = true;
  22.     for (int e = first[x]; e != -1; e = next[e]) if (d[v[e]] > d[x] + w[e]) {
  23.         d[v[e]] = d[x] + w[e];
  24.         q.push(make_pair(d[v[e]]), v[e]);
  25.     }
  26. }

其中关于next数据实际上是稀疏图的邻接表
first[u]保存结点u的第一条边的编号，next[e]表示编号为e的边的下一条边的编号
void read_graph() {
cin >> n >> m;
for (int i = 0; i < n; i++) first[i] = -1;
for (int e = 0; e < m; ++e) {
cin >> u >> v >> w;
next[e] = first[u];
first[u] = e;
}
}
2. SPFA->负权边求最短路

  1. int spfa(int s){
  2.     visited[]s=1;
  3.     q.push(s);
  4.     d[s]=0;
  5.     while(!q.empty()){
  6.         int u=q.front(),q.pop();
  7.         visited[u]=0;  //visited 标记此节点是否在队列中
  8.         for (int i=1;i<=n;++i) {
  9.             if (edges[u][i]!=0) {
  10.                 if (d[i]>d[u]+edges[u][i]) {
  11.                     d[i]=d[u]+egdes[u][i];
  12.                     //pre[i]=u;
  13.                     if (!visited[i]) {
  14.                         cnt[i]++;
  15.                         if (cnt[i] > n) {
  16.                             return true; //存在负环
  17.                         }
  18.                         visited[i] = 1;
  19.                         q.push(i);
  20.                     }
  21.                 }
  22.             }
  23.         }
  24.     }
  25. }
  1. 最大流Dinic
  2. 并查集
  2. int fa[1000]; //初始化fa[i]=i
  3. int find(int x) {
  4.     int r = x;
  5.     while(r != fa[r]){
  6.         r = fa[r];
  7.     }
  8.     int i,j;
  9.     i = x;
  10.     while(i != r) { //路径压缩
  11.         j=fa[i];
  12.         fa[i]=r;
  13.         i=j;
  14.     }
  15.     return r;
  16. }
  18. int join(int x,int y) {
  19.     int r1=find(x);
  20.     int r2=find(y); //注意这里非常容易出错，一定是两个树根的合并!
  21.     if(r1!=r2){
  22.         fa[r1]=r2;
  23.     }
  24.     return fa[r1];
  25. }
  1. 拓扑排序

方法一: 用一个栈来保存入度为0的点较好

  1. //初始化要存储邻接关系以及indegree[]数组
  2. 首先遍历indegree数组，发现==0时入栈(入度为0的顶点入栈)
  3. while(!e.empty()) {
  4.     int u = e.top();e.pop();
  5.     indegree[u] = -1;
  6.     //从邻接关系中得到所有的邻接边并处理--indegree[i]，==0时也入栈
  7. }
  8. //遍历indegree数组查看是否元素全部为-1了
  9. 方法二:
  10. **深搜的逆后序即可拓扑排序的顺序**
  11. 前序:在深搜递归调用之前将顶点加入队列
  12. 后序:在递归调用之后将顶点加入队列
  13. 逆后序:在递归调用之后将顶点压入栈
  1. Kustal求最小生成树
    Prim算法其实也可以用队列实现，只不过队列中包含了很多的无用边以及无效边，最终可以通过索引优先队列进行优化，即保存了位置信息，而且不会存无效边。
    克鲁斯卡尔（Kruskal）算法因为只与边相关，则适合求稀疏图的最小生成树。而prime算法因为只与顶点有关，所以适合求稠密图的最小生成树。
  1. class node{
  2. public:
  3.     int u;
  4.     int v;
  5.     int cost;
  6. };
  7. bool compare(const node&i,const node&j){
  8.     return i.cost<j.cost;
  9. }
  10. int krusal(int n){
  11.     int num=0;
  12.     for(int i=0;i<q.size();++i){
  13.         int r1=find(q[i].u);
  14.         int r2=find(q[i].v);
  15.         if(r1!=r2){
  16.             used[q[i].u][q[i].v]=1;//为了输出最小生成树,也可以直接储存下用到的边的标号即可
  17.             fa[r1]=r2; //合并时有一个秩优化，即将较小的树合并到较大的树上边(http://noalgo.info/454.html)
  18.             num++;
  19.         }
  20.         if (num == n - 1) return true;
  21.     }
  22.     return num == n -1;
  23. }
  25. int main(){
  26.     sort(q.begin(),q.end(),compare);
  27.     krusal();
  28.     else //output
  29. }

7.Floyd算法
用于求任意两点之间的最短路

  1. //初始化:d[i][i] = 0;初始化边的集合,其他d[i][k]为INF，其中INF设置为最短路径的上限即可
  2. int minCircle = INF;
  3. for (int k = 0; k < n; ++k) {
  4.     for(int i = 0; i < k; i++)
  5.         for(int j = 0; j < i; j++)  
  6.             minCircle = min(minCircle, d[i][j] + gra[i][k] + gra[k][j]);  //添加的这一部分可用于求最小环
  7.     for (int i = 0; i < n; ++i)
  8.         for (int j = 0; j < n; ++j)
  9.              if(d[i][j]>d[i][k]+d[k][j]) d[i][j]=d[i][k]+d[k][j];
  10. }

  1. 图的连通性
    利用dfs和bfs在图上进行连通性的判断。关于图的存储，一种是存储邻接关系，以邻接表的形式，另外一种是存储相邻边，通过N*N的矩阵实现，两者都可以借助vector实现。

  2. 连通分量计算
    无向图:通过dfs计算,即下图删掉按照逆后序即可
    有向图:Kosaraju算法
    按照逆后序进行深搜，同时标记一下分支的id
    原理就是逆后序实际上是从入度为0的点开始的，是个source，从它开始遍历不会走出这个连通分量
    void Kosaraju() {
    for (int s : order.reversePost()) {
    if (!marked[s]) {
    dfs(G, s);count++;
    }
    }
    }

void dfs() {
markd[v] = true;
id [v] = count;
for (int w : G.adj(v)) {
if (!markd[w]) dfs(G, w);
}
}
10. 有无环的判定
实际上在dfs的过程中就可以办到，都是查找反向边的过程
无向图:
从dfs(G, s, s)开始即可。
void dfs(Digraph G, int v, int pre) {
marked[v] = true;
for (int w : G.adj(v)) {
if (!marked[w]) dfs(G, w);
else if (w != pre) {
//有环
}
}
}
有向图:
boolean[]onstack;
void start() {
for (int v = 0; v < G.v(); v++)
if (!marked[v]) dfs(G,v);
}
void dfs(Digraph G, int v) {
onStack[v] = true;
marked[v] = true;
for (int w : G.adj(v)) {
if (this.hasCycle()) return;
else if (!marked[w]) dfs(G, w);
else if (onStack(w)) {
//有环，同时可以得到路径
}
onStack[v] = false;
}
}

  1. 无环加权有向图中的最短路径以及最长路径
    distTo[]初始化为无穷大
    void AcycliSp() {
    distTo[s] = 0.0; //s为起点
    Tpological top = new Topological(G);
    for (int v : top.order())
    relax(G, v);
    }
    void relax() {
    for(DirectedEgde e : G.adj(v)) {
    int w = e.to();
    if (distTo[w] > distTo[v] + e.weight()) {
    distTo[w] = distTo[v] + e.weight();
    }
    }
    }
    最长路径只需要改变初始化时为负无穷大，并且改变relax中不等式的方向即可。

注意事项：
1. 图论的题目要注意多重边 负环 成环等特殊情况 no loops指的是没有自环
2. 关掉同步 ios::sync_with_stdio(false);
3. spfa是比二维数组的算法要快的
4. 统一处理string与int输入->atoi(t.c_str())
5. 控制精度 #include cout<

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注