170
правок
Изменения
м
doTopSort<font color=green>// <tex>G</tex> {{---}} исходный граф</font> '''function''' <tex>\mathtt{topologicalSort}(graph G) {:</tex> <tex>fill(\mathtt{visited}, false);</tex> time = 0; '''for (vertex v : ''' <tex>v \in graph V(G) {</tex> '''if (!''' '''not''' <tex>\mathtt{visited}[v]</tex> <tex>\mathtt{dfs}(v) </tex> <tex>\mathtt{ans}.\mathtt{reverse}() </tex> '''function''' <tex>\mathtt{dfs}(vu):</tex> <tex>\mathtt{visited}[u] = true </tex> '''for''' <tex>uv \in E(G);</tex> '''if''' '''not''' <tex>\mathtt{visited}[v] </tex> <tex>\mathtt{dfs}(v) </tex> <tex>\mathtt{ans}.\mathtt{pushBack}(u) </tex>
dfs(vertex u) {
visited[u] = true;
for (vertex v : exists edge uv) {
if (!visited[v]) {
dfs(v);
}
}
topSortAnswer[u] = n - time++;
}
→Алгоритм
Из определения функции <tex>\varphi</tex> мгновенно следует алгоритм топологической сортировки:
Время работы этого алгоритма соответствует времени работы алгоритма поиска в глубину, то есть равно <tex>O(V+E)</tex>.
