【算法与数据结构】——Dijkstra算法，最小生成树

分手后的思念是犯贱 2022-09-04 10:53 146阅读 0赞

# Dijkstra算法 #

Dijkstra算法是解决单源最短路径的常用办法，不过只适用于边的权重为正的情况，但是其拓展性较强，可以适应许多问题，并且与堆结合可以拥有更快的效率。  
算法思想：每次找到距源点最短的顶点，以该顶点为中心进行拓展，最终得到源点到其余各点的最短路径。  
基本步骤：  
1、将所有顶点分为两部分：已知最短路径的顶点集合A和未知最短路径的B  
2、设置源点到自己的最短路径长度为0，将源点的邻接点的最短路径设为与源点边的权重，其他点最短路径设置为正无穷  
3、在B中所有顶点中选择一个离源点最近的顶点u加入到A中，并考察所有以点u为起点的边，对每一条边进行松弛操作，例如存在一条从u到v的边，那么可以将u->v添加到尾部来拓展从源点到v的路径，路径长度是dis\[u\]+Graph\[u\]\[v\]，如果这个值比dis\[v\]小，用dis\[u\]+Graph\[u\]\[v\]来代替  
4、重复第3步直到B为空  
代码：

#include <iostream>
    #define INF 99999
    using namespace std;
    bool visited[1212];//判断是否已经访问过
    int Graph[1212][1212],Dis[1212],Start,End,N,M;
    //Graph存储权重，Dis存储各点到源点的最小距离
    //Start、End为起点终点，N为顶点数，M为边数
    void Dijkstra()
    { 
        int m=INF,loc;
        for(int i=1; i<=N; i++)
            if(Dis[i]<m&&!visited[i])//找出离源点最近的未收录的顶点
            { 
                m=Dis[i];
                loc=i;
            }
        visited[loc]=true;//收录
        for(int i=1; i<=N; i++)
            if(Graph[loc][i]<INF&&Dis[loc]+Graph[loc][i]<Dis[i])
            //进行松弛操作，判断这个已收录的顶点能否使其领接点到源点的距离变小
                Dis[i]=Dis[loc]+Graph[loc][i];
    }
    int main()
    { 
        freopen("test.txt","r",stdin);
        cin >>N>>M>>Start>>End;
        for(int i=1; i<=N; i++)
            for(int j=1; j<=N; j++)
                if(i!=j)
                    Graph[i][j]=INF;//初始化
        while(M--)
        { 
            int a,b,w;
            cin >>a>>b>>w;
            Graph[a][b]=w;//Dijkstra处理有向图
        }
        for(int i=1; i<=N; i++)
            Dis[i]=Graph[Start][i];//路径初始化
        visited[Start]=true;
        for(int i=1; i<N; i++)//每次收录一个顶点并以它为中心进行松弛
            Dijkstra();
        for(int i=1; i<=N; i++)
            cout <<Dis[i]<<" ";
        return 0;
    }

# 最小生成树算法 #

最小生成树是指在图中找到的边权和最小的树。主要有两种算法，Prim算法和Kruskal算法。

## prim算法 ##

Prim算法和Dijkstra算法在许多地方有类似之处，Prim算法是存储各顶点到已经生成的最小生成树的“树距”，Dijkstra算法是存储各顶点到源点的“点距”

算法思想：将顶点分为已入树顶点与未入树顶点，首先选择任意一个顶点加入生成树，之后找到在每一个树顶点到每一个非树顶点的边中找到最短边加入生成树，执行n-1次（通过枚举）

基本步骤：

> 1、从任意一个顶点开始构造生成树，设从一号顶点，将一号顶点加入生成树  
> 2、最初生成树只有1号节点，初始化距离数组Dis  
> 3、从Dis中选出离生成树最近的顶点j加入生成树中，以该点为中间点，更新生成树到每一个非树顶点的距离，即Dis\[k\]>e\[j\]\[k\]时Dis\[k\]=e\[j\]\[k\]  
> 4、重复3，直到n个顶点都入树

图示和代码详细解释可以参考[最小生成树Prim算法理解][Prim]  
代码：这个代码是求最小生成树的最大边权值的

