基础图论与搜索

字数统计: 4.7k字   |   阅读时长≈ 21分钟

Acwing算法基础课的搜索与图论内容

1.DFS

深度优先搜索，可以用一个栈模拟，但是更多时候还是用系统函数栈来写递归比较简单。

DFS的关键是要自己想出来递归搜索树，这棵树想出来了就好写了

DFS的算法步骤就是递归搜索树的执行顺序，模板化一点就是

  • 判断根节点
  • 遍历子节点，看看能不能继续递归下去

时间复杂度是$O(N)$

下面分别是求出一个数字的全排列的递归写法和迭代写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void dfs(int u)
{
    if(u == n)
    {
        for(int i = 0; i < n; i ++ ) cout << p[i] << ' ';
        cout << endl;
        return;
    }
    for(int i = 1; i <= n; i ++ )
    {
        if(!st[i])
        {
            st[i] = true;
            p[u] = i;
            dfs(u + 1);
            st[i] = false;
        }
    }
}
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
void dfs()
{
    stack<string> s;
    s.push("");
    while(s.size())
    {
        auto t = s.top();
        s.pop();
        if(t.size() == n)
        {
            for(auto c : t) cout << c << ' ';
            cout << endl;
            continue;
        }
        for(int i = n; i >= 1; i -- )
        {
            if(t.find(i + '0') == -1)
            {
                string u = t;
                u += i + '0';
                s.push(u);
            }
        }
    }
}

八皇后问题的两种搜索方式，

第一种：按照每一行搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void dfs(int u)
{
    if(u == n)
    {
        for(int i = 0; i < n; i ++ ) puts(g[i]);
        puts("");
    }
    for(int i = 0; i < n; i ++ )
    {
        if(!col[i] && !dg[i + u] && !udg[i - u + n])
        {
            g[u][i] = 'Q';
            col[i] = dg[i + u] = udg[i - u + n] = 1;
            dfs(u + 1);
            col[i] = dg[i + u] = udg[i - u + n] = 0;
            g[u][i] = '.';
        }
    }
}

第二种，按照每一个格子搜索:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void dfs(int x, int y, int s)
{
    if(y == n) y = 0, x ++ ;
    if(x == n)
    {
        if(s == n)
        {
            for(int i = 0; i < n; i ++ ) puts(g[i]);
            puts("");
        }
        return;
    }
    dfs(x, y + 1, s);
    if(!col[y] && !row[x] && !dg[x + y] && !udg[ x- y + n])
    {
        col[y] = row[x] = dg[x + y] = udg[x - y + n] = 1;
        g[x][y] = 'Q';
        dfs(x, y + 1, s + 1);
        col[y] = row[x] = dg[x + y] = udg[x - y + n] = 0;
        g[x][y] = '.';
    }
}

2. BFS

广度优先搜索，需要使用一个队列来实现，可以求解权重相等的图的最短路。

BFS的算法步骤是：

  • 初始化起点距离为0，其他点的距离为-1
  • 定义一个队列，将起点入队列
  • 队列不空时：
    • 弹出队首
    • 遍历队首的邻边，如果没有到达过就更新这个点，如果被搜过了就不要搜了
    • 将搜到的新点加入到队列中

上面这样遍历，能保证队列中的点是按照层级依次排序的，所以能够求最短路

算法的时间复杂度为$O(N)$

以走迷宫为例，写一个BFS的模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int bfs()
{
    queue<PII> q;
    q.push({0,0});
    memset(d, -1, sizeof d);
    d[0][0] = 0;
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        int dx[] = { 1, 0, -1, 0}, dy[] = { 0, 1, 0, -1};
        for(int i = 0; i < 4; i ++ )
        {
            int x = dx[i] + t.first, y = dy[i] + t.second;
            if(x >= 0 && x < n && y >= 0 && y < m && !g[x][y] && d[x][y] == -1)
            {
                d[x][y] = d[t.first][t.second] + 1;
                q.push({x, y});
            }
        }
    }
    return d[n-1][m-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
int bfs()
{
    queue<string> q;
    q.push(start);
    string end = "12345678x";
    unordered_map<string,int> d;
    d[start] = 0;
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        if(t == end) return d[t];
        int k = t.find('x');
        int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
        int a = k / 3, b = k % 3;
        for(int i = 0; i < 4; i ++ )
        {
            int x = a + dx[i], y = b + dy[i];
            if(x >= 0 && x < 3 && y >= 0 && y < 3)
            {
                string u = t;
                swap(u[k], u[x * 3 + y]);
                if(!d.count(u))
                {
                    q.push(u);
                    d[u] = d[t] + 1;
                }
            }
        }
    }
    return -1;
}

3. 树和图的DFS

写法和正常的DFS 类似

