toposort.cpp

图论的一些常用代码

/*
 *功能：拓扑排序，邻接矩阵表示
 *参数：传入图的大小n和邻接阵mat，不相邻点边权为0
 *返回：无法完成排序返回0,否则返回1,ret返回有序点列
 */
#define MAXN 100
int toposort(int n,int mat[][MAXN],int*ret)
{
    int d[MAXN],i,j,k;
    //计算每个顶点的入度
    for (i=0;i<n;i++)
        for (d[i]=j=0;j<n;d[i] += mat[j++][i]);
    for (k=0;k<n;ret[k++]=i)
    {
        //寻找入度为0的顶点
        for (i=0;d[i]&&i<n;i++);
        if (i==n)   //没找到
            return 0;
        //找到后标记为-1，表示访问过
        for (d[i]=-1,j=0;j<n;j++)
            d[j]-=mat[i][j];    //删除这个顶点
    }
}