拓扑排序 topsort

拓扑排序

　　对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

AOV网

　　在有些工程中，很多子工程(活动)必须在其它有关子工程完成之后才能开始，也就是说，一个子工程的开始是以它的所有前序子工程的结束为先决条件的，我们把这种顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network)，简称AOV网。

　　由AOV网构造出拓扑序列的实际意义是：如果按照拓扑序列中的顶点次序，在开始每一项活动时，能够保证它的所有前驱活动都已完成，从而使整个工程顺序进行，不会出现冲突的情况。

求拓扑序通常使用两种方法：（以下代码可通过UVa 10305）

DFS　求拓扑序

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

int n, m, x, y;

int q[200], t;

bool e[200][200];

short v[300];

bool dfs(int u)

{

    v[u] = -1;

    for (int i = 1; i <= n; ++i)

        if (e[u][i]) if (!v[i] < 0) return false;

            else if (!v[i] && !dfs(i)) return false;

    v[u] = 1;

    q[--t] = u;

    return true;

}

bool top_sort(void)

{

    t = n + 1;

    memset(v, 0, sizeof(v));

    for (int i = 1; i <= n; ++i)

        if (!v[i]) if (!dfs(i)) return false;

    return true;

}

int main()

{

    while (cin >> n >> m && n)

    {

        memset(e, false, sizeof(e));

        memset(ind, 0, sizeof(ind));

        for (int i = 1; i <= m; ++i)

        {

            scanf("%d%d", &x, &y);

            e[x][y] = true;

        }

        if (top_sort())

            for (int i = 1; i <= n; ++i)

                printf("%d ", q[i]);

        else printf("-1");

        printf("\n");

    }

}

BFS　求拓扑序

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

int n, m, x, y;

int q[200];

int ind[200];

bool e[200][200];

void top_sort(void)

{

    int h = 1, t = 0;

    for (int i = 1; i <= n; ++i)

        if (ind[i] == 0)

            q[++t] = i;

    while (h <= t)

    {

        int u = q[h++];

        for (int i = 1; i <= n; ++i)

            if (e[u][i])

            {

                --ind[i];

                if (ind[i] == 0)

                    q[++t] = i;

            }

    }

    for (int i = 1; i <= n; ++i)

        printf("%d ", q[i]);

        printf("\n");

}

int main()

{

    while (cin >> n >> m && n)

    {

        memset(e, false, sizeof(e));

        memset(ind, 0, sizeof(ind));

        for (int i = 1; i <= m; ++i)

        {

            scanf("%d%d", &x, &y);

            e[x][y] = true;

            ++ind[y];

        }

        top_sort();

    }

}

巴特西

拓扑排序 topsort

最新文章

热门文章