/* **Author:skj **Time: **Function: */
    #include <bits/stdc++.h>
    #define ll long long
    #define INF 0x3f3f3f3f
    using namespace std;
    const int N = 5e3+5;
    const ll W = 2e18;//最大边权值
    ll lowcost[N];//表示生成树上以i为终点的边的最小权值,当lowcost[i]=0说明以i为终点的边的最小权值=0,也就是表示i点加入了MST
    int mst[N];//表示对应lowcost[i]的起点，即说明边<mst[i],i>是MST的一条边，当mst[i]=0表示起点i加入MST
    ll graph[N][N];
    pair<int,int> p[N];//点坐标
    
    ll weight(int a,int b)
    { 
        return (1LL*p[a].first-p[b].first)*(1LL*p[a].first-p[b].first)+
        (p[a].second-1LL*p[b].second)*(p[a].second-1LL*p[b].second);
    }
    
    void solve()
    { 
        int n;
        scanf("%d",&n);
        for(int i = 1;i <= n;i++)
        { 
            scanf("%d",&p[i].first);
            scanf("%d",&p[i].second);
        }
    
        for(int i = 1;i <= n;i++)
        { 
            for(int j = i+1;j <= n;j++)
            { 
                ll w = weight(i,j);
                graph[i][j] = w;
                graph[j][i] = w;
            }
            lowcost[i] = W;
        }
        for(int i = 2;i <= n;i++)
        { 
            mst[i] = 1;
            lowcost[i] = graph[1][i];
        }
        mst[1] = 0;
        ll ma = 0;
        for(int i = 2;i <= n;i++)
        { 
            ll mi = W;
            int minid = 0;
            for(int j = 2;j <= n;j++)
            { 
                if(lowcost[j]<mi&&lowcost[j]!=0)
                { 
                    mi = lowcost[j];
                    minid = j;
                }
            }
            lowcost[minid] = 0;
            mst[minid] = 0;
            ma = max(mi,ma);
            for(int j = 2;j <= n;j++)
            { 
                if(lowcost[j] > graph[minid][j])
                { 
                    lowcost[j] = graph[minid][j];
                    mst[j] = minid;
                }
            }
        }
        printf("%lld\n",ma);
    }
    int main()
    { 
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
        int t;
        scanf("%d",&t);
        while(t--)
        { 
            solve();
        }
        return 0;
    }

# Kruskal算法 #

Kruskal算法对于最小生成树的构造符合我们的常用认知，即从边的集合中找出最小值、次小值、次次小值等来构成所需要的树，但是在拿取边的时候需要判断是否会构成连通域，使用并查集来判断，理论上能用BFS和DFS，但是效率低

算法思想：每次选取未使用的最短边进行构建

按照边的权值进行从小到大进行排序，每次从剩余边中选择权值较小且不会产生回路的边加入到生成树中，直到加了n-1条边,**需要注意的是需要用并查集确定点所在的集合，防止出现没有连成一棵树的情况**。算法复杂度O( ∣ E ∣ log ⁡ ∣ E ∣ |E|\\log |E| ∣E∣log∣E∣)  
代码：这个代码是求最小生成树的最大值的

/* **Author:skj **Time:2020.8.15 **Function:求最小生成树kruskal算法 */
    #include <bits/stdc++.h>
    #define ll long long
    #define INF 0x3f3f3f3f
    using namespace std;
    const int N = 5e3+5;
    struct Edge
    { 
        int a,b;//两个点
        ll w;//边长
        const bool operator< (Edge e1) const
        { 
            return w > e1.w;
        }
    };
    struct point
    { 
        int a;//终点
        ll w;//边长
        const bool operator< (Edge e1) const
        { 
            return w > e1.w;
        }
    };
    int pre[N];
    pair<int,int> p[N];//点坐标
    
    int Find(int x)     				//查找结点 x的根结点
    { 
        if(pre[x] == x) return x;		//递归出口：x的上级为 x本身，即 x为根结点
        return pre[x] = Find(pre[x]);	//此代码相当于先找到根结点 rootx，然后pre[x]=rootx
    }
    
    void join(int x,int y)
    { 
        x = Find(x);
        y = Find(y);
        if(x != y)
        { 
            pre[x] = y;
        }
    }
    
    ll weight(int a,int b)
    { 
        return (1LL*p[a].first-p[b].first)*(1LL*p[a].first-p[b].first)+
        (p[a].second-1LL*p[b].second)*(p[a].second-1LL*p[b].second);
    }
    
    void solve()
    { 
    
        int n;
        scanf("%d",&n);
        for(int i = 1;i <= n;i++)
        { 
            pre[i] = i;
        }
        for(int i = 1;i <= n;i++)
        { 
            scanf("%d",&p[i].first);
            scanf("%d",&p[i].second);
        }
        priority_queue<Edge> e;
        for(int i = 1;i <= n;i++)
        { 
            for(int j = i + 1;j <= n;j++)
            { 
                Edge ee;
                ee.a = i;
                ee.b = j;
                ee.w = weight(i,j);
                e.push(ee);
            }
        }
        ll ma = 0;
        n--;
        while(!e.empty())
        { 
            if(Find(e.top().a)!=Find(e.top().b))
            { 
                join(e.top().a,e.top().b);
                ma = max(ma,e.top().w);
            }
            if(!n)
            { 
                break;
            }
            e.pop();
        }
        cout << ma << endl;
    }
    int main()
    { 
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
        int t;
        scanf("%d",&t);
        while(t--)
        { 
            solve();
        }
        return 0;
    }

[Prim]: https://blog.csdn.net/yeruby/article/details/38615045