必知必会的图论算法

dijkstra:

vector<int> dijkstra(vector<vector<int>>& graph, int src) {
    vector<int> sp; //distance from src to others
    sp = graph[src]; //initialize

    int N = graph.size();
    vector<bool> s(N, false);
    s[src] = true;
    sp[src] = 0;

    for (int num = 0; num < N - 1; num++) {
        int k = -1;
        int mp = -1;
        for (int i = 0; i < N; i++) {
            if (s[i])
                continue;
            if (mp < 0 || mp > sp[i]) {
                mp = sp[i];
                k = i;
            }
        }
        s[k] = true;
        for (int i = 0; i < N; i++) {
            if(s[i])
                continue;
            sp[i] = min(sp[i],sp[k]+graph[k][i]);
        }
    }
    return sp;
}

floyd:

vector<vector<int>> floyd(const vector<vector<int>>& graph) {
    vector<vector<int>> sp;
    sp = graph;
    int N = (int) graph.size();

    for (int i = 0; i < N; i++) {
        for (int j = 0; i < N; j++) {
            for (int k = 0; k < N; k++) {
                if(sp[i][j] > sp[i][k] + sp[k][j])
                    sp[i][j] = sp[i][k] + sp[k][j];
            }
        }
    }
    return sp;

 prim:

struct SEdge {
    int from;
    int to;
    int val;
    SEdge(int a, int b, int c) :
            from(a), to(b), val(c) {
    }
};

bool prim(const vector<vector<int>>& graph,vector<SEdge>& mst) {
    int N = (int) graph.size();

    vector<bool> s(N, false);       //集合S
    vector<int> dis(N);   //s中结点到其它节点i的距离
    vector<int> from(N, 0); //from[i]=j,s中距离i最近的节点为j

    dis = graph[0]; //以结点作为生成数的根节点
    s[0] = true;

    int d;
    for (int t = 1; t < N; t++) {
        int k = -1;
        //从集合s之外选择加入的节点
        for (int i = 0; i < N; i++) {
            if(s[i]) continue;
            if(k==-1 || d > dis[i]){
                d = dis[i];
                k = i;
            }
        }
        mst[t-1] = SEdge(from[k],k,dis[k]);
        s[k] = true;   //集合s中加入节点k

        //使用节点k更新dis[0...N-1]
        for(int i=0;i<N;i++){
            if(!s[i] && (dis[i] > graph[k][i])){
                dis[i] = graph[k][i];
                from[i] = k;
            }
        }
    }
    return true;
}

kruskal:

class UnionFindSet{
private:
    int m;
    int* fa;
public:
    UnionFindSet(int n){
        m = n;
        fa = new int[m];
        for(int i=0;i<n;i++)
            fa[i] = i;
    }
    ~UnionFindSet(){
        if(fa != nullptr){
            delete[] fa;
            fa = nullptr;
        }
    }

    int find(int x){
        if(x<0 || x>m)
            return -1;

        while(x != fa[x])
            x = fa[x];

        return x;
    }

    void merge(int i,int j){
        if(i<0 || i>m || j<0 || j>m)
            return;
        int ri = find(i);
        int rj = find(j);
        if(ri != rj)
            fa[ri] = rj;
    }
};


struct Edge {
    int fm;
    int to;
    int dist;
    Edge(int a, int b, int c) :
            fm(a), to(b), dist(c) {
    }
};

class kruskalSolution {
private:
    static bool cmpEdge(Edge a,Edge b){
        return a.dist < b.dist;
    }
public:
    void kruskal(vector<vector<int>>& graph, vector<Edge>& mst) {
        vector<Edge> edgeVec;
        int N = graph.size();
        for (int i = 0; i < N; i++) {
            for (int j = i; j < N; j++) {
                edgeVec.push_back(Edge(i,j,graph[i][j]));
            }
        }
        sort(edgeVec.begin(),edgeVec.end(),cmpEdge);

        UnionFindSet s(N);
        int k = 0;
        for(Edge e : edgeVec){
            int ri = s.find(e.fm);
            int rj = s.find(e.to);

            if(ri == rj)
                continue;
            s.merge(e.fm,e.to);
            mst[k++] = e;
            if(k == N-1)
                break;
        }
    }
};