algorithm - 拓扑排序以查找特定节点的依赖关系

Question

给定下图：

我可以使用什么算法来输出拓扑有序列表以及要完成的任务，并且仅与特定节点相关？

例如，考虑到node 2，列表应该是：

7, 5, 11, 2

或者

5, 7, 11, 2

Answer 1

1. 反转边缘
2. 运行 DFS 从2
3. 离开节点后，将其插入列表中。

例子：

Enter 2
  Enter 11
    Enter 7
    Leave 7, insert into list
    Enter 5
    Leave 5, insert into list
  Leave 11, insert into list
Done, insert 2 into list

Result: 7, 5, 11, 2

Answer 2

您必须将图分解为邻接矩阵，其中从节点 A 到节点 B 的每个链接都表示为矩阵中的“1”，其中节点对应于节点和列。

从这一点开始，您需要做的就是从终端节点向后工作，识别指向它的节点，然后从每个节点向后工作。

现在，您可能希望以广度优先的方式执行此操作，因此使用队列数据结构来跟踪“依赖”节点。