文章图片标题

拓扑排序(深度优先) C++ 代码

分类:算法与数据结构 作者:阳光倾城 评论:0 点击: 650 次 日期:2016-08-01


拓扑排序(深度优先) C++ 代码

vector<int>g[N];//邻接表存储
int vis[N],topo[N],cnt;
bool dfs(int u)
{
    vis[u] = -1;//-1用来表示顶点u正在访问
    for(int i = 0 ; i < g[u].size() ; i ++)
    {
        if(vis[g[u][i]] == -1)//表示这个点进入了两次,肯定出现了环
            return false;
        else if(vis[g[u][i]] == 0)
        {
            dfs(g[u][i]);
        }
    }
    vis[u] = 1;
    topo[cnt++] = u;//放到结果数组里,输出的时候记得倒序输出,(回溯的原因)
    return true;
}
bool toposort(int n)
{
    memset(vis,0,sizeof(vis));
    for(int i = 1 ; i <= n ; i ++)
    {
        if(!vis[i])
        {
            if(!dfs(i)) return false;//huan
        }
    }
    return true;
}




声明: 除非注明,本文属( 阳光倾城 )原创,转载请保留链接: http://www.tomrrow.com/archives-7857.html