2

Не понятно, что получается в итоге.

Прочитал статью. Общий принцип работы понятен, но есть неоднозначности. Например:

  • По какому принципу определяется, куда дальше идет алгоритм?
  • Как заполняется граф из стека?

4 ответа 4

3

Достаточно просто для понимания представить топологическую сортировку как "удовлетворение зависимостей"; граф в таком случае есть ничто иное как набор зависимостей каждой вершины от каких-либо других.

Например, по той ссылке у нас список зависимостей:

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.

Тогда если пытаемся разрешить зависимость для вершины "в процессе", то очевидно, что есть циклическая зависимость.

Интересная запись о топологической сортировке есть у Эрика Липперта.

1

По какому принципу определяется, куда дальше идет алгоритм?

Там же была ссылка, вот: http://habrahabr.ru/blogs/algorithm/66586/ Это — реализация уже не топологической сортировки, а обхода в глубину.

Как заполняется граф из стека?

Честно говоря, не совсем понял смысл вопросов. Если вы хотели узнать, как по стеку восстанавливается граф, то последняя вершина в стеке — вершина, в которую не ведёт ни одно ребро, предпоследняя — вершина, в которую не ведёт ни одно ребро, либо же ведёт ребро из последней, и т.д., вплоть до первой вершины, из которой не выходит ни одно ребро.

1
  • Ничего из того что вы написали понимания не прибавляет. Commented 11 окт. 2011 в 22:54
1

Возможно, это не совсем ответ на Ваш вопрос, но думаю это поможет разобраться ссылка.

Но вообще топ.сорт делает следующее: расставляет все вершины ориентированого графа в порядке, что бы все вершины, достижимые из конкретной вершины, следовали строго за ней. И так что бы это свойство выполнялось для всех вершин графа. Как будут располагаться не связные компоненты нам абсолютно не важно, так как в них не существует, взаимнодостежимых узлов.

1

Задача топологической сортировки (топсорт): дан ориентированный граф с 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());
}

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.