sorting - Topological sort on an incidence matrice

Question

If my directed graph is represented as its incidence matrix how do I apply topological sort on that graph? I think it can be done by finding null rows and removing them with their corresponding columns but this is not efficient.How can I do this more efficiently?

Answer 1

我认为这是家庭作业。尝试以下算法：

1）识别所有入度为0的节点（没有边缘点进入节点）

2) 对于步骤 1 中的每个节点，从该节点开始执行深度优先搜索游走。

如果图是 DAG（有向无环图 - 没有像 A -> B、B -> C、C -> A 这样的有向环），则您看到节点的顺序保证是拓扑排序。