图论模板

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
package searchandgraph

/*
树是一种特殊的图,与图的存储方式相同
对于无向图中的边ab,存储两条有向边a->b,b->a,因此可以只考虑有向图的存储
1.邻接矩阵:g[a][b]存储边a->b
2、邻接表:如下
*/

// 对于每个点k,开一个单链表,存储k所有可以走到的点。h[k]存储这个单链表的头节点.n表示点数,m表示边数
var (
h []int
e []int
ne []int
idx int
n, m int
)

// 初始化
func init() {
idx = 0
for i := 1; i <= n; i++ {
h[i] = -1
}
}

// 添加一条边a->b
func Add(a, b int) {
e[idx] = b
ne[idx] = h[a]
h[a] = idx
idx++
}

2.树与图的遍历

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
package searchandgraph

// st[u]表示点u是否被遍历
var st []bool

// 深度优先遍历
func dfs(u int) {
st[u] = true
for i := h[u]; i != -1; i = ne[i] {
j := e[i]
if !st[j] {
dfs(j)
}
}
}

// BFS初始化
func init() {
st[1] = true
push(1)
}

// 宽度优先遍历
func bfs(u int) {
t := front()
pop()

for i := h[t]; i != -1; i = ne[i] {
j := e[i]
if !st[j] {
st[j] = true
push(j)
}
}
}

var (
q []int
hh int
tt int = -1
)

func push(x int) {
tt++
q[tt] = x
}

func pop() {
hh++
}

func front() int {
return q[hh]
}

func empty() bool {
return tt < hh
}

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
package searchandgraph

/*
d 表示点的入度
*/

var d []int

// 判断有向图是否存在拓扑序列
func TopSort() bool {
// 队列清空
hh, tt = 0, -1

// 入度为0的点入队
for i := 1; i <= n; i++ {
if d[i] == 0 {
push(i)
}
}

for !empty() {
t := front()
pop()

// 遍历入度为0的点能到的边
for i := h[t]; i != -1; i = ne[i] {
j := e[i]

// 遍历过的边去掉
d[j]--
if d[j] == 0 {
push(j)
}
}
}

// 如果所有点都入队了,说明存在拓扑序列,否则不存在拓扑序列
return tt == n-1
}

4.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
package searchandgraph

/*
求1号点到n号点的最短距离
g 存储每条边
dist 存储1号点到每个点的最短距离
st 存储每个点的最短距离是否已经确定
*/

var (
g [][]int
dist []int
// st []bool
)

const INF = 0x3f3f3f3f

// 朴素版求一号点到n号点的最短距离,如不存在则返回-1
func Dijkstra() int {
for i := 1; i <= n; i++ {
dist[i] = INF
}

// 1号点的最短距离为0,最短距离已经确认
dist[1] = 0

// 确定剩下的n-1个点,每次循环确定一个点
for i := 0; i < n-1; i++ {
t := -1
for j := 1; j <= n; j++ {
if !st[j] && (t == -1 || dist[t] < dist[j]) {
t = j
}
}

st[t] = true
for j := 1; j <= n; j++ {
dist[j] = min(dist[j], dist[t]+g[t][j])
}
}
if dist[n] > INF/2 {
return -1
}
return dist[n]
}

5.bellman-ford算法

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
package searchandgraph

// 存储a->b的边,权重为w
type edge struct {
a, b, w int
}

var k int

// last存储dist的上一次的结果
var last []int

// edges存储所有的边
var edges []edge

// 求1号点到n号点最多经过k条边的最短路距离,如果不存在,则返回-1
func Bellman_Ford() int {
for i := 1; i <= n; i++ {
dist[i] = INF
}

dist[1] = 0

// 遍历k次,表示最多经过k条边
for i := 0; i < k; i++ {
copy(last, dist)
for j := 0; j < m; j++ {
e := edges[j]
dist[e.b] = min(dist[e.b], dist[e.a]+e.w)
}
}

if dist[n] > INF/2 {
return -1
}
return dist[n]
}

6.spfa算法

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
package searchandgraph

// 邻接表存储每条边a->b,w存储ab边的权重
var w []int

// 边的存储
func Add_1(a, b, wi int) {
e[idx] = b
w[idx] = wi
ne[idx] = h[a]
h[a] = idx
idx++
}

// 队列优化的bellman-Ford算法
func spfa() int {
for i := 1; i <= n; i++ {
dist[i] = INF
}
dist[1] = 0

push(1)
st[1] = true

for !empty() {
t := front()
pop()

st[t] = false
for i := h[t]; i != -1; i = ne[i] {
j := e[i]
if dist[j] > dist[t]+w[i] {
dist[j] = dist[t] + w[i]
if !st[j] {
push(j)
st[j] = true
}
}
}
}

if dist[n] > INF/2 {
return -1
}
return dist[n]
}

