QQ截图20160729182823.png

一直都是在刷题,从来没总结过算法,这样不好啊,特别是这周,发现这么多算法,好多都有相似之处,所以,来个总结把。

下面是总结表:

算法时间复杂度关键词特性
KruskalO(nlogn)最小生成树算法、 维护森林、 并查集、 路径压缩、 稀疏图Kruskal算法主要是运用了并查集的思想,将集合外的元素加入集合中。这个算法的一个重点在于要先排序,然后按照从小到大的顺序取点不断加入集合。它不像其它几种算法,它在过程中维护的可能不是一棵树,可能是一个森林,到最后才把森林变成一棵最小生成树。在加入集合时,使用路径压缩算法可以提高效率。这个算法应该是最好理解的吧。程序中的主要流程就是排序,找父节点(路径压缩),集合不同则加入同一个集合。
PrimO(n^2)最小生成树算法、 维护树、 不断加入最小权、 稠密图Prim算法的主要思想是不断找最小的权加入当前集合。当所有的权都被加入集合,这个集合的权之和就是最小生成树的权的和。它始终维护一棵树,比较简单,效率也比较高。程序中的主要流程就是加入最小权,更新周围的权,重复这个步骤。
DijkstraO(n^2)最短路径算法、 维护树、 更新距离、 单源最短路径Dijkstra算法的主要思想是永远保持当前节点到源点的距离最短。算法实现简单,就是一个找当前距离最小的节点,如果它的周围有节点可以通过当前节点减少距离那么就更新他的距离。当然,我们使用普通的邻接矩阵可能不会发挥Dijkstra算法的真正效率之处, 使用邻接表优化后的Dijkstra算法才能发挥它的高效率。
SpfaO(km) m为边数 k一般为2或3 最坏情况下会退化到O(n2)动态逼进法、 最短路径算法、 更新路径、 单源最短路径Spfa算法主要思想是通过一个队列来对一个距离数组进行不断的松弛操作,运用了BFS的思想(当然,经过优化的Dijkstra算法也可以这样用,个人觉得他们之间相似之处简直不能再相似了,特别是优化的Dijkstra算法,只不过Spfa能解决带负权的问题。)。

下面是各个算法的演示图和关键代码:

1、Kruskal算法:

blob.png blob.png blob.png blob.png blob.png blob.png

由图可以看出Kruskal算法并不是一开始就在维护一棵树,而是到最后才把森林合并成一棵树的。下面贴出一段模板:

const int maxn=100;
int n, cnt, fa[maxn];

struct edge {
    int u, v, cost;
    bool operator<(const edge &cmp) const {
        return cost<cmp.cost;
    }
} E[maxn];

int Find(int x) {
    return x==fa[x]?x:fa[x]=Find(fa[x]);
}

int Kruskal() {
    for(int i=0; i<=n; i++)fa[i]=i;
    sort(E, E+cnt);
    int ans=0;
    for(int i=0; i<cnt; i++) {
        int fu=Find(E[i].u);
        int fv=Find(E[i].v);
        if(fu!=fv) {
            fa[fu]=fv;
            ans+=E[i].cost;
        }
    }
    return ans;
}

2、Prim算法:

blob.pngblob.pngblob.pngblob.pngblob.pngblob.png

由图可以看出,Prim算法始终在维护一棵树。当所有元素加进来,这棵树也生成了,这个树就是最小生成树。Prim算法始终加入的都是距离当前集合最近的那个元素。下面给出关键代码:

const int maxn=28;
int vis[maxn];
struct edge {
    edge(int v, int c) {
        to=v,cost=c;
    }
    edge() {}
    int to, cost;
    bool operator<(const edge &cmp)const {
        return cost>cmp.cost;
    }
};

priority_queue<edge> que;
vector<edge> E[maxn];

void Init() {
    memset(vis, 0, sizeof(vis));
    for(int i=0; i<maxn; i++)E[i].clear();
    while(!que.empty())que.pop();
}

int Prim() {
    int ans=0;
    vis[0]=1;
    for(int i=0; i<E[0].size(); i++) {
        que.push(E[0][i]);
    }
    while(!que.empty()) {
        edge e=que.top();
        que.pop();
        if(vis[e.to])continue;
        vis[e.to]=1;
        ans+=e.cost;
        for(int i=0; i<E[e.to].size(); i++) {
            que.push(E[e.to][i]);
        }
    }
    return ans;
}

3、Dijkstra算法:

blob.png blob.png blob.png blob.png blob.png blob.png

由图可以看出,Dijkstra 算法始终在使用贪心算法对周围的节点进行距离更新,通过局部最优到达最后的整体最优。当然,Dijkstra算法是一种单源最短路径算法,只能计算某个点到其他各点的最小距离。下面给出模板代码:

struct Dijkstra{
    int dis[maxn];
    priority_queue<pair<int, int> > Q;

    void init(){
        for(int i=0;i<maxn;i++){
            dis[i]=inf;
            E[i].clear();
        }
    }

    int dijkstra(int s, int e){
        dis[s]=0;
        Q.push(make_pair(0, s));
        while(!Q.empty()){
            int u=Q.top().second;
            Q.pop();
            for(int i=0;i<E[u].size();i++){
                int v=E[u][i].first;
                if(dis[v]>dis[u]+E[u][i].second){
                    dis[v]=dis[u]+E[u][i].second;
                    Q.push(make_pair(-dis[v], v));
                }
            }
        }
        return dis[e]==inf?-1:dis[e];
    }
};

4、Spfa算法:

图解请看上面的Dijkstra算法,思想类似,BFS嘛,就是上下左右搜咯,这里就不贴图了。直接上代码吧。。



struct Spfa{
    int dis[maxn], inq[maxn];
    vector<pair<int, int> > E[maxn];
    void init(){
        for(int i=0;i<maxn;i++){
            dis[i]=inf;
            E[i].clear();
            inq[i]=0;
        }
    }
    int spfa(int s){
        queue<int> Q;
        dis[s]=0;
        inq[s]=1;
        Q.push(s);
        while(!Q.empty()){
            int u=Q.front();
            Q.pop();
            inq[u]=0;
            for(int i=0;i<E[u].size();i++){
                int v=E[u][i].first;
                if(dis[v]>dis[u]+E[u][i].second){
                    dis[v]=dis[u]+E[u][i].second;
                    if(inq[v])continue;
                    Q.push(v);
                    inq[v]=1;
                }
            }
        }
        return dis[n];
    }
};