验证给定的图节点列表是否是正确的拓扑顺序

Question

我接到一项任务，要编写一些代码，从图中获取节点列表，并确定它们的拓扑顺序是否正确。

图形在内存中表示如下：

typedef struct graph_t* Graph;
typedef struct node_t* Node;

struct node_t {
    int id;
    /*incoming edges*/
    Linked_list incoming;
    /*outgoing edges*/
    Linked_list outgoing;
};

struct graph_t {
    int order;
    int size;
    Node nodes;
};

为简洁起见，我省略了链表的实现，但这只是链表的标准实现。

我也得到了以下算法（伪代码）：

L <- topologically sorted list of nodes
V <- empty list of visited nodes
for each node n in L do
    add n to V
    for each node m reachable from n do
        if m in V then L is not sorted

我确实理解拓扑顺序的定义，但我不明白这将如何或为什么会验证拓扑排序。

这个算法如何正确？另外，鉴于上面的图形表示，for each node m reachable from n do 行将如何实现？

此外，是否有比上述算法更好的算法来执行此任务？

Answer 1

基本上这个想法是基于以下事实：

Let L be an ordered sequence of vertices of graph G. Then L is a topological order of graph G if and only if all edges in G points in L to the right. In other words, for each directed edge (L[i], L[j]) we have i < j.

在您提供的方法中，您正在进行上述检查。你检查L中是否有一条边指向左边，从上面的事实我们知道在这种情况下L不是拓扑序。

Answer 2

引用 CLRS：

A topological sort of a dag G = (V,E) is a linear ordering of all its vertices such that if G contains an edge (u,v), then u appears before v in the ordering.

这就是您在最内层的 for 循环中实际检查的内容。如果 m 从 n 可达，但它已经在 V 中，那么这意味着你在访问 n 之前已经访问过 m。因此 L 不是拓扑排序的。

回答你的下一个问题，你可以实现这条线

for each node m reachable from n do

使用 DFS 或 BFS。因此，在节点 n 上，您需要检查是否存在从 n 到 m 的有向边。

验证给定的图节点列表是否是正确的拓扑顺序

Verify that given list of nodes of a graph is a correct topological order

c

algorithm

graph

topological-sort