图论的基础算法

ACM

本文将着重最基本的图论的算法。顺便学习一下不会的知识。

图的存储

在编程时，一般使用的方法有：

  • 邻接矩阵
  • 邻接表(vector)
  • 链式前向星

前面的一种是针对稠密图而言的。后面的两种是针对稀疏图而言的,链式前向星用的比较的少，学习它只是便于读懂他人的代码。
其中邻接表用的最多，因为大部分的图都是稀疏图。链式前向星主要就是没有使用vector的可扩展大小的特性而已，它存入的顺序和读取的顺序是相反的。

图的遍历

分为DFS遍历和BFS遍历。

DFS遍历

没什么想说明的，直接上代码吧。还是讲两句，dfs序在划分的时候非常有用，将树形的结构转化为线性的。但是我好想已经忘了怎么用了emmmmmm.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
vector<int> G[maxn];
bool vis[maxn];
int n, k, s;
/*
6 9 0
0 1
0 2
2 1
1 3
1 4
2 4
4 3
5 3
4 5
*/
void dfs(int u, int depth){
    vis[u] = true;
    printf("%d ", u);
    for(int i=0; i<G[u].size(); i++){
        int v = G[u][i];
        if(!vis[v]){
            dfs(v, depth+1);
        }
    }
}
void dfs_traverse(){
    memset(vis, 0, sizeof(vis));
    for(int i=0; i<n; i++){
        if(!vis[i]){
            dfs(i, 1);
        }
    }
    printf("\n");
}
int main()
{
    while(~scanf("%d%d%d", &n, &k, &s)){
        for(int i=0; i<maxn; i++)G[i].clear();
        for(int i=0; i<k; i++){
            int u, v;
            scanf("%d%d", &u, &v);
            G[u].push_back(v);
        }
        dfs_traverse();
    }
    return 0;
}

BFS遍历

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
vector<int> G[maxn];
int n, k;
bool inq[maxn];
void bfs(int u){
    queue<int> q;
    q.push(u);
    inq[u] = true;
    while(!q.empty()){
        int temp = q.front();
        q.pop();
        printf("%d ", temp);
        for(int i=0; i<G[temp].size(); i++){
            int v = G[temp][i];
            if(!inq[v]) q.push(v), inq[v] = true;
        }
    }
}
void bfs_traverse(){
    memset(inq, 0, sizeof(inq));
    bfs(0);
    printf("\n");
}
int main()
{
    while(~scanf("%d%d", &n, &k)){
        for(int i=0; i<maxn; i++)G[i].clear();
        for(int i=0; i<k; i++){
            int u, v;
            scanf("%d%d", &u, &v);
            G[u].push_back(v);
        }
        bfs_traverse();
    }
    return 0;
}

最短路算算法

Dijkstra算法

本质上就是一种不断的贪心思想。
应用的范围：注意边权是非负的值。
下面的例子说明了存在负边权时，Dijkstra错误处理的情况：

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
bool vis[maxn];
int G[maxn][maxn];
int dis[maxn];
int n, e, s;
const int INF = 1e9;
//序号从0开始
void dijkstra(){
    for(int i=0; i<maxn; i++)dis[i] = INF;
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;
    for(int i=0; i<n; i++){
        int u = -1;
        int min_weigth = INF;
        for(int j=0; j<n; j++){
            if(!vis[j]&&min_weigth>dis[j])
                min_weigth = dis[j], u = j;
        }
        vis[u] = true;
        for(int v=0; v<n; v++){
            if(!vis[v]&&G[u][v]!=0x7f7f7f7f){
                dis[v] = min(dis[v], dis[u]+G[u][v]);
            }
        }
    }
}
int main()
{
    while(~scanf("%d%d%d", &n, &e, &s)){
        int u, v, weight;
        memset(G, 0x7f, sizeof(G));
        for(int i=0; i<e; i++){
            scanf("%d%d%d", &u, &v, &weight);
            G[u][v] = weight;
        }
        dijkstra();
        printf("%d点到其他所有点的最短距离为：\n", s);
        for(int i=0; i<n; i++){
            printf("编号%d: %d ", i, dis[i]);
        }
    }
    return 0;
}

