2016-04-03 6 views
1

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

На графике представлена ​​в памяти следующим образом:

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?

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

+0

Это не отладки или консультационные услуги.См. [Ask]. – Olaf

+0

@Olaf Я не спрашивал, как реализовать алгоритм, только для объяснения того, почему он работает. Это противоречит правилам? Если это так, я удалю свой пост – JavascriptLoser

+0

Пожалуйста, прочтите мой комментарий еще раз. Я не утверждал, что вы просите об осуществлении. – Olaf

ответ

5

кавычки CLRS:

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

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

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

для каждого узла м достижимых из п делать

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

0

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

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

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

0

Следующий код поможет:

bool Graph::isFollowingOrderAllowed(int *arr, int size) 
{ 
list<int>::iterator i; 
    for (i = adj[4].begin(); i != adj[4].end(); ++i) 
    cout << *i << “\t” ; 
    for(int i = 0 ; i < size-1 ; i++) 
{ 
if(! edgeExist(arr[i] , arr[i+1])) 
return 0 ; 
} 
return 1 ; 
} 

Проверить еще на: http://www.writeulearn.com/topological-sort/