本文作者:yxc

来源: AcWing

原文地址:https://www.acwing.com/blog/content/405/

常用算法模板——搜索与图论

树与图的存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// (1) 邻接矩阵:
// 存储边 a->b
g [a][b]

// (2) 邻接表:
// 对于每个点k,开一个单链表,存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;

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

// 初始化
idx = 0;
memset(h, -1, sizeof h);

树与图的遍历

(1) 深度优先遍历

1
2
3
4
5
6
7
8
9
10
int n, G[1000][1000];
bool vis[1000] = {false};

void dfs(int u) {
vis[u] = true; // vis[u] 表示点u已经被遍历过
// 对 u 的一些操作
for (int v = 0; v < n; v++) {
if (vis[v] == false && G[u][v] != INF) dfs(v);
}
}

(2) 广度优先遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int n, G[1000][1000];
bool vis[1000] = {false};

void bfs(int u) {
queue<int> q;
q.push(u); //将初始结点u入队
vis[u] = true; // 标记为访问

while (!q.empty()) {
int u = q.front(); // 取出队首元素
q.pop(); // 队首元素出队
for (int v = 0; v < n; v++) {
if (vis[v] == false && G[u][v] != INF) { // 未入队的结点全部入队
vis[v] = true; // 标记为访问
q.push(v);
}
}
}
}

拓扑排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> G[1000];  //邻接表
int n, inDegree[1000];

bool toposort() {
int num = 0; // 记录加入拓扑序列的顶点数
queue<int> q;
for (int i = 0; i < n; i++)
if (inDegree[i] == 0) q.push(i); // 将入度为0的顶点入队
while (!q.empty()) {
int u = q.front(); // 取出队首元素
q.pop(); // 队首元素出队
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i]; // u的后继v
inDegree[v]--; // v的入度减1
if (inDegree[v] == 0) q.push(v); // 入度为0则入队
}
num++; // 加入拓扑排序
}
return num == n;
}

朴素 dijkstra 算法

时间复杂度 O(n2+m)O(n^2+m), n 表示点数,m 表示边数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int n, G[1000][1000];
int d[1000]; // 起点到各点的距离
bool vis[1000] = {false};
const int INF = 0x3fffffff;

void Dijlstra(int s) { // s为起点
fill(d, d + 1000, INF);
d[s] = 0; // 起点到自身的距离为0
for (int i = 0; i < n; i++) { // 循环n次
int u = -1; // 寻找距离最小的点
for (int j = 0; j < n; j++) {
if (vis[j] == false && (u == -1 || d[u] > d[j]))
u = j;
}
vis[u] = true;
for (int v = 0; v < n; v++)
d[v] = min(d[v], d[u] + G[u][v]); // 以u为中介点
}
}

堆优化版 dijkstra

时间复杂度 O(mlogn)O(mlogn), n 表示点数,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
typedef pair<int, int> PII;
struct Node {
int v, dis;
};
vector<Node> G[1000]; //邻接表
int n, d[1000];
bool vis[1000] = {false};
const int INF = 0x3fffffff;

void Dijlstra(int s) { // s为起点
fill(d, d + 1000, INF);
d[s] = 0; // 起点到自身的距离为0
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, s}); // first存储距离,second存储节点编号

while (!heap.empty()) {
auto t = heap.top(); // 取堆顶元素
heap.pop();
int pos = t.second, dist = t.first;
if (vis[pos] == true) continue;
vis[pos] = true; // 标记为访问
for (int i = 0; i < G[pos].size(); i++) { // 遍历pos的邻接元素
int v = G[pos][i].v; // 邻接的顶点编号
if (d[v] > dist + G[pos][i].dis) {
d[v] = dist + G[pos][i].dis;
heap.push({d[v], v}); // 入堆
}
}
}
}

Bellman-Ford 算法

时间复杂度 O(nm)O(nm), n 表示点数,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
struct Node {
int v, dis;
};
vector<Node> G[1000]; //邻接表
int n, d[1000];
const int INF = 0x3fffffff;

bool Bellman(int s) { // s为起点
fill(d, d + 1000, INF);
d[s] = 0; // 起点到自身的距离为0
for (int i = 0; i < n - 1; i++) { // 执行n-1轮操作
for (int u = 0; u < n; u++) { // 每次操作遍历所有边
for (int j = 0; j < G[u].size(); j++) {
int v = G[u][j].v; // 邻接边序号
int dis = G[u][j].dis; //邻接边权
if (d[v] > dis + d[u]) {
d[v] = dis + d[u];
}
}
}
}
// 判断负环
for (int u = 0; u < n; u++) { // 对所有边进行判断
for (int j = 0; j < G[u].size(); j++) {
int v = G[u][j].v; // 邻接边序号
int dis = G[u][j].dis; //邻接边权
if (d[v] > dis + d[u]) {
return false;
}
}
}
return true;
}

spfa 算法

时间复杂度 平均情况下 O(m)O(m),最坏情况下 O(nm)O(nm), n 表示点数,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
struct Node {
int v, dis;
};
vector<Node> G[1000]; //邻接表
int n, d[1000];
bool inq[1000] = {false}; // 顶点是否在队列中
const int INF = 0x3fffffff;