上面的代码的时间复杂度为O(\(n^2\))
如果采用邻接表的形式来保存图，若是稀疏图，那么只是遍历边的时候减小了时间复杂度的常数项。

仔细分析，发现我们发了O(n)的时间复杂度来找最小点，而实际上我们可以将其优化到O(log(n)),找到后对其邻接的点的距离最小值进行更新。
总时间复杂度为O(\(E·logn\))

优化代码

注意一个点可以多次的进出优先队列，但是这只影响时间复杂度的常数项。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
int INF = 1e9;
struct Edge{
    int to, weight;
}edge[maxn];
int n, k ,s;
vector<Edge> G[maxn];
typedef pair<int, int> P;//第一维保存最短距离，第二维保存点标
int dis[maxn];
void Dijkstr(){
    priority_queue<P, vector<P>, greater<P> > pq;
    memset(dis, 0x7f, sizeof(dis));
    dis[s] = 0;
    pq.push(P(0, s));
    while(!pq.empty()){
        P p = pq.top();
        int u = p.second;
        pq.pop();
        if(dis[u]<p.first) continue;
        for(int i=0; i<G[u].size(); i++){
            int v = G[u][i].to;
            if(dis[v]>dis[u]+G[u][i].weight){
                dis[v] = dis[u]+G[u][i].weight;
                pq.push(P(dis[v], v));
            }
        }
    }
}
int main()
{
    while(~scanf("%d%d%d", &n, &k, &s)){
        int u, v, weight;
        Edge temp;
        for(int i=0; i<maxn; i++)G[i].clear();
        for(int i=0; i<k; i++){
            scanf("%d%d%d", &u, &v, &weight);
            temp.to = v, temp.weight = weight;
            G[u].push_back(temp);
        }
        Dijkstr();
        for(int i=0; i<n; i++){
            printf("%d ", dis[i]);
        }
        printf("\n");
    }
    return 0;
}

我们都能愉快使用优化后的代码了，当然如果是稠密图的话，两者的时间复杂度将会差不多。

Bellman-ford算法

感觉运用了动态规划的思想：
对所有的边进行了一次遍历，这样遍历了n-1之后，dis[]就是从源点到各点的最短路。
由于可能存在负环，再进行一次遍历，若dis[]数组仍然能够更新，那么说明存在负环。

下面简单的说明为什么要遍历n-1次。

我们首先将s(源点)作为一根树的树根，每次到其它点的最短距离构成了一棵最短路径树。
每次遍历一次所有的边，那么相当于更新了一层树。
这棵树树除了根节点，最多有n-1层（也就是链式的树），因此最多遍历n-1次就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
const int INF = 1e9;
struct Edge{
    int to, weight;
};
vector<Edge> G[maxn];
/*
存在负环的情况:
3 3 0
0 1 -1
1 2 2
2 0 -3
*/
int n, k, s;
int dis[maxn];
bool Bellman_ford(){
    for(int i=0; i<maxn; i++)dis[i] = INF;
    dis[s] = 0;
    //进行n-1一轮的遍历，每一次的遍历都遍历所有的边。
    for(int i=0; i<n-1; i++){
        for(int u=0; u<n; u++){
            for(int j =0; j<G[u].size(); j++){
                int v = G[u][j].to;
                dis[v] = min(dis[v], dis[u]+G[u][j].weight);
            }
        }
    }
    bool flag = false;
    for(int u=0; u<n; u++){
        for(int j=0; j<G[u].size(); j++){
            int v = G[u][j].to;
            if(dis[v]>dis[u]+G[u][j].weight){
                flag = true;
                break;
            }
        }
    }
    return flag;
}
int main()
{
    while(~scanf("%d%d%d", &n, &k, &s)){
        int u, v, weight;
        Edge temp;
        for(int i=0; i<maxn; i++)G[i].clear();
        for(int i=0; i<k; i++){
            scanf("%d%d%d", &u, &v, &weight);
            temp.to = v;
            temp.weight = weight;
            G[u].push_back(temp);
        }
        if(!Bellman_ford()){
            printf("There is no negative loop~\n");
            for(int i=0; i<n; i++)printf("%d ", dis[i]);
            printf("\n");
        }
        else printf("There exists negative loop\n");
    }
    return 0;
}

