172
правки
Изменения
Нет описания правки
Рассмотрим произвольное ребро <tex>(u, v)</tex>, исследуемое процедурой <tex>dfs</tex>. При исследовании вершина <tex>v</tex> не может быть серой, так как серые вершины в процессе работы <tex>dfs</tex> всегда образуют простой путь в графе, и факт попадания в серую вершину <tex>v</tex> означает, что в графе есть цикл из серых вершин, что противоречит условию утверждения. Следовательно, вершина <tex>v</tex> должна быть белой либо черной. Если вершина <tex>v</tex> — белая, то она становится потомком <tex>u</tex>, так что <tex>leave[u] > leave[v]</tex>. Если <tex>v</tex> — черная, значит, работа с ней уже завершена и значение <tex>leave[v]</tex> уже установлено. Поскольку мы все еще работаем с вершиной <tex>u</tex>, значение <tex>leave[u]</tex> еще не определено, так что, когда это будет сделано, будет выполняться неравенство <tex>leave[u] > leave[v]</tex>. Следовательно, для любого ребра <tex>(u, v)</tex> ориентированного ациклического графа выполняется условие <tex>leave[u] > leave[v]</tex>.
}}
Таким образом, теорема доказана.
}}
== Алгоритм ==
Из определения функции <tex>\varphi</tex> мгновенно следует алгоритм топологической сортировки:
doTopSort(graph G) {
fill(visited, false);
time = 0;
for (Vertex v : v in graph G) {
if (!visited[v]) {
dfs(v);
}
}
}
dfs(u) {
visited[u] = true;
for (Vertex v : exists edge uv) {
if (!visited[v]) {
dfs(v);
}
}
topSortAnswer[u] = n - time++;
}
