拓扑排序 | LSABLOG

首页 » Program » C/C++ » 正文

拓扑排序

http://acm.hdu.edu.cn/showproblem.php?pid=1285

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出 现在v之前。通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。
—————–摘自《百度百科》
简单的说,就是要求一项工程的完成时的先后序列,比如做暑假作业,先数学,再语文,最后英语,这是一种。注意拓扑排序不能有环!
排序方法:
步骤:1、找入度0的点进序列,接着去掉这个点的出边
2、再找入度0的点进序列,接着去掉这个点的出边
3、如此循环直到点都进了序列,如果同时有入度为0的点就随便进一个点到序列
上个hdu题目的解题代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int graph[505][505];
int du[505];

void topological_sort(int n)
{
    int i,j,k,w;
    for (i=1; i<=n; i++) //要遍历n次
        {
            for (j=1; j<=n; j++) //找入度为0的点
                {
                    if (du[j]==0)  //找到了
                        {
                            printf("%d%c",j,i==n?'\n':' ');
                            du[j]--;   //入度变-1表示去掉这个点(已经排序了)
                            k = j;   //记录
                            break;
                        }
                }
            for (w=1; w<=n; w++) //找和k点邻接的点(被k打败过的对手)
                {
                    if (graph[k][w]==1)
                        {
                            // graph[k][w] = 0;   //标记为找过了
                            du[w]--;   //入度-1(表示把k的出度/出边去光了)
                        }
                }
        }
}

int main()
{
    int n,m,x,y;
    while (scanf("%d%d",&n,&m)==2)
        {
            memset(graph,0,sizeof(graph));
            memset(du,0,sizeof(du));
            while (m--)
                {
                    scanf("%d%d",&x,&y);
                    if (graph[x][y]==0)  //x打败y
                        {
                            graph[x][y] = 1;   //在邻接矩阵中记录为1表示不能被同一个对手重复打败
                            du[y]++;   //y被打败过就入度+1
                        }
                }
            topological_sort(n);
        }
    return 0;
}

 

赞 (0)

Comment