搜索与图论

树和图的存储

树是一种特殊的图，与图的存储方式相同。 对于无向图中的边ab，存储两条有向边a->b, b->a。 因此我们可以只考虑有向图的存储。

  1. 邻接矩阵：g[a][b] 存储边a->b

  2. 邻接表 (前向星)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const int N = 1e5+10;
struct Node
{
    int to, ne, w;
    
}node[N*2];

int head[N], idx;

// 添加一条边 a -w-> b
void addEdge(int a, int b, int w){
    node[idx].to = b;
    node[idx].ne = head[a];
    node[idx].w = w;
    head[a] = idx++;
}

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

树与图的遍历

时间复杂度 O(n+m) n 表示点数， m表示边数

深度优先遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
int vis[N]; // 存储访问情况

void dfs(int root){
    vis[root] = true;

    for(int i = head[root]; i!=-1; i = node[i].ne){
        int j = node[i].to;
        if(!vis[j]) dfs(j);
        
        // 具体逻辑
    }
}

广度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
queue<int> que;
vis[1] = true; // 表示1号点已经被遍历过
q.push(1);

while (que.size()){
    int cur = que.front();
    que.pop();

    for (int i = head[cur]; i != -1; i = node[i].ne){
        int j = node[i].to;
        if (!vis[j]){
            vis[j] = true; // 表示点j已经被遍历过
            que.push(j);
        }
        
    }
}

拓扑排序

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
queue<int> que;
// d[i] 存储节点i的入度
for(int i=0;i<n; i++) 
    if(d[i] == 0) que.push(i);

while(!que.empty()){
    int cur = que.front();
    que.pop();
    
    for(int i = head[cur]; i != -1; i = node[i].ne){
        int j = node[i].to;
        if(-- d[j] == 0) que.push(j);
    }
}

最短路径

Dijkstra求最短路径

单源最短路径

时间复杂度 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
31
32
33
34
35
36
37
38
39
40
typedef pair<int, int> PII;

// 链式前向星
struct Node{
    int to, ne, w;
}node[N];
int head[N], idx;

// 表示距离以及是否确定最短距离
int dis[N], vis[N];

int dijkstra(int a, int b){
 
    memset(dis, 0x3f, sizeof(dis));
    dis[a] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, a});

    while(heap.size()){
        auto t = heap.top(); heap.pop();
        int cur = t.second;
        
        if(vis[cur]) continue;
        vis[cur] = 1;

        for(int i = head[cur]; i!=-1; i=node[i].ne){
            int j = node[i].to;
            if(dis[j] > dis[cur] + node[i].w){
                dis[j] = dis[cur] + node[i].w;
                heap.push({dis[j], j});
            }
        }
    }


    if(dis[b] == 0x3f3f3f3f) return -1;
    return dis[b];
}


Bellman-Ford算法

时间复杂度 O(nm), n表示点数，m表示边数

Spfa 算法（队列优化的Bellman-Ford算法）

时间复杂度 平均情况下 O(m)，最坏情况下 O(nm), n表示点数，m表示边数

Spfa判断图中是否存在负环

时间复杂度是 O(nm), n表示点数，m表示边数

Floyd算法

多元最短路径

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

1
2
3
4
5
6
7
8
9
10
11
12
13
// 初始化邻接矩阵每条边权为无穷大
for (int i = 1; i <= n; i ++ )
    for (int j = 1; 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 = 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]);
}

最小生成树

Prim算法

最小生成树，类似Dijkstra算法

堆优化版本，时间复杂度是 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
31
32
33
34
35
//.. 前向星 node[M], head[N], idx;
int dis[N], vis[N];
int n, m;

// 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim(){
    memset(dis, 0x3f, sizeof(dis));
    
    int sum = 0, cnt = 0;
    priority_queue<pll, vector<pll>, greater<pll>> heap;
    dis[1] = 0;
    heap.push({0, 1});

    while(!heap.empty()){
        auto cur = heap.top(); heap.pop();

        int distance = cur.first, a = cur.second;
        if(vis[a]) continue;
        vis[a] = 1;
        sum += distance; cnt++;
        
        for(int i = head[a]; i!=-1; i = node[i].ne){
            int b = node[i].to;
            
            if(!vis[b] && dis[b] > node[i].w){
                dis[b] = node[i].w;
                heap.push({dis[b], b});
            }
        }
    }

    if(cnt != n) return INF;
    else return sum;
}

Kruskal算法

时间复杂度是 O(mlogm), 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
34
35
36
37
int n, m;       // n是点数，m是边数
int p[N];       // 并查集的父节点数组

struct Edge{     // 存储边
    int a, b, w;

    bool operator<(const Edge &e) const{
        return w < e.w;
    }
} edges[M];

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

int kruskal(){
    sort(edges, edges + m);

    for (int i = 1; i <= n; i ++ ) p[i] = i;    // 初始化并查集

    int res = 0, cnt = 0;
    for (int i = 0; i < m; i ++ ){
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;

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

    if (cnt < n - 1) return INF;
    return res;
}

二分图

染色法

匈牙利算法