Мне поручено написать код, который принимает список узлов из графика и определяет, находятся ли они в правильном топологическом порядке.Убедитесь, что данный список узлов графа является правильным топологическим порядком.
На графике представлена в памяти следующим образом:
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
?
Кроме того, существует ли лучший алгоритм, чем описанный выше для выполнения этой задачи?
Это не отладки или консультационные услуги.См. [Ask]. – Olaf
@Olaf Я не спрашивал, как реализовать алгоритм, только для объяснения того, почему он работает. Это противоречит правилам? Если это так, я удалю свой пост – JavascriptLoser
Пожалуйста, прочтите мой комментарий еще раз. Я не утверждал, что вы просите об осуществлении. – Olaf