当然，如果我们已经更新了所有的节点，那么可以提前退出。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
bool quit = true;
for(int i=0; i<n-1; i++){
    for(int u=0; u<n; u++){
        for(int j =0; j<G[u].size(); j++){
            int v = G[u][j].to;
            if(dis[v]>dis[u]+G[u][j].weight){
                dis[v] = dis[u]+G[u][j].weight;
                quit = false;
            }
        }
    }
    if(quit) break;
}

这个算法的时间复杂度为O(E·n),我们可以看出每一次都要遍历所有的边时，最坏的情况下能够更新的节点数只有1，而我们却要遍历所有的边，十分的浪费时间。

SPFA算法

SPFA运用了一个性质，一个点最多被更新n-1次，如果更新的次数超过n-1次，那么表明存在负环。
具体的证明我也不是很清楚，下面列一个一个点最多入队n-1次的点，希望帮助理解。

代码

最关键的是一个点不可能被更新n次， 最多更新n-1次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
const int INF = 1e9;
struct Edge{
    int to, weight;
};
vector<Edge> G[maxn];
int dis[maxn];
bool inq[maxn];
int num_inq[maxn];
int n, k, s;
bool SPFA(){
    for(int i=0; i<maxn; i++) dis[i] = INF;
    memset(inq, 0, sizeof(inq));
    queue<int> q;
    dis[s] = 0;
    q.push(s);
    inq[s] = true;
    num_inq[s]++;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        inq[u] = false;
        for(int i=0; i<G[u].size(); i++){
            int v = G[u][i].to;
            if(dis[v]>dis[u]+G[u][i].weight){
                dis[v] = dis[u]+G[u][i].weight;
                if(!inq[v]){
                    q.push(v);
                    inq[v] = true;
                    num_inq[v]++;
                    if(num_inq[v]>=n) return true;
                }
            }
        }
    }
    return false;
}
int main()
{
    while(~scanf("%d%d%d", &n, &k, &s)){
        for(int i=0; i<maxn; i++)G[i].clear(),inq[i] = false;
        int u, v, weight;
        for(int i=0; i<k ;i++){
            scanf("%d%d%d", &u, &v, &weight);
            Edge temp;
            temp.to = v;
            temp.weight = weight;
            G[u].push_back(temp);
        }
        if(!SPFA()){
            printf("There is no negative loop\n");
            for(int i=0; i<n; i++)printf("%d ", dis[i]);
            printf("\n");
        }
        else printf("There is a negative loop\n");
    }
    return 0;
}

Floyd算法

没有固定起点的最短路问题。时间复杂度是O(\(n^3\)).用的是动态规划的思想，学习一下怎么打印最短路径，之前并不会。
状态转移方程：
\(dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]), k\in(0, n)\).
注意一定要先枚举k!!!!!

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e2+10;
const int INF = 1e9;
int G[maxn][maxn];
int n, m;
int path[maxn][maxn];
void Floyd()
{
    for(int k=0; k<n; k++){
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(G[i][k]!=INF&&G[k][j]!=INF)
                    if(G[i][j]>G[i][k]+G[k][j]){
                        G[i][j] = G[i][k]+G[k][j];
                        path[i][j] = path[k][j];
                    }
            }
        }
    }
}
void print_path(int u, int v){
    int node = path[u][v];
    queue<int> ans;
    ans.push(u);
    if(u!=node) ans.push(node);
    while(node != path[node][v]){
        ans.push(node);
        node = path[node][v];
    }
    ans.push(v);
    while(!ans.empty()){
        ans.front() == v?printf("%d\n", ans.front()):printf("%d-->", ans.front());
        ans.pop();
    }
}
int main()
{
    while(~scanf("%d%d", &n, &m)){
        for(int i=0; i<maxn; i++)
            for(int j=0; j<maxn; j++)
                G[i][j] = INF;
        for(int i=0; i<maxn; i++)G[i][i] = 0;
        int u, v, weight;
        for(int i=0; i<m; i++){
            scanf("%d%d%d", &u, &v, &weight);
            G[u][v] = weight;
        }
        for(int i=0; i<maxn; i++){
            for(int j=0; j<maxn; j++){
                if(G[i][j] != INF)
                    path[i][j] = i;//注意这个保存的是路径的前驱
                else path[i][j] = -1;
            }
        }
        Floyd();
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                printf("%d ",G[i][j]);
            }
            printf("\n");
        }
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                printf("%d ", path[i][j]);
            }
            printf("\n");
        }
        scanf("%d%d", &u, &v);
        print_path(u, v);
    }
    return 0;
}

