Не понятно, что получается в итоге.
Прочитал статью. Общий принцип работы понятен, но есть неоднозначности. Например:
- По какому принципу определяется, куда дальше идет алгоритм?
- Как заполняется граф из стека?
Не понятно, что получается в итоге.
Прочитал статью. Общий принцип работы понятен, но есть неоднозначности. Например:
Достаточно просто для понимания представить топологическую сортировку как "удовлетворение зависимостей"; граф в таком случае есть ничто иное как набор зависимостей каждой вершины от каких-либо других.
Например, по той ссылке у нас список зависимостей:
1 : 4
2 :
3 : 2
4 : 2, 3
Суть алгоритма сводится к псевдокоду:
[bool, sorted] TopologicalSort(dependencies)
{
states = new [dependencies.Length];
foreach (var state in states)
{
state = None;
}
var result = [];
for (var vertex in Range(dependencies.Length))
{
if (!Resolve(vertex, dependencies, states))
return [false, []];
}
return [true, result];
}
[bool] Resolve(vertex, dependencies, states, result)
{
if (states[vertex] == InProcess)
return false;
if (states[vertex] == Resolved)
return true;
states[vertex] = InProcess;
foreach (var dep in dependencies[vertex])
{
if (!Resolved(dep, dependencies, states, result))
return false;
}
states[vertex] = Resolved;
result.append(vertex);
return true;
}
т.е. задаём каждой вершине состояние ("цвет"): None - не обрабатывалась, InProcess - в процессе разрешения зависимостей, Resolved - уже добавлена в result.
Тогда если пытаемся разрешить зависимость для вершины "в процессе", то очевидно, что есть циклическая зависимость.
Интересная запись о топологической сортировке есть у Эрика Липперта.
По какому принципу определяется, куда дальше идет алгоритм?
Там же была ссылка, вот: http://habrahabr.ru/blogs/algorithm/66586/ Это — реализация уже не топологической сортировки, а обхода в глубину.
Как заполняется граф из стека?
Честно говоря, не совсем понял смысл вопросов. Если вы хотели узнать, как по стеку восстанавливается граф, то последняя вершина в стеке — вершина, в которую не ведёт ни одно ребро, предпоследняя — вершина, в которую не ведёт ни одно ребро, либо же ведёт ребро из последней, и т.д., вплоть до первой вершины, из которой не выходит ни одно ребро.
Возможно, это не совсем ответ на Ваш вопрос, но думаю это поможет разобраться ссылка.
Но вообще топ.сорт делает следующее: расставляет все вершины ориентированого графа в порядке, что бы все вершины, достижимые из конкретной вершины, следовали строго за ней. И так что бы это свойство выполнялось для всех вершин графа. Как будут располагаться не связные компоненты нам абсолютно не важно, так как в них не существует, взаимнодостежимых узлов.
Задача топологической сортировки (топсорт): дан ориентированный граф с N вершинами и M рёбрами. Требуется перенумеровать его вершины таким образом, чтобы каждое рёбро вело из вершины с меньшим номером в вершину с большим.
Для решения используется обход в глубину (dfs(v), v - вершина из которой запускается обход).
Предположим, что граф ацикличен, т.е. решение существует. Что делает обход в глубину? При запуске из какой-то вершины V он пытается запуститься вдоль всех рёбер, исходящих из V. Вдоль тех рёбер, концы которых уже были посещены ранее, он не проходит, а вдоль всех остальных — проходит и вызывает себя от их концов.
Таким образом, к моменту выхода из вызова dfs(V) все вершины, достижимые из V как непосредственно (по одному ребру), так и косвенно (по пути) — все такие вершины уже посещены обходом. Следовательно, если мы будем в момент выхода из dfs(V) добавлять нашу вершину в начало некоего списка, то в конце концов в этом списке получится топологическая сортировка.
Эти объяснения можно представить и в несколько ином свете, с помощью понятия "времени выхода" обхода в глубину. Время выхода для каждой вершины v — это момент времени, в который закончил работать вызов dfs(v) обхода в глубину от неё (времена выхода можно занумеровать от 1 до N). Легко понять, что при обходе в глубину время выхода из какой-либо вершины всегда больше, чем время выхода из всех вершин, достижимых из неё (т.к. они были посещены либо до вызова dfs(V), либо во время него). Таким образом, искомая топологическая сортировка — это сортировка в порядке убывания времён выхода!!!!
Реализация:
int n; // число вершин
vector<int> g[MAXN]; // граф
bool used[MAXN];
vector<int> ans;
void dfs (int v) {
used[v] = true;
for (size_t i=0; i<g[v].size(); ++i) {
int to = g[v][i];
if (!used[to])
dfs (to);
}
ans.push_back (v);
}
void topological_sort() {
for (int i=0; i<n; ++i)
used[i] = false;
ans.clear();
for (int i=0; i<n; ++i)
if (!used[i])
dfs (i);
reverse (ans.begin(), ans.end());
}