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

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

引用CLRS:

拓扑类型的dag G =(V,E)是其所有顶点的线性排序,这样如果G包含边(u,v),则u在排序中出现在v之前.

这是你在最里面的for循环中实际检查的内容.如果m可以从n到达,但它已经在V中,那么这意味着你在访问n之前已经访问了m.因此L不是拓扑排序的.

回答你的下一个问题,你可以实现这一行

对于可从n执行的每个节点

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