算法图算法

异构图建图

字数统计: 1.8k字   |   阅读时长: 7分
,

摘要: 两种类型的点和边的异构图建图

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

我们知道图论的算法相对比较固定，变化的地方不多，难点在于怎样从实际问题转换为图，图中的节点、边在原问题中是什么含义；原问题怎样转换为图上的问题。

建图过程的一个难点是 Corner Case 比较多，在文章 建图的CornerCase 中我们处理过类似的问题。

本文我们看建图时另一个很常见的难点，也就是图中有两种类型的点（项目和组），以及两种类型的边（从项目到组，表示项目属于哪个组；从项目到项目，表示项目依赖关系）。这样在建图的时候要根据需要进行分层，用两个邻接表分别表示外层图和内层图。具体思路见题解。

$1 题目

公司共有 n 个项目和 m 个小组，每个项目要不没有归属，要不就由其中的一个小组负责。

我们用 group[i] 代表第 i 个项目所属的小组，如果这个项目目前无人接手，那么 group[i] 就等于 -1。（项目和小组都是从零开始编号的）

请你帮忙按要求安排这些项目的进度，并返回排序后的项目列表：

  • 同一小组的项目，排序后在列表中彼此相邻。
  • 项目之间存在一定的依赖关系，我们用一个列表 beforeItems 来表示，其中 beforeItems[i] 表示在进行第 i 个项目前（位于第 i 个项目左侧）应该完成的所有项目。

如果存在多个解决方案，只需要返回其中任意一个即可。如果没有合适的解决方案，就请返回一个 空列表。

提示：

1
2
3
4
5
6
7
1 <= m <= n <= 3*10^4
group.length == beforeItems.length == n
-1 <= group[i] <= m-1
0 <= beforeItems[i].length <= n-1
0 <= beforeItems[i][j] <= n-1
i != beforeItems[i][j]
beforeItems[i] 不含重复元素

示例 1：

输入：n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]
输出：[6,3,4,1,5,2,0,7]
示例 2：
输入：n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3],[],[4],[]]
输出：[]
解释：与示例 1 大致相同，但是在排序后的列表中，4 必须放在 6 的前面。

$2 题解

算法: 异构图建图+拓扑排序

一共有 n 个项目，m 个组。

最终输出的是项目排序，而项目之间有两种依赖关系，一个是项目之间本身的依赖关系，一个是以同一个组的项目要挨在一起。

因为同一个组的项目要挨在一起，可以将同一个组的项目视为一个点，暂时不考虑内部的顺序，此时要做的就是两层排序。

  • 第一层：各个组以及各个无主项目之间的排序。
  • 第二层：各个组内部的项目之间的顺序。

在一个图上维护第一层(外层)这些关系，也就是从项目到组的关系。一共 n + m 个点，其中前 n 个点 [0..n-1] 是项目；后 m 个点 n..n + m - 1 是组。外层图建图的依据是如果是无主项目 x，对应外层图的 g_outer[x] 节点，如果是有主项目，属于组 group[i]，则对应外层图的 g_outer[group(x) + n]。

在另一个图上维护第二层(内层)这些关系，一共 n 个点。内层图的建图依据比较简单，对于项目 x，对应内层图的节点 g_inner[x]。

此外我们还需要一个图，维护从组到项目的关系，即一个组都有哪些项目。

基于以上分析，我们给出建图的过程。首先建立两个层的图 g_inner 和 g_outer，其中：

  • g_outer 维护组与组的关系、组与无主项目之间的关系，以及若干无主项目的关系。
  • g_inner 维护组内各个项目的关系。

建图过程: 对每个节点，枚举所有依赖关系的边 (x, i)，

  • 如果 x 项目无主，则
    • x 属于 g_outer 的节点 g_outer[x] 此时就要看项目 i 了，如果项目 i 无主，则连接 x -> i，如果有主，则连接 x -> group[i] + n。
  • 如果 x 项目有主，则
    • group[x] + n 属于 g_outer，如果 i 无主，则连接 group[x] + n -> i，如果 i 有主，还要看 i 的主根 x 的主是否一样，若不一样，则则连接 group[x] + n -> group[i] + n，若一样，则这属于内层关系，在内层图中加入该点 g_inner[x].push_back(i)，即连接 (x , i)

按层次建好图后，分别对外层和内层做拓扑排序。

代码(C++)

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
class Solution {
public:
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        vector<vector<int> > g(n + m); // 记录组对应哪些项目

        // 外层 TopSort, 组编号为 [n, n + m - 1]
        vector<vector<int> > g_outer(n + m), g_inner(n);
        vector<int> indegrees_outer(n + m, 0), indegrees_inner(n, 0);

        for(int i = 0; i < n; ++i)
            if(group[i] != -1) // 第 i 个项目
                g[group[i] + n].push_back(i);

        // 建立两种图的关系
        for(int i = 0; i < n; ++i)
            for(int x: beforeItems[i])
            {
                if(group[x] == -1)
                {
                    if(group[i] == -1)
                        g_outer[x].push_back(i);
                    else
                        g_outer[x].push_back(group[i] + n);
                }
                else
                {
                    if(group[i] == -1)
                        g_outer[group[x] + n].push_back(i);
                    else
                    {
                        if(group[x] != group[i])
                            g_outer[group[x] + n].push_back(group[i] + n);
                        else
                            g_inner[x].push_back(i);
                    }
                }
            }

        // 统计外部关系的入度
        for(int i = 0; i < m + n; ++i)
            for(int j = 0; j < (int)g_outer[i].size(); ++j)
                ++indegrees_outer[g_outer[i][j]];

        // 统计内部依赖关系每个点的入度
        for(int i = 0; i < n; i++)
            for(int j = 0; j < (int)g_inner[i].size(); ++j)
                ++indegrees_inner[g_inner[i][j]];

        queue<int> q;
        for(int i = 0; i < m + n; ++i)
            if(indegrees_outer[i] == 0)
                q.push(i);

        vector<int> sorted_outer = top_sort(q, g_outer, indegrees_outer);
        if((int)sorted_outer.size() != m + n)
            return {};

        vector<int> result;
        for(int v: sorted_outer)
        {
            if(v < n)
            {
                // 当前是项目
                if(group[v] == -1) // 项目不属于任何组
                    result.push_back(v);
            }
            else
            {
                // 当前点是一个组
                int cnt = 0;
                for(int j: g[v])
                {
                    // 当前组 v 下的项目 j
                    ++cnt;
                    if(indegrees_inner[j] == 0)
                        q.push(j);
                }
                vector<int> sorted_inner = top_sort(q, g_inner, indegrees_inner);
                if((int)sorted_inner.size() != cnt)
                    return {};
                result.insert(result.end(), sorted_inner.begin(), sorted_inner.end());
            }
        }
        return result;
    }

private:
    vector<int> top_sort(queue<int>& q, const vector<vector<int> >& g, vector<int>& indegrees)
    {
        // start 已经进队
        vector<int> result;
        while(!q.empty())
        {
            int cur = q.front();
            q.pop();
            result.push_back(cur);
            for(int son: g[cur])
            {
                --indegrees[son];
                if(indegrees[son] == 0)
                    q.push(son);
            }
        }
        return result;
    }
};
Share