图论入门

概念

  1. 有向图
  2. 无向图
  3. 入度出度
  4. 节点
  5. 边权
  6. 路径
  7. 圈/环

存储

  1. 邻接矩阵
  2. 邻接表
  • vector存图

    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
     #include <vector>
    using namespace std; //个人习惯

    sreuct Edge {
    int from, to, dist;
    Edge() {}
    Edge(int _from, int _to, int _dist): from(_from), to(_to), dist(_dist) {}
    };

    vector<Edge> g[MAXN];

    void insert(int u, int v, in w) { //双向边带权值w
    g[u].push_back(Edge(u, v, w));
    g[v].push_back(Edge(v, u, w));
    }

    int now;//枚举点now的出边

    //不推荐的写法,完全没有使用STL特性
    for (int i = 0; i < g[now].size(); i++) {
    Edge &e = g[now][i];
    printf("%d\n", e.to);
    }
    //推荐的写法
    for (vector<Edge>::iterator it = g[now].begin(); it != g[now].end(); it++) {
    printf("%d\n", it->to);
    }
    //C++11
    for (auto &e : g[now]) {
    printf("%d\n", e.to);
    }
    • 链式前向星
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
struct Edge {
int from, to, dist;
Edge() {}
Edge(int _from, int _to, int _dist): from(_from), to(_to), dist(_dist) {}
};

Edge ed[MAXM];
int he[MAXN], ne[MAXM], etop = 1;
//边编号从1开始,0代表没有下一条边,对应链表的NULL
//he[i]代表点i边集中的第一条边编号,对应链表的head指针
//ne[i]代表边i的下一条边编号,对应链表中的next指针
//ed[i]代表边i的信息

void insert(int u, int v, int w) { //单向边带权值w
ed[etop] = Edge(u, v, w);
ne[etop] = he[u];
he[u] = etop++;
//单向链表从头部插入元素
}

int now;
for (int i = he[now]; i; i = ne[i]) {
Edge &e = ed[i];
printf("%d\n", e.to);
}

INF 未连通的边,把边权视为无限大

  • -1:非负权值使用
  • 0x7fffffff : 理论非常大,但相加会溢出
  • 0x3fffffff : 相加不会溢出
  • 0x3f3f3f3f : 常用,不溢出,可用memset();

拓扑排序

遍历节点时,有一个特殊的遍历顺序。对DAG(有向无环图)进行特殊的遍历:寻找DAG上的最长链。

  1. 建图时记录入度
  2. 把没有入度的每一个点放进队列里
  3. 队头出
  4. 出队点相连的点入度–
  5. 回到步骤2,直到所有点都遍历完

最小生成树

  • Prim

适用于稠密图,时间复杂度 O(n2)O(n2)。

核心思想:每次挑一条与当前集合相连的最短边。

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
// st[i] 表示点i是否在当前生成树集合中
// dist[i] 表示点i到当前集合的最短边的长度
// gi 表示点i和点j之间边的长度
// 返回值:最小生成树中所有边的总长度
int Prim()
{
int res = 0;
for (int i = 1; i <= n; i ++ )
{
dist[i] = INF;
st[i] = false;
}
dist[1] = 0;
for (int i = 1; i <= n; i ++ )
{
int id = -1, min_dist = INF;
// 寻找最短边
for (int j = 1; j <= n; j ++ )
if (!st[j] && dist[j] < min_dist)
{
id = j;
min_dist = dist[j];
}
st[id] = true;
res += dist[id];
// 用新加入的点更新其余点到生成树的最短边
for (int j = 1; j <= n; j ++ )
if (!st[j])
dist[j] = min(dist[j], gid);
}
return res;
}
  • 克鲁斯卡尔

适用于稀疏图,时间复杂度 O(mlogm)O(mlogm)。

核心思想:从小到大挑不多余的边。

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
// 边的信息
struct Edge
{
int a, b, v;
bool operator< (const Edge &W) const
{
return v < W.v;
}
};

// 并查集——寻找当前集合的代表元素
int find(int x)
{
if (father[x] != x) father[x] = find(father[x]);
return father[x];
}

// 所有边存储在 Edge edges[M];
// 函数返回最小生成树中所有边的总长度
int Kruskal()
{
int res = 0;
// 初始化并查集代表元素
for (int i = 1; i <= n; i ++ ) father[i] = i;
sort(edge, edge + m);
for (int i = 0; i < m; i ++ )
{
int a = edge[i].a, b = edge[i].b;
if (find(a) != find(b))
{
res += edge[i].v;
father[find(a)] = find(b);
}
}
return res;
}

最短路

  • Floyd算法:
    • 多源最短路,求出所有点对的最短路长度
    • 时间复杂度:0($n^3$)
  • Dijkstra算法:
    • 单源最短路,求出某个点s到所有点的最短路长度
    • 时间复杂度:$0(n^2)$/$0(mlogn)$
    • 无法处理负权
  • SPFA算法,即队列优化的Be11man-Ford算法
    • 单源最短路,求出某个点s到所有点的最短路长度
    • 时间复杂度:声称为0(m),最坏0(nm),容易卡到最坏
    • 可以处理负权边,可以判断负权环

