精华内容
下载资源
问答
  • 拓扑排序实例

    2013-06-21 04:28:00
    拓扑排序实例 转载于:https://www.cnblogs.com/LoveFishC/p/3845908.html
    拓扑排序实例

    转载于:https://www.cnblogs.com/LoveFishC/p/3845908.html

    展开全文
  • 本题主要运用拓扑排序来解题,将每个队伍作为一个节点,如果两个队友有比赛,胜者作为负者的入度。如果负者输于多个队伍,则进行入度加运算,如果出去的是它的入度,则进行入度减一运算,每次取入度为0,切编号小的...
    本题主要运用拓扑排序来解题,将每个队伍作为一个节点,如果两个队友有比赛,胜者作为负者的入度。如果负者输于多个队伍,则进行入度加运算,如果出去的是它的入度,则进行入度减一运算,每次取入度为0,切编号小的数。即按顺序遍历所有节点,发现入读为0且未排序的节点。即中止此次遍历,对其进行出栈,处理 并将与其相邻的节点的入度-1.用if(i==n)来做防止图有回路。下面是具体代码实现:(已AC
    
    <span style="font-size:18px;">import java.util.Scanner;
    
    public class Main{
        static int n;
        static int m;
        static int degre[];//入度数
        static int sorted[];//是否排序。0未排,1已排
        static int arc[][];//胜负结果数组
        static Scanner sc=new Scanner(System.in);
        public static void main(String[] args) {
            while(sc.hasNext()){
                n=sc.nextInt();
                m=sc.nextInt();
                init();
                topoSort();
            }
        }
        private static void topoSort() {
            int s=0;//已排序的节点数
            while(s<n){
                int i=0;
                //按顺序遍历所有节点,发现入读为0且未排序的节点。即中止此次遍历,对其进行出栈,处理 并将与其相邻的节点的入度-1.
                for(i=0;i<n;i++){
                    if(degre[i]==0&&sorted[i]==0){
                        break;
                    }
                }
                if(i==n){
                    System.out.println("图有回路,无解");
                    return;
                }
                //对for循环中找的节点i进行处理
                sorted[i]=1;
                s++;
                System.out.print(i+1);
                if(s<n){
                    System.out.print(" ");
                }
                for(int j=0;j<n;j++){
                    if(arc[i][j]!=0){
                        degre[j]--;//把以i节点 为起点 节点j的入度-1;
                    }
                }
            }
            System.out.println();
        }
        
        private static void init() {
            
            //数组初始化
            sorted=new int[n];
            degre=new int[n];
            arc=new int[n][n];
            for (int i = 0; i < n; i++) {
                sorted[i]=0;
                degre[i]=0;
                for (int j = 0; j <n; j++) {
                    arc[i][j]=0;
                }
            }
            
            //每场比赛胜负的输入
            for (int i = 0; i < m; i++) {
                int a=sc.nextInt()-1;
                int b=sc.nextInt()-1;
                if (arc[a][b]==0) {//防护有重复边
                    arc[a][b]=1;//节点a与节点b有连通
                    degre[b]++;//节点b的入度+1
                }
                
            }
        }
    
    }</span>

    展开全文
  • 拓扑排序

    2019-07-16 20:43:22
    一个有向无环图的拓扑排序:(直接看实例) 怎么用代码实现:从上图中可以看出,拓扑排序每次输出的都是没有其他节点指向它的结点,即入度为0的点,所以我们将每个点的入度都记录下来,每次输出入度为0的点就可以...

    参考:拓扑排序和并查集

    在图论中,拓扑排序是一个有向无环图(DAG)的所有顶点的线性序列。通常,一个有向无环图可以有一个或多个拓扑排序序列。

    一个有向无环图的拓扑排序:(直接看实例)
    在这里插入图片描述
    怎么用代码实现:从上图中可以看出,拓扑排序每次输出的都是没有其他节点指向它的结点,即入度为0的点,所以我们将每个点的入度都记录下来,每次输出入度为0的点就可以了,同时将这个点所指的点的入度减一

    记录入度:

    vector<int>a[600];//存边
    
    memset(c,0,sizeof(c));
    for(int i=1; i<=n; i++)
    {
        scanf("%d%d",&p1,&p2);
        a[p1].push_back(p2);
        c[p2]++;//记录入度
    }
    

    例题1:确定比赛名次
    主要是题目中要求每次都是输出编号最小的队伍,可以直接遍历找编号最小的且入度为0的点,也可以借用优先队列

    用邻接矩阵存边:
    一开始就卡在第20行——if(!mp[p1][p2])——了,不过一条边可以输入两次!?????

    #include <iostream>
    #include <stdio.h>
    #include <string.h>
    #include <queue>
    using namespace std;
    const int maxn=510;
    const int INF=0x3f3f3f3f;
    priority_queue<int,vector<int>,greater<int> >qu;
    int main()
    {
        int n,m,c[600],p1,p2,mp[600][600];
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            memset(c,0,sizeof(c));
            memset(mp,0,sizeof(mp));
            int flag=n;
            for(int i=1; i<=m; i++)
            {
                scanf("%d%d",&p1,&p2);
                if(!mp[p1][p2])
                {
                    mp[p1][p2]=1;
                    c[p2]++;
                }
            }
            for(int i=1; i<=n; i++)
            {
                if(!c[i])
                    qu.push(i);
            }
            while(flag--)
            {
                int net=qu.top();
                qu.pop();
                if(flag)
                    printf("%d ",net);
                else
                    printf("%d\n",net);
                for(int j=1; j<=n; j++)
                    if(mp[net][j]==1)
                    {
                        c[j]--;
                        if(!c[j])
                            qu.push(j);
                    }
            }
        }
    }
    
    

    也可以用vector和邻接表存/黑脸
    例题2:Reward

    //存个反向边就行了,剩下的就是套模板
    #include<stdio.h>
    #include<string.h>
    #include<string>
    #include<iostream>
    #include<algorithm>
    #include<math.h>
    #include<set>
    #include<stack>
    #include<vector>
    #include<map>
    #include<queue>
    using namespace std;
    const int manx=4e4+10;
    const int INF=0x3f3f3f3f;
    int n,m,c[manx],head[manx],cou,a[manx];
    struct node
    {
        int e,bf;
    } edge[manx];
    void add(int s,int e)
    {
        edge[cou]=node{e,head[s]};
        head[s]=cou++;
    }
    int main()
    {
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            cou=0;
            queue<int>qu;
            int s,e,ans=0,flag=n;
            memset(head,-1,sizeof(head));
            memset(c,0,sizeof(c));
            for(int i=0; i<m; i++)
            {
                scanf("%d%d",&e,&s);
                add(s,e);
                c[e]++;
            }
            for(int i=1; i<=n; i++)
                if(!c[i])
                {
                    a[i]=888;
                    ans+=a[i];
                    qu.push(i);
                    flag--;
                }
            while(!qu.empty())
            {
                int sx=qu.front();
                qu.pop();
                for(int i=head[sx]; ~i; i=edge[i].bf)
                {
                    int nx=edge[i].e;
                    c[nx]--;
                    if(!c[nx])
                    {
                        a[nx]=a[sx]+1;
                        ans+=a[nx];
                        qu.push(nx);
                        flag--;
                    }
                }
            }
            if(!flag)
                printf("%d\n",ans);
            else
                printf("-1\n");
        }
    
    }
    
    展开全文
  • 拓扑排序概念

    千次阅读 2018-12-27 22:43:41
    拓扑排序,顾名思义,就是一种排序方法。这是一种什么排序?这种排序的作用?然后怎么去实现这种排序算法?现在就让我们仔细研究下。 1、什么是拓扑排序,也就是拓扑排序的概念 实际上,拓扑排序是一种图论算法,...

    拓扑排序,顾名思义,就是一种排序方法。这是一种什么排序?这种排序的作用?然后怎么去实现这种排序算法?现在就让我们仔细研究下。

    1、什么是拓扑排序,也就是拓扑排序的概念

    实际上,拓扑排序是一种图论算法,该算法在《数据结构与算法》一书中有涉猎。引用维基百科的定义:

    在图论中,由一个有向无环图的顶点组成的序列,当且仅当满足下列条件时,称为该图的一个拓扑排序(英语:Topological sorting)。
    (1)每个顶点出现且只出现一次;
    (2)若A在序列中排在B的前面,则在图中不存在从B到A的路径。
    也可以定义为:拓扑排序是对有向无环图的顶点的一种排序,它使得如果存在一条从顶点A到顶点B的路径,那么在排序中B出现在A的后面。

    是不是觉得看完概念还是很晕的感觉,下面就用一个实例来讲具体的拓扑排序样例。

    (a)有向图网(AOV)  (b)输出v6后       (c)输出v1后    (d)输出v4后 (e)输出v3后 (f)输出v2后

                                                               输出排序结果:v6-v1-v4-v3-v2-v5

    此拓扑排序的思想是:

    (1)从有向图中选取一个没有前驱的顶点,并输出之;

    (2)从有向图中删去此顶点以及所有以它为尾的弧;

    重复上述两步,直至图空,或者图不空但找不到无前驱的顶点为止。没有前驱 -- 入度为零,删除顶点及以它为尾的弧-- 弧头顶点的入度减1。

    何谓入度?

    我觉得得先明白什么是度?度(Degree):一个顶点的度是指与该顶点相关联的边的条数,顶点v的度记作d(v)。

    入度:对于有向图来说,一个顶点的度可细分为入度和出度。一个顶点的入度是指与其关联的各边之中,以其为终点的边数。

    出度:出度则是相对的概念,指以该顶点为起点的边数。

    以v6这个顶点为例,它的入度为0,出度为2。

    以v5这个顶点为例,它的入度为3,出度为0。

    以v4这个顶点为例,它的入度为2,出度为1。

    以v3这个顶点为例,它的入度为1,出度为2。

    以v2这个顶点为例,它的入度为2,出度为0。

    以v1这个顶点为例,它的入度为0,出度为3。

    经验证,一个有向五环图中所有顶点的入度之和(0+3+2+1+2+0=8)等于所有顶点的出度之和(2+0+1+2+0+3=8)。

    2、拓扑排序的作用

    不禁有人就问了,有很多排序算法啊,快速排序,插值排序,这个排序到底有什么优点呢?平常这种排序又用于哪种场景呢?

    我们说快速排序是不稳定的,这是因为最后的快排结果中相同元素的出现顺序和排序前不一致了。如果用偏序的概念可以这样解释这一现象:相同值的元素之间的关系是无法确定的。因此它们在最终的结果中的出现顺序可以是任意的。而对于诸如插入排序这种稳定性排序,它们对于值相同的元素,还有一个潜在的比较方式,即比较它们的出现顺序,出现靠前的元素大于出现后出现的元素。因此通过这一潜在的比较,将偏序关系转换为了全序关系,从而保证了结果的唯一性。而拓扑排序就是一种将偏序转换为全序的一种算法。

    这里要补充两个概念,偏序和全序?

    偏序:有向图中两个顶点之间不存在环路,至于连通与否,是无所谓的。

    全序:就是在偏序的基础之上,有向无环图中的任意一对顶点还需要有明确的关系(反映在图中,就是单向连通的关系,注意不能双向连通,那就成环了)。

    意思就是讲,一个不确定的偏序关系经全序后就有一种确定的先后顺序了。

    既然有先后,那么在实际生活中的选课问题,比如大一时一定要修完这门课,大二才学第二门课,这种排课问题就是拓扑排序问题。
     

    转载至:https://blog.csdn.net/Jasmine_shine/article/details/43488895

    展开全文
  • 数据结构实习题目:拓扑排序实现学生排课 结构简单,易懂。也很实用。拓扑排序实现学生排课
  • 本文将介绍活动网络的基础知识,并用C++实现拓扑排序(Topological Sort)和关键路径(Critical Path)。
  • 拓扑排序 几乎在所有的项目,甚至日常生活,待完成的不同任务之间通常都会存在着某些依赖关系,这些依赖关系会为它们的执行顺序行程表部分约束。对于这种依赖关系,很容易将其表示成一个有向无环图(Directed ...
  • 既然是一种排序,那么肯定是按照某种规则进行排序,那么这么想的话,先了解基本知识,再来实战演练 1. AOV网(Activity On Vertex Network)【顶点——表示活动】 是一个——有向无回路的图 顶点——表示活动 用弧...
  • 拓扑排序的原理及实现

    万次阅读 多人点赞 2017-08-05 14:06:27
    拓扑排序,顾名思义,就是一种排序方法。这是一种什么排序?这种排序的作用?然后怎么去实现这种排序算法?现在就让我们仔细研究下。1、什么是拓扑排序,也就是拓扑排序的概念 实际上,拓扑排序是一种图论算法,该...
  • python拓扑排序

    2018-03-12 19:30:32
    发现自己并没有真的理解拓扑排序,再次学习了下 拓扑排序要满足如下两个条件 每个顶点出现且只出现一次。 若A在序列中排在B的前面,则在图中不存在从B到A的路径。 拓扑排序算法 任何无回路的顶点活动网...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,529
精华内容 3,811
关键字:

拓扑排序实例