DFS和BFS一般都需要使用一个st数组来判断一下这个节点是否已经被处理过了

算法的步骤：

  • 将点标记为已经遍历过
  • 遍历所有的邻点，看看邻点遍历过没有，没有的话就继续遍历下去

时间复杂度为$O(N)$

以树的重心这一题为例说明一下

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
//建图
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

// dfs
int dfs(int u)
{
    st[u] = true;
    int size = 0, sum = 1;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!st[j])
        {
            int d = dfs(j);
            size = max(size, d);
            sum += d;
        }
    }
    size = max(size, n - sum);
    ans = min(ans, size);
    return sum;
}

4. 树和图的BFS

和一般的BFS类似

算法的步骤为:

  • 初始化起点的距离为0，其他点的距离为无穷大或者-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
int bfs()
{
    queue<int> q;
    q.push(1);
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    st[1] = true;
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(!st[j])
            {
                q.push(j);
                d[j] = d[t] + 1;
                st[j] = true;
            }
        }
    }
    if(d[n] == 0x3f3f3f3f) return -1;
    else return d[n];
}

5. 拓扑排序

拓扑排序是指：将一个有向无环图进行排序，排好序之后，所有边的起点在终点之前，当出现环的时候，拓扑排序将无法完成对所有点的排序。时间复杂度是$O(N)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool topsort()
{
    hh = 0, tt = - 1;
    for(int i = 1; i <= n; i ++ )
        if(!d[i]) // d[i]是第i个节点的入度
            q[++tt] = i;
    while(hh <= tt)
    {
        auto t = q[hh ++ ];
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(!--d[j])
            {
                q[++tt] = j;
            }
        }
    }
    return tt == n - 1;
}

6. Dijkstra