次短路问题

还是运用的是Dijkstra算法，只不过多了中间的保存的变量。

  • u->v:到v的次算路，要么是u的次短路+dis(u, v)
  • 要么是u的最短路+dis[u][v].

题目

Roadblocks

题意

次短路，双向连通，一条路可以重复经过。

题解

见上面的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 5e3+10;
const int INF = 1e9;
struct Edge{
    int to, weight;
};
vector<Edge> G[maxn];
int dis[maxn];
int dis2[maxn];
int n, m;
typedef pair<int, int> P;
void Dijkstra(){
    priority_queue<P, vector<P>, greater<P> > que;
    fill(dis, dis+n, INF), fill(dis2, dis2+n, INF);
    dis[0] = 0;
    que.push(P(0, 0));
    //pair第一维记录距离，第二维记录序号。
    while(!que.empty()){
        P p = que.top();
        que.pop();
        int u = p.second, distan = p.first;
        //printf("%d %d\n", u, distance);
        if(dis2[u]<distan)continue;
        for(int i=0; i<G[u].size(); i++){
            int v = G[u][i].to;
            int d2 = G[u][i].weight+distan;
            if(dis[v]>d2){
                swap(dis[v], d2);
                //最短路被更新后，该路径有可能是次短路径，因此需要保留。
                que.push(P(dis[v], v));
            }
            if(dis2[v]>d2&&dis[v]<d2){
                dis2[v] = d2;
                que.push(P(dis2[v], v));
            }
        }
    }
    printf("%d\n", dis2[n-1]);
}
int main()
{
    while(~scanf("%d%d", &n, &m)){
        for(int i=0; i<maxn; i++) G[i].clear();
        int u, v, weight;
        for(int i=0; i<m; i++){
            scanf("%d%d%d", &u, &v, &weight);
            Edge temp;
            temp.to = v-1;
            temp.weight = weight;
            G[u-1].push_back(temp);
            temp.to = u-1;
            G[v-1].push_back(temp);
        }
        Dijkstra();
    }
    return 0;
}
非常需要注意的一点：更新的数字不是dis[u]而是p.first.因为入队的元素可能是第二大的，和前面的最短路优化不同！！！

int d2 = G[u][i].weight+distan;

k短路问题

A*的裸题，好好体会一下A*的思想。
具体的代码可以看我之前写的博客，安利一波。

最小生成树

这个问题有两种算法：Prim算法和Kruskal算法，两者的本质都是贪心算法，只不过贪心的策略不同。
稠密图prim算法比较合适，稀疏图kruskal算法比较合适。

prim算法

贪心的策略是将图划分成两个集合，不断的加入最小的边，并且满足已经加入的点不构成环，然后将相关的点加入集合。
其实代码实现的过程和Dijkstra一模一样，只不过dis[]数组的含义变了：该节点到初始集合的最小距离。注意是到一个集合的距离。
而dijkstra中dis[]表示到源点的最短距离。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
using namespace std;
/*
6 10
0 1 4
0 4 1
0 5 2
4 5 3
5 1 3
4 3 4
5 3 5
5 2 5
1 2 6
2 3 6
*/
const int maxn = 1e3+10;
const int INF = 1e9;
bool vis[maxn];
struct Edge{
    int to;
    int weight;
};
vector<Edge> G[maxn];
int n, m;
int dis[maxn];
int Prim(){
    memset(vis, 0, sizeof(vis));
    for(int i=0; i<maxn; i++)dis[i] = INF;
    dis[0] = 0;
    int ans = 0;
    for(int i=0; i<n; i++){
        int u = -1;
        int min_length = INF;
        for(int j=0; j<n; j++){
            if(!vis[j]&&dis[j]<min_length){
                u = j;
                min_length = dis[j];
            }
        }
        vis[u] = true;
        ans += dis[u];
        for(int i=0; i<G[u].size(); i++){
            int v = G[u][i].to;
            if(!vis[v]&&G[u][i].weight<dis[v])
                dis[v] = G[u][i].weight;
        }
    }
    return ans;
}
int main()
{
    while(~scanf("%d%d", &n, &m)){
        for(int i=0; i<maxn; i++)G[i].clear();
        int u, v, weight;
        for(int i=0; i<m; i++){
            scanf("%d%d%d", &u, &v, &weight);
            Edge temp;
            temp.to = v;
            temp.weight = weight;
            G[u].push_back(temp);
            temp.to = u;
            G[v].push_back(temp);
        }
        printf("%d\n", Prim());
    }
    return 0;
}