void spfa(int s) { // s为起点
fill(d, d + 1000, INF);
queue<int> q;
q.push(s);
inq[s] = true;
d[s] = 0; // 起点到自身的距离为0

while (!q.empty()) {
int u = q.front(); // 取队首元素
q.pop(); // 出队
inq[u] = false; // u不在队列中
for (int j = 0; j < G[u].size(); j++) {
int v = G[u][j].v; // 邻接边序号
int dis = G[u][j].dis; //邻接边权
if (d[v] > dis + d[u]) {
d[v] = dis + d[u];
if (!inq[v]) { // 如果v不在队列中
q.push(v);
inq[v] = true;
}
}
}
}
}

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
struct Node {
int v, dis;
};
vector<Node> G[1000]; //邻接表
int n, d[1000], num[1000] = {0}; // num记录顶点入队次数
bool inq[1000] = {false}; // 顶点是否在队列中
const int INF = 0x3fffffff;

bool spfa(int s) { // s为起点
fill(d, d + 1000, INF);
queue<int> q;
q.push(s);
inq[s] = true;
num[s]++;
d[s] = 0; // 起点到自身的距离为0

while (!q.empty()) {
int u = q.front(); // 取队首元素
q.pop(); // 出队
inq[u] = false; // u不在队列中
for (int j = 0; j < G[u].size(); j++) {
int v = G[u][j].v; // 邻接边序号
int dis = G[u][j].dis; //邻接边权
if (d[v] > dis + d[u]) {
d[v] = dis + d[u];
if (!inq[v]) { // 如果v不在队列中
q.push(v);
inq[v] = true;
num[v]++;
if (num[v] >= n) return false;
}
}
}
}
return true;
}

floyd 算法

时间复杂度是 O(n3)O(n^3), n 表示点数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 初始化:
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (i == j)
d[i][j] = 0;
else
d[i][j] = INF;

// d[a][b]表示a到b的最短距离
void floyd() {
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}

朴素版 prim 算法

时间复杂度是 O(n2+m)O(n^2+m), n 表示点数,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
int n, G[1000][1000];
int d[1000]; // 起点到各点的距离
bool vis[1000] = {false};
const int INF = 0x3fffffff;

int prim() { // 默认0号点为初始点
fill(d, d + 1000, INF);
d[0] = 0; // 起点到自身的距离为0
int ans = 0; // 最小生成树边权之和
for (int i = 0; i < n; i++) { // 循环n次
int u = -1, MIN = INF; // 寻找距离最小的点
for (int j = 0; j < n; j++) {
if (vis[j] == false && d[j] < MIN) {
u = j;
MIN = d[j];
}
}
if (u == -1) return -1; // 找不到说明其他点与起点不连通
vis[u] = true;
ans += d[u]; // 加入距离最小的边
for (int v = 0; v < n; v++) {
if (vis[v] == false) {
d[v] = min(d[v], G[u][v]); // 以u为中介点
}
}
}
return ans;
}

Kruskal 算法

时间复杂度是 O(mlogm)O(m \log m), n 表示点数,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
int n, m;  // n 表示点数,m 表示边数
int father[1000];
const int INF = 0x3fffffff;
struct edge {
int u, v; // 边序号
int cost; // 边权
} E[1000];
bool cmp(edge a, edge b) { return a.cost < b.cost; }
int findFather(int x) { // 并查集核心操作
if (father[x] != x) father[x] = findFather(father[x]);
return father[x];
}

int Kruskal() {
int ans = 0, num = 0; // ans为边权和,num为生成树边数
for (int i = 0; i < n; i++) father[i] = i; // 并查集初始化
sort(E, E + m, cmp); // 按边权从小到大排序
for (int i = 0; i < m; i++) { //枚举所有边
int u = findFather(E[i].u);
int v = findFather(E[i].v);
if (u != v) { //如果不在一个集合
father[u] = v; //合并
ans += E[i].cost;
num++;
if (num == n - 1) break;
}
}
if (num != n - 1) return -1;
return ans;
}

染色法判别二分图

时间复杂度是 O(n+m)O(n + m), n 表示点数,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
int n;                  // n表示点数
vector<vector<int>> G; // 邻接表
int color[n]; // 表示每个点的颜色,-1表示未染色,0表示白色,1表示黑色
bool dfs(int u, int c) {
// u表示当前节点,c表示当前点的颜色
color[u] = c;
// 遍历u的邻接节点
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
// 如果相邻节点未染色
if (color[v] == -1) {
// 将相邻的点染成相反的颜色
if (!dfs(v, !c)) return false;
} else if (color[v] == c)
//结点v已经着色,且和结点u颜色冲突
return false;
}
return true;
}
bool check() {
memset(color, -1, sizeof(color));
bool flag = true;
for (int i = 0; i < n; i++)
// 如果当前节点未染色
if (color[i] == -1)
if (!dfs(i, 0)) {
flag = false;
break;
}
return flag;
}

相关内容