拓扑排序

有向无环图 DAG

如果一个有向图的任意顶点都无法通过一些有向边回到自身，那么称这个有向图为有向无环图。

拓扑排序

拓扑排序是将有向无环图G的所有顶点排成一个线性序列，使得对图G中的任意两个顶点u、v，如果存在边 u->v，那么在序列中u一定在v前面，这个序列又被称为拓扑序列。

算法实现

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edge

while S is not empty do
    remove a node n from S
    add n to L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S

if graph has edges then
    return error   (graph has at least one cycle)
else
    return L   (a topologically sorted order)

复杂度分析：

  • 时间复杂度：O(E + V)。这里 E 表示邻边的条数，V 表示结点的个数。初始化入度为 0 的集合需要遍历整张图，具体做法是检查每个结点和每条边，因此复杂度为 O(E+V)，然后对该集合进行操作，又需要遍历整张图中的每个结点和每条边，复杂度也为 O(E+V)；
  • 空间复杂度：O(V)：入度数组、邻接表的长度都是结点的个数 V，即使使用队列，队列最长的时候也不会超过 V，因此空间复杂度是 O(V)。

题解

207 Course Schedule

标准拓扑排序

 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

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        unordered_map<int, int> inDegree;
        unordered_map<int, vector<int>> adjacent;
        for (auto item : prerequisites) {
            int course = item[0];
            int pre = item[1];
            inDegree[course]++;
            adjacent[pre].push_back(course);
        }

        queue<int> q;
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                q.push(i);
            }
        }

        vector<int> result;
        while (!q.empty()) {
            int pre = q.front();
            q.pop();
            result.push_back(pre);

            for (auto course : adjacent[pre]) {
                inDegree[course]--;
                if (inDegree[course] == 0) {
                    q.push(course);
                }
            }
        }

        return result.size() == numCourses;
    }
};

210 Course Schedule II

  • Topological sort，与 207 相同解法

269 Alien Dictionary

现有一种使用字母的全新语言，这门语言的字母顺序与英语顺序不同。您有一个单词列表（从词典中获得的），该单词列表内的单词已经按这门新语言的字母顺序进行了排序。需要根据这个输入的列表，还原出此语言中已知的字母顺序。

输入:
[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]

输出: "wertf"
  • Topological sort.

310 Minimum Height Trees

  • Given a tree, find the root set where it has minimum height.
  • Topological sort, remove leaves.
 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

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        unordered_map<int, int> outDegree;
        unordered_map<int, unordered_set<int>> adjacent;
        vector<int> result;
        if (n == 1) {
            result.push_back(0);
            return result;
        }

        for (auto e : edges) {
            int v0 = e[0];
            int v1 = e[1];
            outDegree[v0]++;
            outDegree[v1]++;
            adjacent[v0].insert(v1);
            adjacent[v1].insert(v0);
        }

        queue<int> q;
        for (int i = 0; i < n; i++) {
            if (outDegree[i] == 1) {
                q.push(i);
            }
        }

        while (!q.empty()) {
            int size = q.size();
            result.clear();
            for (int i = 0; i < size; i++) {
                int cur = q.front();
                q.pop();
                result.push_back(cur);

                outDegree[cur]--;
                for (auto u : adjacent[cur]) {
                    outDegree[u]--;
                    if (outDegree[u] == 1) {
                        q.push(u);
                    }
                }
            }
        }

        return result;
    }
};

332 Reconstruct Itinerary

  • O(n) time since the problem is finding Eularian path.

399 Evaluate Division

  • Use floyd. Similar to currency exchange.
  • Union-find is also ok. For each a/b=x, assume a=x and b=1. If a and b already have assumed values, update them. Union-find is used for this update.

444 Sequence Reconstruction

  • Given some sequences, judge whether a supersequence S can be uniquely constructed from those sequences.
  • Topological sort.

743 Network Delay Time

  • Given a network and source node, find time for all nodes to receive a message.
  • BFS on priority queue or Dijkstra.

787 Cheapest Flights Within K Stops

  • BFS on priority queue.

863 All Nodes Distance K in Binary Tree

  • Convert tree to a graph.

1136 Parallel Courses

  • Topological sort.

1066 Campus B

  • Similar to 1057, but requires overall manhattan distance sum minimum.
  • DFS or use max flow. Note for cost x we can use max_cost-x to replace x because there are ways person-num edges.

参考资料