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

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 行？

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

Answer 1

引用 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 的有向边。