Убедитесь, что данный список узлов графа является правильным топологическим порядком

Мне дали задание написать код, который берет список узлов из графа и определяет, находятся ли они в правильном топологическом порядке.

Граф представляется в памяти следующим образом:

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?

Кроме того, есть ли лучший алгоритм, чем приведенный выше, для выполнения этой задачи?


c graph algorithm topological-sort
person JavascriptLoser    schedule 03.04.2016    source источник
comment
Это не отладка или консультационные услуги. См. Как спросить.   -  person too honest for this site    schedule 03.04.2016
comment
@Olaf Я не спрашивал, как реализовать алгоритм, только для объяснения, почему он работает. Это противоречит правилам опроса? Если да, то я удалю свой пост   -  person JavascriptLoser    schedule 03.04.2016
comment
Пожалуйста, прочитайте мой комментарий еще раз. Я не заявлял, что вы просите о реализации.   -  person too honest for this site    schedule 03.04.2016

Ответы (2)


arrow_upward
6
arrow_downward

Цитирую КЛРС:

Топологическим сортом дага G = (V,E) называется такое линейное упорядочение всех его вершин, что если G содержит ребро (u,v), то u стоит перед v в упорядочении.

Это то, что вы на самом деле проверяете в самом внутреннем цикле for. Если m достижимо из n, но уже находится в V, то это означает, что вы уже посетили m до посещения n. Следовательно, L не является топологически отсортированным.

Отвечая на ваш следующий вопрос, вы можете реализовать строку

для каждого узла m, достижимого из n do

с помощью DFS или BFS. Итак, на узле n вам нужно проверить, есть ли направленное ребро, идущее из n в m.

person Community    schedule 03.04.2016

arrow_upward
0
arrow_downward

В основном идея основана на следующем факте:

Пусть L — упорядоченная последовательность вершин графа G. Тогда L — топологический порядок графа G тогда и только тогда, когда все ребра в G указывают в L вправо. Другими словами, для каждого направленного ребра (L[i], L[j]) мы имеем i ‹ j.

В указанном вами методе вы выполняете вышеуказанную проверку. Вы проверяете, есть ли в L ребро, указывающее влево, и из приведенного выше факта мы знаем, что в этом случае L не является топологическим порядком.

person pkacprzak    schedule 03.04.2016