// cnt[x] 存储1到x的最短路中经过的点数
var cnt []int

// spfa算法判断图中是否有负环
func spfa_cycle() bool {
for i := 1; i <= n; i++ {
push(i)
st[i] = true
}

for !empty() {
t := front()
pop()

st[t] = false
for i := h[t]; i != -1; i = ne[i] {
j := e[i]
if dist[j] > dist[t]+w[i] {
dist[j] = dist[t] + w[i]
cnt[j] = cnt[t] + 1
if cnt[j] >= n {
return true
}

if !st[j] {
push(j)
st[j] = true
}
}
}
}
return false
}

7.Floyd算法

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
package searchandgraph

/*
floyd算法求任意两个点的最短路距离

distance[a][b] 表示a到b的最短距离
*/

var distance [][]int

// 初始化
func init() {
for i := 1; i <= n; i++ {
for j := 1; j <= n; j++ {
if i == j {
distance[i][j] = 0
} else {
distance[i][j] = INF
}
}
}
}

// 计算完之后,distance[a][b]就是a到b的最短距离
func floyd() {
for k := 1; k <= n; k++ {
for i := 1; i <= n; i++ {
for j := 1; j <= n; j++ {
distance[i][j] = min(distance[i][j], distance[i][k]+distance[k][j])
}
}
}
}

8.prim算法

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
package searchandgraph

/*
g 邻接矩阵,存储所有边
dist 存储其他点到最小生成树的距离
st 存储每个点是否已经在最小生成树中
*/

// 如果图不连通,返回INF,否则返回最小生成树的树边权重之和
func Prim() int {
for i := 1; i <= n; i++ {
dist[i] = INF
}

res := 0
dist[1] = 0
for i := 1; i <= n; i++ {
t := -1
for j := 1; j <= n; j++ {
if !st[j] && (t == -1 || dist[j] < dist[t]) {
t = j
}
st[t] = true
if dist[t] > INF/2 {
return -1
}
res += dist[t]
for k := 1; k <= n; k++ {
if !st[k] {
dist[k] = min(dist[k], g[t][k])
}
}
}
}
return res
}

9.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
package searchandgraph

import "sort"

/*
p 存储并查集的父节点数组
*/

var p []int

// 并查集的核心操作
func find(x int) int {
if x != p[x] {
p[x] = find(p[x])
}
return p[x]
}

// 如果图不连通,返回INF,否则返回最小生成树的树边权重之和
func kruskal() int {
// 按照权重从小到大给边排序
sort.Slice(edges, func(i, j int) bool {
return edges[i].w < edges[j].w
})

// 初始化并查集
for i := 1; i <= n; i++ {
p[i] = i
}

var res, cnt int
// 遍历所有的边
for i := 0; i < m; i++ {
a, b, w := edges[i].a, edges[i].b, edges[i].w

a, b = find(a), find(b)
// 如果a,b两个块不连通,则将两个块联通
if a != b {
p[a] = b
res += w
cnt++
}
}

if cnt < n-1 {
return INF
}

return res
}

10.染色法判定二分图

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
package searchandgraph

/*
染色法判定二分图
邻接表存储图
color 存储每个点的颜色,0表示未染色,1表示白色,2表示黑色
*/

var color []int

// 参数:u表示当前点,c表示当前点的颜色
func dfs_1(u, c int) bool {
color[u] = c

for i := h[u]; i != -1; i = ne[i] {
j := e[i]
if color[j] == 0 {
if !dfs_1(j, 3-c) {
return false
}
} else if color[j] == c {
return false
}
}
return true
}

11.匈牙利算法

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
package searchandgraph

/*
求二分图的最大匹配
n1,n2 n1表示第一个集合中的点数,n2表示第二个集合中的点数
match 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个
st 表示第二个集合中的每个点是否已经被遍历过
*/

var match []int
var n1, n2 int

func find_1(x int) bool {
for i := h[x]; i != -1; i = ne[i] {
j := e[i]

if !st[j] {
st[j] = true
if match[j] == 0 || find_1(j) {
match[j] = i
return true
}
}
}
return false
}

// 求最大匹配数,依次枚举第一个集合中的每个点能否匹配第二个集合中的点
func hungarian() int {
res := 0
for i := 1; i <= n1; i++ {
for j := 1; j <= n2; j++ {
st[j] = false
}
if find_1(i) {
res++
}
}

return res
}