Kruskal算法

首先将边的权值进行排序，然后不断的将最小的权值加入到最小生成树中。若不构成环，那么结着寻找下面的点。若构成环，那么就跳过这条线，直到构成最小生成树为止。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
struct Edge{
    int u, v, weight;
}edge[maxn*maxn/2+10];
int fa[maxn];
int find(int x){
    int a = x;
    while(x!=fa[x]){
        x = fa[x];
    }
    while(a!=fa[a]){
        int z = a;
        a = fa[a];
        fa[z] = x;
    }
    return x;
}
void union_set(int u, int father){
    int temp = u;
    while(u!=fa[u]){
        u = fa[u];
        fa[temp] = father;
        temp = u;
    }
    fa[u] = father;
}
int n, m;
bool cmp(Edge a, Edge b){
    return a.weight<b.weight;
}
int kruskal(){
    for(int i=0; i<maxn; i++) fa[i] = i;
    int ans = 0;
    int edge_num = 0;
    sort(edge, edge+m, cmp);
    for(int i=0; i<m; i++){
        int u = edge[i].u;
        int v = edge[i].v;
        int fau = find(u);
        int fav = find(v);
        if(fau!=fav){
            union_set(u, fav);
            //printf("%d--%d:%d %d %d\n", u, v, fau, fav, edge[i].weight);
            ans+=edge[i].weight;
            edge_num++;
            if(edge_num == n-1) break;
        }
    }
    if(edge_num == n-1) return ans;
    else return -1;
}
int main()
{
    while(~scanf("%d%d", &n, &m)){
        for(int i=0; i<m; i++){
            int u, v, weight;
            scanf("%d%d%d", &u, &v, &weight);
            edge[i].u = u, edge[i].v = v, edge[i].weight = weight;
        }
        printf("%d\n", kruskal());
    }
    return 0;
}

次小生成树

