Топологическая сортировка

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

Топологически можно отсортировывать вершины только ациклических орграфов (DAGов).
Реализовать такую сортировку можно как с помощью bfs так и с помощью dfs.

Асимптотика O(M+N).

Листинг C++ (bfs)

bool topsort (vector < vector < int > > e, vector < int > &top)
{
    int i, j;
    int n = e.size ();
    top.resize (n, 0);

    // находим степени по входу для каждой вершины
    vector < int > degree_in (n, 0);
    for (i = 0; i < n; ++ i)
        for (j = 0; j < e[i].size (); ++ j)
            ++ degree_in[e[i][j]];

    // запоминаем все истоки
    queue < int > q;
    for (i = 0; i < n; ++ i)
        if (degree_in[i] == 0)
            q.push (i);

    // поиск в ширину от истоков - пронумеровываем вершины
    int k = 0;
    while (q.size ())
    {
        i = q.front ();
        q.pop ();
        top[k] = i;
        ++ k;

        for (j = 0; j < e[i].size (); ++ j)
        {
            -- degree_in[e[i][j]];
            if (degree_in[e[i][j]] == 0)
                q.push (e[i][j]);
        }
    }
    if (k < n) return false;
    return true;
}

Листинг C++ (dfs)

bool flag_top = 0; // есть ли в графе циклы
void dfs_top (int &v, vector < vector < int > > &e,
        vector < int > &color, vector < int > &top, int &count)
{
    color[v] = 1; // вершина открыта

    for (int i = 0; i < e[v].size (); ++ i)
    {
        int u = e[v][i];

        if (color[u] == 1) // найден цикл
        {
            flag_top = 1;
            return;
        }
        if (color[u] == 0)
            dfs_top (u, e, color, top, count);
    }

    top[-- count] = v;
    color[v] = 2; // вершина закрыта
}

28.05.2007, 15:39

По всем вопросам обращаться: rumterg@gmail.com