c# - 有向图顶点子集的拓扑排序

Question

我正在用 C# 4.0 编写一个程序，我已经将其抽象为以下内容(我提到语言是为了让您知道我必须使用哪些库；没有第三方库):

---

让S = { s1, s2, s3, ..., sn } .

对于所有si , sj在 S , i != j , 函数 f(si, sj)是 { true, false } 的一个元素.调用此函数 f然而，这是非常昂贵的，应该尽可能少地进行。

给定集 T = { t1, t2, t3, ..., tm } S 的非空子集, 计算序列 U = u1, u2, u3, ..., uo其中包含 T 的所有元素这样 f(ui, uj) == false对于所有 i < j , 和 f(ui, s') == false对于所有 i和 s'在 S - U .您可以假设存在这样的序列。

---

虽然这与学校没有任何关系(它是为了工作)，但我希望尽可能少地帮助我找到你能想到的最佳解决方案，这样我可以了解更多:)

---

提示(我想到的一些东西:)

1. 您需要至少访问每个节点一次。考虑T = { t } 的情况。和 f(t, s') == false对于所有 s'在 S - T和 |S| >= 2 .在这种情况下，一次也足够了。

2. 至少 U必须计算。此计算可以表示为以下内容:一个 |S|x|S|条目为的邻接矩阵

   • ? : 我不知道
   • 1 : 取决于。
   • 0 : 不依赖于。
   • - : 我不在乎。

考虑这一点(我正在通过一个示例来查看是否存在用于帮助开发算法的最佳潜在检查序列的模式)。 S = { a, b, c, d, e } T = { a, b, c } (用星星表示):

     a  b  c  d  e
   ----------------
*a | -  -  -  ?  ?
*b | -  -  -  ?  ?
*c | -  -  -  ?  ?
 d | -  -  -  -  ?
 e | -  -  -  ?  -

U = { a, b, c }最初。对角线是 -因为f当其操作数相等时未定义。自 a , b和 c已经在集合中，是否有人依赖它们并不重要，因此 - .

f(a, d) , f(a, e) , f(b, d) , f(b, e) , f(c, d) , f(c, e)由于对称性，都是平等的候选人。假设我们选择 f(a, d)它返回 false。我们的表现在看起来像这样:

     a  b  c  d  e
   ----------------
*a | -  -  -  0  ?
*b | -  -  -  ?  ?
*c | -  -  -  ?  ?
 d | -  -  -  -  ?
 e | -  -  -  ?  -

案例 1:U = { a, b, c }

要找出这一点，我们可以通过检查 f(b, d) 来检查 3 次，如果幸运的话。 , f(c, d)和 f(e, d)并且让它们都是false .

案例 2:U = { a, b, c, d, e }

要找出这一点，我们可以在两次检查中完成，如果幸运的话，通过检查 f(b, d)和 f(a, e)并让他们都返回 true .

(我还没有完全想清楚这些，我要去吃饭了。感谢大家阅读!)

案例 3:U = { a, b, c, d }

案例 4:U = { a, b, c, e }

Answer 1

我的理解是，您想要从子集 T 中的任何节点开始可以访问的所有节点...如果这就是您的意思，您可以试试这个...

1. 用您的所有节点填充一个字典(节点作为键，访问的 bool 值作为值(此值开始为 false))
2. 用子集 T 中的节点填充队列(添加它们时在字典中搜索它们并将它们标记为已访问)
3. 选择队列中的第一个元素检查你可以访问的节点，在字典中搜索是否访问过，如果访问过则跳过，如果没有，将它们添加到队列中并将它们设置为已访问，删除第一个元素队列
4. 重复 3 直到队列中没有元素

你从 t 开始可以访问的节点子集是你在字典中标记的节点

希望对你有帮助