Dijkstra算法可以解决非正权图，当点数较少，边多时，可以使用朴素版的Dijkstra算法，时间复杂度是$O(N^2)$，边比较多的时候，可以使用堆优化的Dijkstra()算法，时间复杂度是$O(MlogN)$

  • 算法步骤
    • 初始化起点距离为0，其他点为无穷大
    • 循环n-1次
      • 选出距离最小的点
      • 将这点加入已经确定最小距离的集合
      • 用这个点去更新集合（已经确定最小距离的集合）外的其他的点
  • 从上述步骤可以看出来，Dijkstra算法没循环一轮就可以确定一个点的最短距离，最后只剩一个点的时候无需更新了，所以Dijkstra只用循环n-1轮
  • 由于自环肯定不会出现在最短路的，因为在更新过程中，每次都要比较一下的，如果是自环$d[j] \le d[j] + g[j][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
int dijkstra()
{
    memset(d, 0x3f, sizeof d); // 初始化
    d[1] = 0;
    for(int i = 0; i < n -1 ; i++ ) // 循环n-1次,每次确定一个点
    {
        int t = -1;
        for(int j = 1; j <= n; j ++ )
            if(!st[j] && (t == -1 || d[t] > d[j]))
                t = j; // 找出集合外的距离最小的点
        st[t] = true;  // 拿出来的点一定是集合外的呀,将这个点加入集合中
        for(int j = 1; j <= n; j ++ ) 
        {
            if(!st[j] && d[j] > d[t] + g[t][j]) // 更新集合外的点
                d[j] = d[t] + g[t][j];
        }
        /*
       	也可以这样写
       	for(int j = 1; j <= n; j ++ )
       		d[j] = min(d[j], d[t] + g[t][i]);
       	因为集合内的点一定不会被更新的，已经是最小了，不可能被更新的
       	*/
    }
    if(d[n] == 0x3f3f3f3f) return -1;
    else return d[n];
}

堆优化版本

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
int dijkstra()
{
    memset(d, 0x3f, sizeof d); // 初始化
    d[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> q; // 记得定义成小根堆
    q.push({0,1});
    while(q.size())
    {
        auto t = q.top().second;
        q.pop(); // 取出堆顶,说明这个点是当前集合外距离最短的点
        if(st[t]) continue; // 重复入堆的就不用看了
        st[t] = true; // 将这个点放进集合
        for(int i = h[t]; i != -1; i = ne[i]) // 遍历它的所有邻点
        {
            int j = e[i];
            if(!st[j] && d[j] > d[t] + w[i]) // 更新集合外的点，这里去掉判断也是可以的，因为已经确定的点一定不会被更新
            {
                d[j] = d[t] + w[i];
                q.push({d[j],j}); // 可能有重复入堆，因为可能一个点和很多个点相连接，多次更新了
            }
        }
    }
    if(d[n] == 0x3f3f3f3f) return -1;
    return d[n];
}

7. Bellman_ford

负权图最短路问题，时间复杂度$O(NM)$

算法的步骤:

  • 初始化

  • 循环n次

  • 遍历所有的边进行更新

这里的每次循环代表走了一步路，所以这个算法可以解决步数限制的最短路问题

算法模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int bellman_ford()
{
    memset(d, 0x3f, sizeof d); // 初始化起点距离为0,其他点的距离为正无穷
    d[1] = 0;
    for(int i = 0; i < k; i ++ ) // 循环k次，表示最多走k步
    {
        memcpy(backup, d,sizeof d); // 备份一下距离，防止链式更新了，这样就不止走了一步了
        for(auto& [a, b, w] : e) // 遍历所有的边
        {
            d[b] = min(d[b] , backup[a] + w); // d[b]用这一次的，因为有重边，a用上一次的，因为最多走一步
        }
    }
    return d[n]; // 有可能走不到的点也被更新了，因为无穷加一个负数也还是无穷，但是按照程序会被更新，所以到不了不一定就是0x3f3f3f3f
}

bellman_ford可以判定负环，当第n次还有更新时，说明至少有一条路有n+1个点，根据抽屉原理，会有重复点，重复点，距离减小了，说明就是有负环了

8. SPFA

SPFA是bellman_ford算法的优化版本， $d_b = min(d_b, d_a + w)$, 可以看到$d_b$更新的前提是$d_a$更新了，所以我就存下来需要更新的点就好啦

算法步骤：

  • 初始化起点距离为0，其他点的距离为无穷大
  • 将起点加入队列，并将标志位置为1，说明需要更新（标志位表示是否在队列中，在队列中就要更新它的邻点了）
  • 循环直到队列空
    • 取出队头，并将标志置false,说明取出来了
    • 遍历队头的邻点，并更新一下
    • 更新的点判断是否在队列中，在队列中就不重复加入了，因为队列中只是一个是否要更新的标志而已啦，不在的话就加进去

算法模板：

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 spfa()
{
    memset(d, 0x3f, sizeof d); // 初始化距离
    d[1] = 0;
    queue<int> q; // 记录一下更新过的点
    q.push(1);
    st[1] = true;
    while(q.size())
    {
        auto t = q.front(); // 取出一个点
        q.pop();
        st[t] = false; // 表示已经取出来了
        for(int i = h[t]; i != -1; i = ne[i]) // 遍历它的邻点
        {
            int j = e[i];
            if(d[j] > d[t] + w[i]) // 更新一下
            {
                d[j] = d[t] + w[i];
                if(!st[j]) // 如果已经在队列中了，就不用重复进入了
                {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }
    return d[n];
}

SPFA是bellman_ford的优化算法，所以也可以判断负环，只用在记录一下个点最短路的长度即可，如果大于等于n了就有负环

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
bool spfa()
{
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    queue<int> q;
    for(int i = 1; i <= n; i ++ ) // 每个点都可能使负环的起点，都加进去
    {
        q.push(i);
        st[i] = true;
    }
   
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        st[t] = false;
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(d[j] > d[t] + w[i])
            {
                d[j] = d[t] + w[i];
                if(!st[j])
                {
                    st[j] = true;
                    q.push(j);
                }
                cnt[j] = cnt[t] + 1;
                if(cnt[j] >= n) return true; // 边数大于等于n了，有负环
            }
        }
    }
    return false;
}

9. Floyd

可以解决多源汇最短路问题，时间复杂度使$O(N^3)$，算法是动态规划算法

在有负环的图中得不到结果，但是多源汇最短路只会这么一个算法了

算法步骤

  • k循环
    • i 循环
      • j 循环
        • 状态转移方程 $d_{ij} = min(d_{ij}, d_{ik} + d_{kj})$

算法模板

1
2
3
4
5
6
7
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]);
}

开始的时候d存的是距离，结束之后存的就是最短路的距离了，注意最后无穷大也不一定是0x3f3f3f3f

10. Prim

最小生成树算法，有朴素版和Dijkstra写法很像，所以也可以进行堆优化，但是一般不常用，因为用Kruskal就好啦

算法时间复杂度为$O(N^2)$

算法步骤

  • 初始化一个点的距离为0，其他点的距离为无穷大
  • 循环n次，因为要选择n个点做最小生成树
    • 选择距离已经确定点集合最短的点
    • 将这点放到集合中
    • 用这个点更新一下其他点到集合的最小距离