次小生成树的步骤以及代码：
首先贴上一份很好的url: 次小生成树的步骤及原理
问题在原blog中就已经有了
下面是我对次小生成树的一些个人的总结：

  1. 用prime算法求出最小生成树。
    这个函数中，包含了有个Max[][]的求解。这个数组是什么含义呢？表示的的是（i, j）这两个点间最小生成树中边的最大权值（限制条件：①这个边是在最小生成树中的②权值是一条边的权值，不是一条链的权值（反正当时我们有弄的很清楚））。这个权值有什么用呢？当我们枚举不在最小生成树中的边的时候，我们要删去的是环中的最大边权，这样得到的才可能是次小生成树。因此，Max[][]是这个算法的核心。
  2. 枚举不在最小生成树中的边
  3. 出次小生成树的权值

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 111;
int Max[maxn][maxn];
bool vis[maxn];
bool used[maxn][maxn];
int d[maxn];
int adj[maxn][maxn];
int n, m;
int fa[maxn];
int mst;
bool prim(){
    memset(vis, 0, sizeof(vis));
    memset(used, 0, sizeof(used));
    mst = 0;
    for(int i=2; i<=n; i++){
        d[i] = adj[1][i];
        fa[i] = 1;
    }
    fa[1] = 0;
    d[1] = 0;
    vis[1] = true;
    for(int i=2; i<=n; i++){
        int u = -1;
        int mindis = INF;
        for(int j=1; j<=n; j++){
            if(!vis[j]&&mindis>d[j]){
                u = j;
                mindis = d[j];
            }
        }
        if(mindis == INF||u == -1) return false;
        mst += mindis;
        vis[u] = true;
        used[u][fa[u]] = used[fa[u]][u] = true;
        for(int v=1; v<=n; v++){
            if(vis[v]) Max[u][v] = Max[v][u] = max(d[u], Max[v][fa[u]]);
            if(!vis[v]){
                if(d[v]>adj[u][v]){
                    d[v] = adj[u][v];
                    fa[v] = u;
                }
            }
        }
    }
    return true;
}
bool smst()
{
    int ans = INF;
    for(int i=1; i<=n; i++){
        for(int j=1+i; j<=n; j++){
            if(!used[i][j]&&adj[i][j] != INF){
                ans = min(ans, mst-Max[i][j]+adj[i][j]);
            }
        }
    }
    if(ans == mst) return false;
    return true;
}
void solve(){
    bool flag = prim();
    if(!flag){
        printf("Not Unique!\n");
        return ;
    }
    //cout<<mst<<endl;
    flag = smst();
    if(!flag){
        printf("Not Unique!\n");
        return;
    }
    printf("%d\n", mst);
    return ;
}
int main()
{
    int t;
    scanf("%d", &t);
    while(t--){
        for(int i=0; i<maxn; i++){
            for(int j=0; j<maxn; j++){
                if(i == j) adj[i][j] = 0;
                else adj[i][j] = INF;
            }
        }
        scanf("%d%d", &n, &m);
        for(int i=0; i<m; i++){
            int u, v, weight;
            scanf("%d%d%d", &u, &v, &weight);
            adj[u][v] = weight;
            adj[v][u] = weight;
        }
        solve();
    }
    return 0;
}

拓扑排序(AOV)

主要就是记录一个节点的入度数。若入度为0，那么就加入将要删除的队列。
如果要求最小字典序的拓扑排序，那么可以使用优先队列。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;
int n, k;
const int maxn = 1e3+10;
vector<int> G[maxn];
int indegree[maxn];
bool topo_sort()
{
    queue<int> q;
    for(int i=1; i<n; i++){
        if(indegree[i] == 0) q.push(i);
    }
    int tot = 0;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        printf("%d ", u);
        for(int i=0; i<G[u].size(); i++){
            int v = G[u][i];
            indegree[v]--;
            if(indegree[v] == 0)q.push(v);
        }
        tot++;
    }
    if(tot == n) return true;
    else return false;
}
int main()
{
    while(~scanf("%d%d", &n, &k)){
        for(int i=0; i<maxn; i++) G[i].clear(), indegree[i] = 0;
        int u, v;
        for(int i=0 ;i<k; i++){
            scanf("%d%d", &u, &v);
            G[u].push_back(v);
            indegree[v]++;
        }
        if(!topo_sort())printf("there exists a loop\n");
    }
    return 0;
}

关键路径问题

数据结构的ppt很好的展示了该程序运行的流程。
首先区分几个概念：

  • 事件指的是顶点的序号， ve[]表示事件最早的发生时间，vl[]表示事件最迟的发生时间
  • 弧上的权值表示一个活动，e[]表示活动的最早的发生时间，l[]表示活动的最迟的发生的时间。

算法的流程

  1. 先按照拓扑序来更新\(ve[]\)
  2. 然后倒过来，按照逆拓扑序来更新\(vl[]\).
  3. 通过ve[], vl[]来求活动的e[], l[].
    假设活动\(a_r\)连接了点u, v.那么\(e[r] = ve[u]\), \(l[r] = vl[v]-length_{uv}\)
    若e[r] == l[r], 那么u–v弧就是关键活动。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
