算法(四)

发表于2022-10-06更新于2023-04-25字数统计2.2k阅读时长14分阅读次数

二分图

二分图(Bipartite graph)是一种特殊的无向图，对于一张图 G=(V,E)G=(V,E)，如果所有的顶点 VV 能够被分割成两个互不相交的子集 (A,B)(A,B)，且图中每条边 Ei,jE_{i,j} 的两个顶点有一个在子集 AA 中，另一个在子集 BB 中，那么这张图被称为一个二分图。

785. 判断二分图

以邻接表的形式给出一张图，判断其是否是二分图。

1
2
3
4
5
输入：graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
0---1
| \ |
3---2
输出：false

解：判断一张图是否是二分图，可以使用二分图算法(或染色法)，使用两种颜色对图中的结点进行染色，且保证相邻的结点染上不同的颜色。如果无法做到，则图不是二分图。

这里使用广度优先遍历给结点上色，0表示该结点还未上色，1 和 2 分别表示不同的颜色。每次遍历的第一个点先上颜色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
bool isBipartite(vector<vector<int>>& graph) {
    // 二分图染色
    int n = graph.size();
    vector<int> color(n, 0);   // 结点颜色， 0表示未上色
    queue<int> qu;
    for (int i=0; i<n; ++i) {
        if (color[i] == 0) {
            color[i] = 1;
            qu.push(i);
            while (!qu.empty()) {
                int node = qu.front();
                qu.pop();
                // 广度搜索当前结点的相邻结点，涂上不同的颜色
                for (int next : graph[node]) {
                    if (color[next] == color[node]) {
                        return false;
                    } else if (color[next] == 0) {
                        color[next] = (color[node] == 1 ? 2 : 1);
                        qu.push(next);
                    }
                }
            }
        }
    }
    return true;
}

Dijkstra 算法

Dijkstra 算法是求单源最短路径的常用算法，它要求图中边的权重均为正数，能够得出图中所有结点到源结点的最短距离。 Dijkstra 算法的思想是贪心。

我们首先对每个结点 ii 记录一个到源结点的最短距离数组 distdist，其中 dist[i]dist[i] 表示结点 ii 到源结点最短距离，该数组所有值初始化为 +∞+\infty。Dijkstra 算法在运行过程中维持一组结点集合 SS，该集合中所有的点到源结点的最短距离均已被找到。算法循环执行：在集合V−SV-S中选择到源结点路径估计最短的结点 uu，将其加入集合 SS，然后对所有从 uu 出发的边进行松弛：

1
2
3
for vertex v in u.Adj:
    if w(u, v) + dist[u] < dist[v]:
        dist[v] = w(u, v) + dist[u]

也就是说如果花费更小，我们可以通过结点 uu 到达结点 vv。《算法导论3th》P383 对该算法有详细的讨论。

743. 网络延迟时间

有 n 个网络结点，标记为 1 到 n。

给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源结点，vi 是目标结点， wi 是一个信号从源结点传递到目标结点的时间。

现在，从某个结点 K 发出一个信号。需要多久才能使所有结点都收到信号？如果不能使所有结点收到信号，返回 -1 。

解：经典的有向图单源最短路径，且每条边的权值都为正，可以使用Dijkstra算法进行求解得到每个结点距离源结点的最短路径，然后返回各结点最短路径的最大值。

先使用最朴素的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
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
    // 朴素Dijkstra算法
    vector<vector<int>> graph(n+1, vector<int>(n+1, INT_MAX / 2));
    // 建图
    for (const auto& time : times) {
        graph[time[0]][time[1]] = time[2];
    }
    vector<int> dist(n+1, INT_MAX / 2);   // 记录到源结点的最短路径
    dist[k] = 0;
    vector<int> used(n+1, 0);           // 记录当前已经确定最短路径的结点集合 S
    for (int i=1; i<=n; ++i) {
        int node = -1;
        // 找到未确定结点中距离估计最小的结点
        for (int i=1; i<=n; ++i) {
            if (!used[i] && (node == -1 || dist[i] < dist[node])) {
                node = i;
            }
        }
        used[node] = 1;
        // 松弛所有从node出发的边
        for (int i=1; i<=n; ++i) {
            if (graph[node][i] + dist[node] < dist[i]) {
                dist[i] = graph[node][i] + dist[node];
            }
        }
    }
    int res = *max_element(dist.begin()+1, dist.end());
    return res == INT_MAX / 2 ? -1 : res;
}