Floyd算法:

本质就是DP。

  • 设d[i][j][k]为从i到j,仅通过编号为1-k的中间节点的最短路径距离
  • $d[i][j][k]=min(d[i][j][k-1],d[i][k][k-1]+d[k][j][k-1])$
  • 初始值d[i][j][e]为两点之间边权值,未连通为INF
  • 从1到n枚举k,然后枚举(i,j)
  • 为了方便可以不开第三维,在原地迭代
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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 1010, M = 2000010, INF = 1000000000;

int n, m;
int d[N][N];

int main()
{
cin >> m >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
d[i][j] = i == j ? 0 : INF;
for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
d[a][b] = d[b][a] = min(c, d[a][b]);
}
// floyd 算法核心
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
cout << d[1][n] << endl;
return 0;
}

Dijkstra算法:

$O(n^2)$做法,不优化版本:

最裸的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
46
47
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010, M = 2000010, INF = 1000000000;

int n, m;
int g[N][N], dist[N];
bool st[N];

void dijkstra()
{
for (int i = 1; i <= n; i++) dist[i] = INF;
dist[1] = 0;
for (int i = 0; i < n; i++)
{
int id, mind = INF;
for (int j = 1; j <= n; j++)
if (!st[j] && dist[j] < mind)
{
mind = dist[j];
id = j;
}
st[id] = 1;
for (int j = 1; j <= n; j++) dist[j] = min(dist[j], dist[id] + g[id][j]);
}
}

int main()
{
cin >> m >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
g[i][j] = INF;
for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
g[a][b] = g[b][a] = min(g[a][b], c);
}
dijkstra();
cout << dist[n] << endl;
return 0;
}
dijkstra+heap优化 $O(mlogn)$

用堆维护所有点到起点的距离。时间复杂度是 O(mlogn)。
这里我们可以手写堆,可以支持对堆中元素的修改操作,堆中元素个数不会超过 n。也可以直接使用STL中的priority_queue,但不能支持对堆中元素的修改,不过我们可以将所有修改过的点直接插入堆中,堆中会有重复元素,但堆中元素总数不会大于 m。
只能处理边权为正数的问题。
图用邻接表存储。

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <functional>

using namespace std;

const int N = 1010, M = 2000010, INF = 1000000000;

int n, m;
int dist[N];
int h[N], e[M], v[M], ne[M], idx;

void add(int a, int b, int c)
{
e[idx] = b, v[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void dijkstra_heap()
{
priority_queue < pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;
for (int i = 1; i <= n; i++) dist[i] = INF;
dist[1] = 0;
heap.push(make_pair(dist[1], 1));
while (heap.size())
{
pair<int, int> t = heap.top();
heap.pop();
if (t.first > dist[t.second]) continue;
for (int i = h[t.second]; i != -1; i = ne[i])
if (dist[e[i]] > t.first + v[i])
{
dist[e[i]] = t.first + v[i];
heap.push(make_pair(dist[e[i]], e[i]));
}
}
}

int main()
{
memset(h, -1, sizeof h);
cin >> m >> n;
for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
add(b, a, c);
}
dijkstra_heap();
cout << dist[n] << endl;
return 0;
}

SPFA算法:

bellman-ford算法的优化版本,可以处理存在负边权的最短路问题。
最坏情况下的时间复杂度是 O(nm),但实践证明spfa算法的运行效率非常高,期望运行时间是 O(km),其中 k 是常数。
但需要注意的是,在网格图中,spfa算法的效率比较低,如果边权为正,则尽量使用 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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 1010, M = 2000010, INF = 1000000000;

int n, m;
int dist[N], q[N];
int h[N], e[M], v[M], ne[M], idx;
bool st[N];

void add(int a, int b, int c)
{
e[idx] = b, v[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void spfa()
{
int hh = 0, tt = 0;
for (int i = 1; i <= n; i++) dist[i] = INF;
dist[1] = 0;
q[tt++] = 1, st[1] = 1;
while (hh != tt)
{
int t = q[hh++];
st[t] = 0;
if (hh == n) hh = 0;
for (int i = h[t]; i != -1; i = ne[i])
if (dist[e[i]] > dist[t] + v[i])
{
dist[e[i]] = dist[t] + v[i];
if (!st[e[i]])
{
st[e[i]] = 1;
q[tt++] = e[i];
if (tt == n) tt = 0;
}
}
}
}

int main()
{
memset(h, -1, sizeof h);
cin >> m >> n;
for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
add(b, a, c);
}
spfa();
cout << dist[n] << endl;
return 0;
}
本站文章除注明转载外均为原创,未经允许不要转载哇. ヾ(゚ー゚ヾ) http://chicago01.top/2019/01/29/图论入门/index.html
Compartir