将有向图编码为数字
Encoding directed graph as numbers
假设我有一个有向图，单根且没有环。我想在每个节点上添加一个类型（例如作为具有一些自定义排序的整数），具有以下 属性:
if Node1.type <= Node2.type then there exists a path from Node1 to Node2
注意拓扑排序其实满足倒序属性:
if there exists a path from Node1 to Node2 then Node1.type <= Node2.type
所以不能在这里使用。
现在请注意，这里不能使用具有自然顺序的整数，因为每两个整数都可以进行比较，即整数的顺序是线性的，而树不一定是。
这是一个例子。假设该图有 4 个节点 A, B, C, D 和 4 个箭头：
A->B, A->C, B->D, C->D
所以这是一颗钻石。现在我们可以把
A.type = 00
B.type = 01
C.type = 10
D.type = 11
右边是二进制格式的整数。比较按位定义：
(X <= Y) if and only if (n-th bit of X <= n-th bit of Y for all n)
所以我猜可以使用这样的排序，问题是如何从给定的图形构造值？我什至不确定解决方案是否始终存在。有什么提示吗？
更新：由于对我使用的术语存在一些误解，让我更明确一点：我对有向无环图感兴趣，这样只有一个节点没有前辈（a.k.a.根）并且任意两个节点之间至多有一个箭头。钻石就是一个例子。它不必只有一片叶子（即没有后继节点）。每个节点可能有多个前驱和多个后继。你可能会说这是一个具有最小元素的偏序集（即唯一的全局最小元素）。
您将关系称为 <=，但它不一定是完整的（即：对于给定的一对 a 和 b，它可能是 a <= b也没有 b <= a).
这里有一个关于如何定义它的想法。
如果您的节点编号为 0、1...、N-1，那么您可以这样定义 type：
type(i) = (1 << i) + sum(1 << (N + j), for j such that Path(i, j))
并像这样定义 <=：
type1 <= type2 if (type1 >> N) & type2 != 0
即type(i)在最低N位编码i的值，在最高N位编码所有可达节点的集合。 <= 关系在编码的可达节点集中查找目标节点。
无论图中是否存在循环，此定义都有效，实际上只是对节点集上的任意关系进行编码。
您可以通过使用 ceil(log2(N)) 位来编码节点号（每个 type 总共 N + ceil(log2(N)) 位）来使定义更有效一些。
对于任何 DAG，您可以定义 x <= y 为 "there's a path from x to y"。这种关系是偏序的。我认为问题是如何有效地表示这种关系。
对于每个顶点X，将¡X 定义为从X 可达的顶点集（包括X 本身）。两个语句
- ¡X 是¡Y
的子集
- X 可以从 Y 到达
是等价的。
将这些集合编码为位集（N 位二进制数），您就设置好了。
问题说（并继续说）输入是一棵树，但后来的编辑用菱形图的例子反驳了这一点。在这种非树的情况下，我下面的算法将不适用。
现有答案适用于一般有向图的一般关系，这将它们的表示大小扩大到 n 个顶点的 O(n) 位。由于您有一棵树，因此可以使用更短的 O(log n) 位表示。
在远离根的树中，对于任意两个顶点u和v，分别从u和v可达的叶子集L(u)和L(v)必须不相交，或者一个必须是另一个的子集。如果它们不相交，则 u 无法从 v 到达（反之亦然）；如果一个是另一个的真子集，则具有较小集合的那个可以从另一个到达（在这种情况下，具有较小集合的那个必然具有更大的深度）。如果 L(u) = L(v)，则当且仅当 depth(v) < depth(u) 时，u 可从 v 到达，其中 depth(u) 是从根到 u 的路径上的边数。 （特别是，如果 L(u) = L(v) 且 depth(u) = depth(v)，则 u = v。）
我们可以通过注意从给定顶点 v 可达的所有叶子占据树的中序遍历输出的叶子的连续部分来简明地编码这种关系。对于任何给定的顶点 v，这组叶子因此可以由一对整数 (first, last) 表示，其中 first 标识第一个叶子（按顺序遍历顺序），last 最后一个。测试是否存在从 i 到 j 的路径非常简单——在伪 C++ 中：
bool doesPathExist(int i, int j) {
return x[i].first <= x[j].first && x[i].last >= x[j].last && depth[i] <= depth[j];
}
请注意，如果树中的每个非叶顶点都有至少 2 个子节点，那么您就不需要为深度烦恼，因为在这种情况下 L(u) = L(v) 意味着 u = v . （我的 post 的原始版本做出了这个假设；我现在已经修复它，即使不是这种情况也能正常工作。）
假设我有一个有向图，单根且没有环。我想在每个节点上添加一个类型（例如作为具有一些自定义排序的整数），具有以下 属性:
if Node1.type <= Node2.type then there exists a path from Node1 to Node2
注意拓扑排序其实满足倒序属性:
if there exists a path from Node1 to Node2 then Node1.type <= Node2.type
所以不能在这里使用。
现在请注意，这里不能使用具有自然顺序的整数，因为每两个整数都可以进行比较，即整数的顺序是线性的，而树不一定是。
这是一个例子。假设该图有 4 个节点 A, B, C, D 和 4 个箭头：
A->B, A->C, B->D, C->D
所以这是一颗钻石。现在我们可以把
A.type = 00
B.type = 01
C.type = 10
D.type = 11
右边是二进制格式的整数。比较按位定义：
(X <= Y) if and only if (n-th bit of X <= n-th bit of Y for all n)
所以我猜可以使用这样的排序，问题是如何从给定的图形构造值？我什至不确定解决方案是否始终存在。有什么提示吗？
更新：由于对我使用的术语存在一些误解，让我更明确一点：我对有向无环图感兴趣，这样只有一个节点没有前辈（a.k.a.根）并且任意两个节点之间至多有一个箭头。钻石就是一个例子。它不必只有一片叶子（即没有后继节点）。每个节点可能有多个前驱和多个后继。你可能会说这是一个具有最小元素的偏序集（即唯一的全局最小元素）。
您将关系称为 <=，但它不一定是完整的（即：对于给定的一对 a 和 b，它可能是 a <= b也没有 b <= a).
这里有一个关于如何定义它的想法。
如果您的节点编号为 0、1...、N-1，那么您可以这样定义 type：
type(i) = (1 << i) + sum(1 << (N + j), for j such that Path(i, j))
并像这样定义 <=：
type1 <= type2 if (type1 >> N) & type2 != 0
即type(i)在最低N位编码i的值，在最高N位编码所有可达节点的集合。 <= 关系在编码的可达节点集中查找目标节点。
无论图中是否存在循环，此定义都有效，实际上只是对节点集上的任意关系进行编码。
您可以通过使用 ceil(log2(N)) 位来编码节点号（每个 type 总共 N + ceil(log2(N)) 位）来使定义更有效一些。
对于任何 DAG，您可以定义 x <= y 为 "there's a path from x to y"。这种关系是偏序的。我认为问题是如何有效地表示这种关系。
对于每个顶点X，将¡X 定义为从X 可达的顶点集（包括X 本身）。两个语句
- ¡X 是¡Y 的子集
- X 可以从 Y 到达
是等价的。
将这些集合编码为位集（N 位二进制数），您就设置好了。
问题说（并继续说）输入是一棵树，但后来的编辑用菱形图的例子反驳了这一点。在这种非树的情况下，我下面的算法将不适用。
现有答案适用于一般有向图的一般关系，这将它们的表示大小扩大到 n 个顶点的 O(n) 位。由于您有一棵树，因此可以使用更短的 O(log n) 位表示。
在远离根的树中，对于任意两个顶点u和v，分别从u和v可达的叶子集L(u)和L(v)必须不相交，或者一个必须是另一个的子集。如果它们不相交，则 u 无法从 v 到达（反之亦然）；如果一个是另一个的真子集，则具有较小集合的那个可以从另一个到达（在这种情况下，具有较小集合的那个必然具有更大的深度）。如果 L(u) = L(v)，则当且仅当 depth(v) < depth(u) 时，u 可从 v 到达，其中 depth(u) 是从根到 u 的路径上的边数。 （特别是，如果 L(u) = L(v) 且 depth(u) = depth(v)，则 u = v。）
我们可以通过注意从给定顶点 v 可达的所有叶子占据树的中序遍历输出的叶子的连续部分来简明地编码这种关系。对于任何给定的顶点 v，这组叶子因此可以由一对整数 (first, last) 表示，其中 first 标识第一个叶子（按顺序遍历顺序），last 最后一个。测试是否存在从 i 到 j 的路径非常简单——在伪 C++ 中：
bool doesPathExist(int i, int j) {
return x[i].first <= x[j].first && x[i].last >= x[j].last && depth[i] <= depth[j];
}
请注意，如果树中的每个非叶顶点都有至少 2 个子节点，那么您就不需要为深度烦恼，因为在这种情况下 L(u) = L(v) 意味着 u = v . （我的 post 的原始版本做出了这个假设；我现在已经修复它，即使不是这种情况也能正常工作。）