此外，可以使用最小优先队列来保存未确定距离的结点，从而优化找距离估计最小点的时间：

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
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
    // graph[u_i] = <v_i, w_i>
    vector<vector<pair<int, int>>> graph(n+1, vector<pair<int, int>>());
    for (const auto& t : times) {
        graph[t[0]].push_back({t[1], t[2]});
    }
    vector<int> dist(n+1, INT_MAX);
    dist[k] = 0;
    // 用小根堆获取当前未确定最短距离的点中距离最小的点
    // <distance, node>
    priority_queue<pair<int, int>> qu;
    qu.push({0, k});
    while (!qu.empty()) {
        auto p = qu.top();
        qu.pop();
        int dis = p.first, node = p.second;
        // 这些结点在队列里，最短路径被更新过
        if (dist[node] < dis) {
            continue;
        }
        // 遍历相邻结点，松弛相应边
        for (auto& m : graph[node]) {
            int nei = m.first, newDis = m.second + dist[node];
            if (newDis < dist[nei]) {
                dist[nei] = newDis;
                // 只要更新了距离的邻居都入队，有些结点可能还不是最终结点，这些结点会 continue
                qu.push({newDis, nei});  
            }
        }
    }
    int res = *max_element(dist.begin()+1, dist.end());
    return res == INT_MAX ? -1 : res;
}

拓扑排序

对于一个有向无环图 G=(V,E)G=(V,E)，其拓扑排序(topological sort)是所有结点的一种线性排序，该排序满足：若图中包含边 (u,v)(u,v)，则结点 uu 在拓扑排序中处于结点 vv 的前面。这要求图是无环的，换句话说，对于有环的有向图不存在拓扑排序。拓扑排序的结果往往不是唯一的。

210. 课程表 II

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。

返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

解：非常经典的拓扑排序题，和算法导论上举例几乎是一致的，拓扑排序的第一种解法是深度优先遍历每个结点，并记录每个结点的结束访问时间，并按照结点的结束访问时间对结点排序。每个结点有未访问，访问中和已访问三种状态。

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
class Solution {
public:
    bool valid = true;  // 当前是否找到环路
    vector<int> res;
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        // 拓扑排序
        vector<vector<int>> graph(numCourses, vector<int>());
        // 记录每个节点的访问状态：0-未访问，1-访问中(还未回溯)，2-访问完成
        vector<int> visit(numCourses, 0);  
        // 构建图
        for (const auto& p : prerequisites) {
            graph[p[1]].push_back(p[0]);
        }
        for (int i=0; i<numCourses; ++i) {
            if (!valid) {
                return {};
            }
            dfs(i, graph, visit);
        }
        reverse(res.begin(), res.end());  // 需要按结束时间反序
        return res;
    }

    void dfs(int node, vector<vector<int>>& graph, vector<int>& visit) {
        // 发现环路
        if (visit[node] == 1) {
            valid = false;
            return;
        }
        if (visit[node] == 2) {
            return;
        }
        visit[node] = 1;
        for (int next : graph[node]) {
            dfs(next, graph, visit);
        }
        visit[node] = 2;
        // 访问完当前节点(回溯完)
        res.push_back(node);
    }
};

第二种方法是广度优先搜索，其中关键点是记录每个结点的入度，也就是进入边的数量，每经过一个结点就将其入度减1， 只要一个结点入度为 0 就将其加入队列和结果。因为入度为 0 的结点没有依赖它的课程，那么就可以先修这门课。

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
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
    // 拓扑排序，广度优先算法
    vector<vector<int>> graph(numCourses, vector<int>()); 
    vector<int> indegree(numCourses, 0);  // 记录每个节点的入度
    vector<int> res;
    for (const auto& p : prerequisites) {
        graph[p[1]].push_back(p[0]);
        ++ indegree[p[0]];
    }
    queue<int> qu;
    // 从入度为 0 的节点开始搜索
    for (int i=0; i<numCourses; ++i) {
        if (indegree[i] == 0) {
            qu.push(i);
            res.push_back(i);
        }
    }
    while (!qu.empty()) {
        int node = qu.front();
        qu.pop();
        for (int next : graph[node]) {
            --indegree[next];
            if (indegree[next] == 0) {
                res.push_back(next);
                qu.push(next);
            }
        }
    }
    // 存在环路，导致有些节点入度始终大于 0
    if (res.size() != numCourses) {
        return {};
    }
    return res;
}

参考文献

  1. https://github.com/changgyhub/leetcode_101
  2. 《算法导论3th》
  3. https://leetcode-cn.com/problemset/all/