int n, m;
struct Edge{
    int to, weight;
};
/*
样例：
9 11
0 1 6
0 2 4
0 3 5
1 4 1
2 4 1
3 5 2
4 6 8
4 7 7
5 7 4
6 8 2
7 8 4
*/
vector<Edge> G[maxn];
int indegree[maxn];
stack<int> toporder;
//表示的是时间的最早的开始时间和最迟的开始时间。
int ve[maxn], vl[maxn];
bool topo_sort(){
    while(!toporder.empty())toporder.pop();
    queue<int> q;
    for(int i=0; i<n; i++){
        if(indegree[i] == 0) q.push(i);
    }
    while(!q.empty()){
        int u = q.front();
        q.pop();
        toporder.push(u);
        for(int i=0; i<G[u].size(); i++){
            int v = G[u][i].to;
            indegree[v]--;
            if(indegree[v] == 0) q.push(v);
            if(ve[u]+G[u][i].weight>ve[v])
                ve[v] = ve[u]+G[u][i].weight;
        }
    }
    if(toporder.size() == n) return true;
    else return false;
}
//以n-1作为结束的点。
int critical_path(){
    memset(ve, 0, sizeof(ve));
    if(topo_sort() == false){
        printf("what happened?\n");
    }
    fill(vl, vl+n, ve[n-1]);
    while(!toporder.empty()){
        int u = toporder.top();
        toporder.pop();
        for(int i=0; i<G[u].size(); i++){
            int v = G[u][i].to;
            if(vl[u]>vl[v]-G[u][i].weight){
                vl[u] = vl[v] - G[u][i].weight;
            }
        }
    }
    for(int u=0; u<n; u++){
        for(int i=0; i<G[u].size(); i++){
            int v = G[u][i].to;
            int weight = G[u][i].weight;
            int e = ve[u], l = vl[v]-weight;
            if(e == l){
                printf("%d-->%d\n", u, v);
            }
        }
    }
    return ve[n-1];
}
int main()
{
    while(~scanf("%d%d", &n ,&m)){
        for(int i=0; i<maxn; i++) G[i].clear();
        for(int i=0; i<maxn; i++) indegree[i] = 0;
        int u, v, weight;
        for(int i=0; i<m; i++){
            scanf("%d%d%d", &u, &v, &weight);
            Edge temp;
            temp.to = v;
            temp.weight = weight;
            G[u].push_back(temp);
            indegree[v]++;
        }
        critical_path();
    }
    return 0;
}

上面的代码是以n-1作为汇点的，若不知道汇点，那么最后求最大值的时候扫一遍就行了。

判断图中是否存在环

判断的方法有很多，只列出老师上课讲过的，其他等慢慢的积累吧qaq。

有向图

  • topological sort.
  • 深度优先搜索，若有回边，那么直接判断有圈，

无向图

  • 若无向连通图中\(e\ge n\).
  • 每个点的度数大于等于2.
  • DFS.

最后想讲的一些话

其实图论相当的有意思，但是最困难的是建模。往往难以正确的转换套用正确的模型，还是得多做题才行吧。

未解决的问题

本文标题:图论的基础算法

文章作者:Babydragon

发布时间:2017-11-24, 12:38:28

最后更新:2018-03-23, 13:33:56

原始链接:http://baolintian.github.io/2017/11/24/图论的基础算法/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 图的存储
  2. 2. 图的遍历
    1. 2.1. DFS遍历
      1. 2.1.1. 代码
    2. 2.2. BFS遍历
      1. 2.2.1. 代码
  3. 3. 最短路算算法
    1. 3.1. Dijkstra算法
      1. 3.1.0.1. 代码
      2. 3.1.0.2. 优化代码
  4. 3.2. Bellman-ford算法
  5. 3.3. SPFA算法
    1. 3.3.1. 代码
  6. 3.4. Floyd算法
    1. 3.4.1. 代码
  • 4. 次短路问题
    1. 4.1. 题目
    2. 4.2. 题意
    3. 4.3. 题解
    4. 4.4. 代码
  • 5. k短路问题
  • 6. 最小生成树
    1. 6.1. prim算法
    2. 6.2. 代码
    3. 6.3. Kruskal算法
    4. 6.4. 代码
  • 7. 次小生成树
    1. 7.1. 代码
  • 8. 拓扑排序(AOV)
    1. 8.1. 代码
  • 9. 关键路径问题
    1. 9.1. 代码
  • 10. 判断图中是否存在环
    1. 10.1. 有向图
    2. 10.2. 无向图
  • 11. 最后想讲的一些话
  • 12. 未解决的问题
    • {{ live2d() }}