拓扑排序

淡淡的烟草味﹌ 2022-06-09 05:58 326阅读 0赞

C++版本实现

/*以邻接矩阵Edge[A][B]=N存放图信息：A指向B，权值为N*/
    /*假设不相连的边的Edge==INT_MAX*/
    void Topo()
    {
        sort(Edge+1,Edge+N+1);
        for (int i=1; i<=N; i++)
        {
            int j;
            for (j=1; j<=N; i++)  //vis为标记数组，标记是否已经存在在Topo数组中
                if (!vis[j]&&!in[j]) //in数组表示的下标顶点的入度
                {
                    Topo[i]=j;
                    vis[j]=1;
                    break;
                }
            for (int k=1;k<=N;k++) //将与j点相连的顶点的入度刷新
                if (Edge[j][k]!=INT_MAX)
                    in[k]--;
        }
    }

拓扑排序并不一定唯一，有时会要求顶点数值大的尽量在前，这个时候应该 反向建图 ，再进行拓扑排序，来保证更多小数值顶点在后面

拓扑排序每次选择一个顶点进入序列后，要更新所有与这个顶点相连的顶点的入度。而上面的代码全是把所有的顶点都遍历了一边。

这里可以使用邻接表或者链式前向星这一类数据结构来优化，来记录图的信息，可以做到只遍历与该顶点相连的顶点。

/*优先队列+邻接表实现拓扑排序*/
    void Topo()
    {
        priority_queue<int> que;
        for (int i=1; i<=N; i++) //将入度为零的顶点压入队列
            if (dis[i]==0)
                que.push(i);
        int p=N+1;
        while (!que.empty())
        {
            int tmp=que.top();
            que.pop();
            topo[--p]=tmp;     //存入topo数组
            int z=first[tmp];
            while (z!=-1)       //邻接表遍历与tmp相连的顶点
            {
                dis[end[z]]--; //入度减一
                if(!dis[end[z]]) que.push(end[z]);
                z=next[z];
            }
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，326人围观）

还没有评论，来说两句吧...

相关阅读

相关拓扑排序

在这里我们引入AOV（Activity-On-Vertex）网，图的顶点代表活动，其有向边<Vi,Vj>代表完成Vj之前Vi必须先完成。对于一个工程，我们首先将这

野性酷女/ 2022年06月10日 13:28/ 0 赞/ 198 阅读

相关拓扑排序

C++版本实现 /以邻接矩阵Edge[A][B]=N存放图信息：A指向B，权值为N/ /假设不相连的边的Edge==INT_MAX/ void

淡淡的烟草味﹌/ 2022年06月09日 05:58/ 0 赞/ 327 阅读

相关拓扑排序

什么是拓扑排序? 在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序

冷不防/ 2022年06月09日 05:57/ 0 赞/ 186 阅读

相关拓扑排序

拓扑排序一个较大的工程往往被划分成许多子工程，我们把这些子工程称作活动(activity)。在整个工程中，有些子工程(活动)必须在其它有关子工程完成之后才能开始，也就

小鱼儿/ 2022年04月10日 08:23/ 0 赞/ 212 阅读

相关拓扑排序

（1）有向无环图无环的有向图，简称 DAG (Directed Acycline Graph) 图。有向无环图在工程计划和管理方面的应用：除最简单的情况之外，几

古城微笑少年丶/ 2022年03月18日 12:35/ 0 赞/ 246 阅读

相关拓扑排序

拓扑排序：拓扑排序是根据离散数学中有关偏序与全序定义的。 ![0_1314168765l7fq.gif][] 若一个集合 X 上的关系 R 是自反的反

淩亂°似流年/ 2021年12月23日 02:43/ 0 赞/ 296 阅读

相关拓扑排序

拓扑排序题目做的烦，题解写着玩 [POJ 2762 Going from u to v or from v to u?][POJ 2762 Going from

谁借莪１个温暖的怀抱￠/ 2021年12月20日 16:11/ 0 赞/ 242 阅读

相关拓扑排序

拓扑排序源代码测试1 输入输出测试2 输入输出源代码 include<bits/

古城微笑少年丶/ 2021年12月05日 14:53/ 0 赞/ 263 阅读

相关拓扑排序

一个较大的工程往往被划分成许多子工程，我们把这些子工程称作活动(activity)。在整个工程中，有些子工程(活动)必须在其它有关子工程完成之后才能开始，也就是说，一个子工程

野性酷女/ 2021年09月19日 05:04/ 0 赞/ 404 阅读

相关拓扑排序

作用：判断是否存在环 1.数组模拟队列 include <iostream> include <vector> include <cst

喜欢ヅ旅行/ 2021年06月22日 15:37/ 0 赞/ 477 阅读