从上面步骤可以看出，Prim算法每次都选择了一条边加到集合中，即每次将一个点加到最小生成树中去，这样最后如果有一步选出来的最小值已经是无穷大了就说明找不到点了，生不成了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int prim()
{
    memset(d, 0x3f, sizeof d); // 初始化距离
    d[1] = 0;
    int res = 0;
    for(int i = 0; i < n; i ++ ) // 循环n次
    {
        int t = -1;
        for(int j = 1; j <= n; j ++) // 选一个距离集合最小的点
            if(!st[j] && (t == -1 || d[t] > d[j]))
                t = j;
        if(d[t] == 0x3f3f3f3f) return 0x3f3f3f3f; // 如果生不成了
        res += d[t];
        st[t] = true; // 将这个点加入集合
        for(int j = 1; j <= n; j ++ ) // 更新一下邻点，这里为了简单不判断是否在集合中了，因为更新了在集合中的点不会影响的，不会被选到的
            d[j] = min(d[j], g[t][j]);
    }
    return res;
}

11. Kruskal

这是一个非常优美的算法，时间复杂度是$O(NlogN)$的

算法步骤：

  • 将所有的点都存起来，排个序
  • 依次选出最短的边，判断两个端点是否已经连通了，如果已经就不连通了，如果没有联通就将这两个点连通，那么相应的这两个点所在集合就在一起了，而且没有环
  • 如果最后选的边数小于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
struct Edge{
    int a, b, w;
    bool operator < (const Edge& e) const
    {
        return w < e.w;
    }
}e[N];
int p[N];
int cnt;
int n, m;
int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int main()
{
    cin >> n >> m;
    for(int i = 0; i < m; i ++ )
    {
        int a, b, w;
        cin >> a >> b >> w;
        e[i] = {a, b, w};
    }
    for(int i = 1; i <= n; i ++ ) p[i] = i; // 并查集
    sort(e, e + m); // 排序
    int res = 0, cnt = 0;
    for(auto& [a, b, w] : e) // 从小到大遍历所有的边
    {
        int pa = find(a), pb = find(b);
        if(pa != pb) // 不在一个集合中可以合并集合的
        {
            res+=w;
            cnt ++ ;
            p[pa] = pb;
        }
    }
    if(cnt < n - 1) puts("impossible");
    else cout << res << endl;
    return 0;
}

12. 二分图

12.1 染色法判别二分图

所谓二分图就是可以将点分为两个集合，集合内没有边就是二分图。

那么这么判断二分图呢？就是给二分图染色，可以证明，如果可以dfs染色下去的话，就可以二分，否则不可二分

$Proof:$首先，如果图里面没有环的话，一定可以二分的，因为只用交叉染色就好了；

如果有奇数环的话，必不可二分：假设环是$1,2,3,…,2k+1$, 那么连接$1,2$不同集合，$2,3$不同集合，…,用黑白两色表示的话，$1$是黑色，$2$是白色的话，那么所有奇数的点都是黑色， 但是$2k+1,1$是连着的，一条边两个点都黑的，属于同一个集合，所以不可二分。

反之：如果是偶数环的话，用上面的染色法就可以将整张图变成二分图。$Q.E.D.$

算法模板：用dfs染色即可

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
bool dfs(int u, int c)
{
    color[u] = c; // 染色
    for(int i = h[u]; i != -1; i = ne[i]) // 遍历邻点
    {
        int j = e[i];
        if(color[j] == 0 && !dfs(j, 3 - c)) return false; // 如果没染过色，然后就去染色，然不了的话就说明染不了
        else if(color[j] == c) return false; // 如果染过色了，但是一条边的两个端点的颜色是一样的，说明染不了
    }
    return true; // 成功染色了
}
int main()
{
    int n, m;
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while(m -- )
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    bool ok = true;
    for(int i = 1; i <= n; i ++ ) // 遍历每一个点，看看染没染色
    {
        if(!color[i])
        {
            if(!dfs(i, 1))
            {
                ok = false;
                break;
            }
        }
    }
    if(ok) puts("Yes");
    else puts("No");
    return 0;
}

12.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
bool find(int x)
{
    for(int i = h[x] ; i != -1; i = ne[i]) // 遍历他心仪的所有女孩子
    {
        int j = e[i];
        if(st[j]) continue; // 这个女孩被别人考虑了，不用考虑了
        st[j] = true; // 我正在考虑她，你们先别考虑
        if(match[j] == 0 || find(match[j])) // 如果这个女孩没有男友，就匹配，如果有男友，就替她男友找个下家，撬墙角
        {
            match[j] = x;
            return true;
        }
    }
    return false; // 所有心仪女孩都考虑过了，都没有，注孤生
}
int main()
{
    int n1,n2, m;
    cin>> n1 >> n2 >>  m;
    memset(h, -1, sizeof h);
    while(m -- )
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    int res = 0;
    for(int i = 1; i <= n1; i ++ )
    {
        memset(st,false, sizeof st); // 一开始肯定是一个女孩都没考虑过的呀
        if(find(i)) res ++; 
    }
    cout << res << endl;
    return 0;
}
  • © 2019-2022 Wendell
  • Powered by Hexo Theme Ayer

请我喝杯咖啡吧~

支付宝
微信