ACM之图论基本算法详解

Dear 丶 2022-05-26 07:20 139阅读 0赞

# 图论基本算法 #

DFS,BFS  
两个生成树prim + Kruskal  
4个最短路径Dijkstra+Floyd+Bellman-Ford+SPFA

--------------------

## DFS&BFS ##

DFS——遍历所有解  
模板：

void DFS( Point P ){
            for(所有P的邻接点K){
                    if(K未被访问){
                             标记K;
                             DFS(K);
                             //有时候要清空之前的标记；
                    }
            }
    }

dfs一般会配合剪枝策略使用  
详见：[https://blog.csdn.net/u010700335/article/details/44095171][https_blog.csdn.net_u010700335_article_details_44095171]

BFS——寻找最优解  
利用队列，层次来搜索  
模板

Q={起点s}; 标记s为己访问;
        while (Q非空) {
            取Q队首元素u; u出队;
            所有与u相邻且未被访问的点进入队列;
            标记u为已访问;
        }
    ////////////////////////////////////////////////////////////
    whlie (队列不空) {
        u = 对队首元素；
        首元素出队；
        for (所有与 u 邻接点 v)      //  u 的上 下 左 右 
              // if(v 的坐标在 row, col之内 
              //     并且 v 不是墙
              //     并且 v 未被遍历) 
               v 入队
    }

--------------------

## 两个生成树 ##

## prim ##

算法核心思想：用集合论的观点来看，则是不断将离这棵树最近的点归约进来。

weight\[n\] 记录此集合中到各个点(i)的最短距离

adjex\[n\] 记录此集合中哪个点到各个点(i)的最短距离

visit[n]  记录哪些点属于那个集合 1为此树中，0为未归约进来的点

[cpp] view plain copy
    #include <stdio.h>  
    #include <string.h>  
    #define N 401  
    int state[N][N];  
    int maps [N][N];  
    
    
    int solve(int n)  
    {  
        int weight[N];  
        int adjex[N];  
        int visit[N];  
        int i,j,k;  
        int minnum,ans;  
        ans=0;  
        for(i=0;i<n;i++)  
            weight[i]=maps[0][i],adjex[i]=visit[i]=0;  
        visit[0]=1;  
        for(i=1;i<n;i++)  
        {  
            minnum=0xffffff;  
            for(j=1;j<n;j++)  
                if(minnum>weight[j] && visit[j] == 0)  
                    minnum=weight[j],k=j;  
            visit[k]=1;  
            ans+=minnum;  
            for(j=1;j<n;j++)  
                if(maps[k][j]<weight[j] && visit[j]==0 )  
                    weight[j]=maps[k][j],adjex[j]=k;  
    
        }  
        return ans;  
    
    }  
    
    
    
    
    
    
    int main()  
    {  
        int i,j,k,n;  
    
    while(  scanf("%d",&n)!=EOF)  
    {  
        for(i=0;i<n;i++)  
            for(j=0;j<n;j++)  
                scanf("%d",&maps[i][j]);  
    
        printf("%d\n",solve(n));  
    }  
    
        return 0;  
    }

## Kruskal ##

核心思想：不断用最短的边构建生成树，且避免回路。

使用并查集来快速查询一条边的两点是否在同一集合中，避免回路

[cpp] view plain copy
    /* 
    课堂上，归并的时候以边中最小结点编号作为连通子图的编号 
    此处使用归并集 
    */  
    void kruskal (edgeset ge, int n, int e)  
    // ge为权按从小到大排序的边集数组  
    {   
    int set[MAXE], v1, v2, i, j;  
    for (i=1;i<=n;i++)  
    set[i]=0;　 　// 给set中每个元素赋初值  
    i=1;　// i表示获取的生成树中的边数，初值为1  
    j=1;　// j表示ge中的下标，初始值为1  
    while (j<n && i<=e)  
    // 检查该边是否加入到生成树中  
    {  
    v1=seeks(set,ge[i].bv);  
    v2=seeks(set,ge[i].tv);  
    if (v1!=v2)　// 当v1,v2不在同一集合，该边加入生成树  
    {  
    printf(“(%d,%d)”,ge[i].bv,ge[i].tv);  
    set[v1]=v2;  
    j++;//j是为了判断是否已经使n个点加入生成树中，是则结束  
    }  
    i++;  
    }  
    }  
    int seeks( int *set,int i)  
    {  
        while(set[i]!=i)  
            i=set[i];  
        return i;  
    }

注：并查集可以使用路径压缩，每次查询的时候递归返回，使查询时间到O(1)。

--------------------

## 四个最短路 ##

## Dijkstra ##

每次用图中节点更新所有点路径，以达到最短路径的目的  
1.循环n次  
2.在所以d\[\]节点中找到最小点x  
3.标记该点x  
4.对于从该点出发的边更新d\[y\]=min\{d\[y\],d\[x\]+w\[x\]\[y\]\}

[cpp] view plain copy
    void Dijkstra(){       
           int k;  
        for(int i=1;i<=n;i++)        
            dis[i] = map[1][i];          
        for(int i=1;i<n;i++){        
            int tmin = maxint;       
            for(int j=1;j<=n;j++)         
                if( !used[j] && tmin > dis[j] ){          
                    tmin = dis[j];  
                    k = j;  
                }  
                used[k] = 1;        
            for(int j=1;j<=n;j++)         
                if( !used[j] &&dis[k] + map[k][j] < dis[j] )  //跟佛洛依德算法相似，看中间是否有个中间点  
                    dis[j] = dis[k] + map[k][j];       
         }       
         printf("%d",dis[n]);  
    } /* 求1到N的最短路,dis[i] 表示第i个点到第一个点的最短路 By Ping*/  
    //找未用过的最短邻接点，以此为中转修正其余点，直到全部完成

## Floyd ##

注意使用更新的中间结点k在最外层。（之前写了个在最内层，违背了方法。用一个节点更新所有路径）

可以有负权边的图进行计算

对于任意两点 (i,j) 之间,每次使用一个结点更新所有路径。同时我们知道，任意两点之间最短距离最多经过n-1个结点

这样下来，对于特定两点来说加入的点的次序变得不重要

1.加的点不再所求两点的路上，无所谓

2.从与两点直接相连到间接相连，符合我们的思维

3.最重要，若是无序，如果从中间一个开始怎么办？

若是中间点，则会更新与之相连点间的最短路径，这样对于下一次次中间点有帮助，同时也相当于先修了”中间路”.

[cpp] view plain copy
    //d[i][j]用于记录从i到j的最短路径的长度  
    // path[i][j]用于记录从i到j的最短路径上j点的前一个节点  
    //d[i][j]用于记录从i到j的最短路径的长度  
    void Floyd(int num,int **path,int**d,int **a)  
    
    
    {  
        int i,j,k;  
        for(i=0;i<num;i++)  
        {  
            for(j=0;j<num;j++)//初始化  
            {  
                if(a[i][j]<max) path[i][j]=j;//从i到j有路径  
                else path[i][j]=-1;  
                d[i][j]=a[i][j];  
            }  
        }  
        for(k=0;k<num;k++)  
            for(i=0;i<num;i++)  
                for(j=0;j<num;j++)  
                    if(d[i][j]>d[i][k]+d[k][j])//从i到j的一条更短的路径  
                    {  
                        d[i][j]=d[i][k]+d[k][j];  
                        path[i][j]=path[i][k];  
                    }  
    }

## Bellman-Ford ##

之前的求最短路径要求图中无负向边，该算法可以求有负向边的图最短路径。

对每条边进行松弛，每次松弛至少可以增加一个抵达点，所以外循环至多v-1次，

与迪杰斯特拉不同之处在于：迪杰斯特拉每次使用一个点更新后不再使用，而贝尔曼的每条边每次都使用。

迪杰斯特拉每次都从已找到的最短路的集合中寻找一条连接到没找到的集合的一条路，不会再次计算集合内部的点的最短路。

解释：

dijkstra由于是贪心的，每次都找一个距源点最近的点（dmin），然后将该距离定为这个点到源点的最短路径（d\[i\]<–dmin）；但如果存在负权边，那就有可能先通过并不是距源点最近的一个次优点（dmin’），再通过这个负权边L(L<0)，使得路径之和更小（dmin’+L

算法实现：
    
    [cpp] view plain copy
    #include <iostream>  
    using namespace std;  
    const int maxnum = 100;  
    const int maxint = 99999;  
    
    // 边，  
    typedef struct Edge{  
        int u, v;    // 起点，重点  
        int weight;  // 边的权值  
    }Edge;  
    
    Edge edge[maxnum];     // 保存边的值  
    int  dist[maxnum];     // 结点到源点最小距离  
    
    int nodenum, edgenum, source;    // 结点数，边数，源点  
    
    // 初始化图  
    void init()  
    {  
        // 输入结点数，边数，源点  
        cin >> nodenum >> edgenum >> source;  
        for(int i=1; i<=nodenum; ++i)  
            dist[i] = maxint;  
        dist[source] = 0;  
        for(int i=1; i<=edgenum; ++i)  
        {  
            cin >> edge[i].u >> edge[i].v >> edge[i].weight;  
            if(edge[i].u == source)          //注意这里设置初始情况  
                dist[edge[i].v] = edge[i].weight;  
        }  
    }  
    
    // 松弛计算  
    void relax(int u, int v, int weight)  
    {  
        if(dist[v] > dist[u] + weight)  
            dist[v] = dist[u] + weight;  
    }  
    
    bool Bellman_Ford()  
    {  
        for(int i=1; i<=nodenum-1; ++i)  
            for(int j=1; j<=edgenum; ++j)  
                relax(edge[j].u, edge[j].v, edge[j].weight);  
        bool flag = 1;  
        // 判断是否有负环路  
        for(int i=1; i<=edgenum; ++i)  
            if(dist[edge[i].v] > dist[edge[i].u] + edge[i].weight)  
            {  
                flag = 0;  
                break;  
            }  
        return flag;  
    }  
    int main()  
    {  
        //freopen("input3.txt", "r", stdin);  
        init();  
        if(Bellman_Ford())  
            for(int i = 1 ;i <= nodenum; i++)  
                cout << dist[i] << endl;  
        return 0;  
    }

## SPFA（万能最短路算法） ##

详解看：[https://blog.csdn.net/xunalove/article/details/70045815][https_blog.csdn.net_xunalove_article_details_70045815]  
初始化的时候只添加出边,不添加入边不然顶住

使用队列优化 Bellman-Ford 算法其原理是利用：

不一定每次都要把所有的边都松弛一遍，只有在上次更新过的点所连的边才会对下次松弛有作用。而SPFA则记录了这些刚刚更新过点

若一个点进队N次则判断该图有环，退出。或者队空，退出

初始化时仅起始点进队.

void  spfa(s);  //求单源点s到其它各顶点的最短距离
        for i=1 to n do { dis[i]=∞; vis[i]=false; }   //初始化每点到s的距离，不在队列
        dis[s]=0;  //将dis[源点]设为0
        vis[s]=true; //源点s入队列
        head=0; tail=1; q[tail]=s; //源点s入队, 头尾指针赋初值
        while head<tail do {
           head+1;  //队首出队
           v=q[head];  //队首结点v
           vis[v]=false;  //释放对v的标记，可以重新入队
           for 每条边(v,i)  //对于与队首v相连的每一条边
          if (dis[i]>dis[v]+a[v][i])  //如果不满足三角形性质
            dis[i] = dis[v] + a[v][i]   //松弛dis[i]
            if (vis[i]=false) {tail+1; q[tail]=i; vis[i]=true;} //不在队列，则加入队列
        }

[https_blog.csdn.net_u010700335_article_details_44095171]: https://blog.csdn.net/u010700335/article/details/44095171
[https_blog.csdn.net_xunalove_article_details_70045815]: https://blog.csdn.net/xunalove/article/details/70045815