精华内容
下载资源
问答
  • 对下面的有向图进行拓扑排序
    千次阅读
    2021-02-05 16:40:24

    思路:

    用数组模拟链表,首先如果能用拓扑排序则其一定是有向无环图。
    所以我们应该先找到其入度为0的点。然后将其入队,并将与此点相连的边全部删去。最后当队尾指针是n-1时说明一共入队n个元素说明此图是有向无环图。存在拓扑排序。
    注意:h[i]中存储的是元素在e[]中的下标。

    问题描述

    给定一个n个点m条边的有向图,点的编号是1到n,图中可能存在重边和自环。

    请输出任意一个该有向图的拓扑序列,如果拓扑序列不存在,则输出-1。

    若一个由图中所有点构成的序列A满足:对于图中的每条边(x, y),x在A中都出现在y之前,则称A是该图的一个拓扑序列。

    输入格式

    第一行包含两个整数n和m

    接下来m行,每行包含两个整数x和y,表示存在一条从点x到点y的有向边(x, y)。

    输出格式

    共一行,如果存在拓扑序列,则输出任意一个合法的拓扑序列即可。

    否则输出-1。

    数据范围

    1≤n,m≤105
    输入样例:
    3 3
    1 2
    2 3
    1 3
    输出样例:
    1 2 3

    代码

    #include<iostream>
    #include<cstring>
    using namespace std;
    const int N = 100010;
    int e[N], ne[N], h[N], idx = 0;
    int q[N], d[N];    
    int n = 0, m = 0;
    void add(int a, int b){
        e[idx] = b, ne[idx] = h[a], h[a] = idx++;
    }
    
    bool toposort()
    {
        
        int hh = 0, tt = -1;
        for (int i = 1; i <= n; ++ i){
            if (!d[i]){
                q[++ tt] = i;
            }
        }
        while(hh <= tt){
            int t = q[hh++];
            for(int i = h[t]; i != -1; i = ne[i]){
                d[e[i]]--;
                if(!d[e[i]])
                    q[++tt] = e[i];
            }
        }
        return tt == n-1;
    }
    
    int main(){
        cin >> n >> m;
        int a, b;
        memset(h, -1, sizeof h);
        for(int i = 0; i < m; ++i){
            cin >> a >> b;
            add(a, b);
            d[b]++;
        }
        if(toposort()){
            for(int i = 0; i <= n - 1; ++i){
                cout << q[i] << " ";
            }
        }else{
            cout << "-1" << endl;
        }
        return 0;
    }
    

    原题链接

    更多相关内容
  • 有向图拓扑排序

    2014-08-03 01:17:10
    对于有向图进行拓扑排序,图使用邻接矩阵的存储结构。
  • 有向图拓扑排序

    千次阅读 2021-05-27 21:22:40
    有向图拓扑排序 前言 本文介绍有向图拓扑排序算法的思路及代码实现,首先讲解什么是拓扑排序,其次介绍实现拓扑排序需要的检测有向图是否有环的算法及顶点排序算法,最终实现有向图的拓扑排序。 一、什么是拓扑排序...

    有向图拓扑排序

    前言

    本文介绍有向图拓扑排序算法的思路及代码实现,首先讲解什么是拓扑排序,其次介绍实现拓扑排序需要的检测有向图是否有环的算法及顶点排序算法,最终实现有向图的拓扑排序。

    一、什么是拓扑排序?

    • 给定一副有向图,将所有的顶点排序,使得所有的有向边均从排在前面的元素指向排在后面的元素,此时就可以明
      确的表示出每个顶点的优先级。如对下图进行拓扑排序:
      在这里插入图片描述
    • 拓扑排序结果为:
      在这里插入图片描述
    • 根据拓扑排序的概念,如果对有向图进行拓扑排序,那么图中必须没有环,否则,就不能进行拓扑排序,然后在图中无环的情况下,再进行顶点排序,最终实现拓扑排序。

    二、检测有向图中是否有环

    • 算法思路:基于深度优先搜索算法检测图中是否有环。1. 定义boolean辅助数组onStack,以栈的思想标识顶点是否在搜索中;2. 在深度优先搜索中,不断检测当前搜索的顶点是否在栈中(即当前顶点的值是否为true,如果为true,则在栈中,否则不在栈中),如果在栈中,说明该顶点被重复搜索到,代表图中有环;3. 每个顶点深度优先搜索完成,onStack需要出栈(即将当前索引对应的值修改为false),为下个顶点搜索做准备
    • 示例:
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
    • 代码实现
    public class DirectedCycle {
        private boolean[] marked;//索引代表顶点,用于标识顶点是否搜索过,是深度优先搜索的复杂数组
        private boolean hasCycle;//记录图中是否有环
        private boolean[] onStack; //索引代表顶点,使用栈的思想,记录当前顶点有没有已经处于正在搜索的栈上,如果有,则证明有环。
    
        //创建一个检测环对象,检测图G中是否有环
        DirectedCycle(DirectGraph G)
        {
            this.marked=new boolean[G.V()];//用于标识顶点是否搜索过
            this.hasCycle=false;
            this.onStack=new boolean[G.V()];//用于标识顶点是否在搜索中
    
            //遍历所有顶点,将未搜索过的顶点作为入口,进行深度优先遍历,检测是否有环,一旦检测到有环,则结束;
            //因为对于不连通图,有很多个子图,也许某个子图存在环,因此,要对每个子图进行深度优先遍历检测,而不能只检测某一个子图。
            for (int v = 0; v < G.V(); v++) {
                if (!marked[v])
                    dfs(G,v);//每次搜索一个子图,判断子图内是否有环,如果没环,继续搜索下一个子图(一次搜索后,未搜索的顶点一定在另一个子图中)
            }
        }
    
        //基于深度优先搜索,检测图G中是否有环
        private void dfs(DirectGraph G,int v)
        {
            //1.当前顶点标记为已搜索
            marked[v]=true;
            //2.当前顶点入栈
            onStack[v]=true;
            //3.递归深度优先遍历,检查遍历结点是否已经在栈中,如果在栈中,则表明该顶点被两次搜索到,证明有环,则结束
            for (Integer w : G.adj(v)) {
                if (!marked[w])
                    dfs(G,w);
                //如果该顶点已经被搜索过,且如果该顶点在搜索的路径上,则代表又一次搜索到该顶点,证明有环,结束搜索。
                if (onStack[w]) {
                    hasCycle = true;
                    return;
                }
            }
            //4.当前顶点出栈,为下一个节点作为入口,检测是否有环做准备(为什么需要这样,图2.png可以解释)
            onStack[v]=false;
        }
        //判断当前有向图G中是否有环
        public boolean hasCycle()
        {
            return hasCycle;
        }
    }
    

    代码中为什么每个顶底深度优先搜索完成后onStack需要出栈,下图可以解释:
    在这里插入图片描述

    三、基于深度优先的顶点排序

    • 拓扑排序使得所有的有向边均从排在前面的元素指向排在后面的元素,要实现这一需要,可以通过顶点排序进行实现。
    • 顶点排序算法思路:1. 定义栈stack用于存储顶点排序的结果;2. 基于深度优先搜索算法,每个顶点深度优先搜索完成后,将该顶点入栈;3. 依次弹出栈中顶点,即为满足拓扑排序要求的顶点序列。
    • 顶点排序示例:
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
    • 代码实现
    public class DepthFirstOrder {
        private boolean[] marked;//索引代表顶点,值表示当前顶点是否已经被搜索
        private Stack<Integer> reversePost;//使用栈,存储顶点序列,打印出栈中的顶点,即是排序后的顶点
    
        public DepthFirstOrder(DirectGraph G)
        {
            //初始化辅助变量
            this.marked=new boolean[G.V()];//默认全部赋值为false
            this.reversePost=new Stack<Integer>();
            //对每一个未搜索过的顶点进行深度优先遍历
            for (int v = 0; v < G.V(); v++) {
                if (!marked[v])
                    dfs(G,v);
            }
        }
    
        //基于深度优先搜索,生成顶点线性序列
        private void dfs(DirectGraph G,int v)
        {
            //1. 将当前顶点标记为已搜索
            marked[v]=true;
            //2. 遍历当前顶点的邻接表,对邻接表中未搜索的顶点递归调用深度优先搜索
            for (Integer w : G.adj(v)) {
                if(!marked[w])
                    dfs(G,w);
            }
            //3. 当前顶点v深度优先搜索完毕后,入栈
            reversePost.push(v);
        }
        //获取顶点线性序列
        public Stack<Integer> reversePost()
        {
            return reversePost;
        }
    }
    

    四、拓扑排序实现

    • 实现了检测是否有环和顶点排序算法,也就完成了拓扑排序,拓扑排序是对上面两个算法的封装。
    • 拓扑排序算法步骤:1. 定义栈用于存储拓扑排序顶底;2. 检测图中是否有环;3. 若有环则不做拓扑排序,若无环则对图进行顶点排序,完成拓扑排序
    • 代码实现
    public class TopoLogical {
        private Stack<Integer> order; //顶点的拓扑排序
    
        public TopoLogical(DirectGraph G)
        {
            //1. 检测是否有环
            DirectedCycle directedCycle = new DirectedCycle(G);
            if (!directedCycle.hasCycle())
            {
                //2. 调用顶点排序算法
                DepthFirstOrder depthFirstOrder = new DepthFirstOrder(G);
                this.order=depthFirstOrder.reversePost();
            }
        }
    
        //判断图G是否有环
        public boolean isCycle()
        {
            return order==null;
        }
        //获取拓扑排序的所有顶点
        public Stack<Integer> order()
        {
            return order;
        }
    }
    
    展开全文
  • 数据结构课程设计:有向图拓扑排序算法的实现.docx
  • PAGE 数据结构课程设计 设计说明书 有向图拓扑排序算法的实现 学生姓名 樊佳佳 学号 1318064017 班级 网络工程1301 成绩 指导教师 申静 数学与计算机科学学院 2016年1月4日 课程设计任务书 20152016学年第一学期 ...
  • 有向图拓扑排序

    万次阅读 2018-10-20 23:06:53
    有向图 在无向图中,边没有方向,两条边之间的顶点是单向可达...对有向图的结构定义如下: #include <map> #include <forward_list> using namespace std; struct DirectedGraph { size_t V, E;...

    有向图

    无向图中,边没有方向,两条边之间的顶点是单向可达的,而有向图的边是单向的。虽然边的性质不同,但我们仍然可以用邻接表来表示有向图。对有向图的结构定义如下:

    #include <map>
    #include <forward_list>
     
    using namespace std;
     
    struct DirectedGraph
    {
        size_t V, E; //V表示顶点数,E表示边数
        map<int, forward_list<int>> adj; //邻接表
    };
    

    有向图在计算机中有广泛的应用,如任务调度条件、网络等。有向图的顶点之间的联系是描述现实世界的有利工具,如计算机的任务调度系统中,根据多任务之间的先后关联需要给出任务的执行顺序,拓扑排序就是可以得到这一顺序的算法。

    拓扑排序

    给定一幅有向图,将所有的顶点排序,使得所有的有向边均从排在前面的元素指向排在后面的元素(或者说明无法做到这一点)。

    还是以任务调度系统为例,假设一个任务x必须在任务y之前完成,任务y必须在任务z之前完成,任务z又必须在任务x之前完成,这样的问题肯定是无解的。也就是说,拓扑排序能得出结果的前提是图必须是有向无环图(Directed Acyclic Graph,DAG),即一幅不含有环路的有向图。

    一种拓扑排序的思想是基于深度优先搜索的顶点排序。它的基本思想是深度优先搜索会沿着开始顶点一直向下搜索,且正好只会访问每个顶点一次。基于深度优先搜索的拓扑排序基于一个重要命题:一幅有向图的拓扑顺序即为所有顶点的逆后序排列。所谓逆后序遍历即在路径达到最大深度后再保存(打印)顶点,得到后序遍历,将其逆向输出即可。

    下面是基于深度优先搜索来得到拓扑排序后的顶点顺序(默认无环,因此未给出判断是否存在有向环的代码):

    void dfs(DirectedGraph &g, vector<int> &visited, stack<int> &st, int v)
    {
        visited[v] = 1;
        for (int &i : g.adj[v])
        {
            if (!visited[v])
            {
                dfs(g, visited, st, i);
            }
        }
        st.push(v);
    }
    
    void TopologicalSort(DirectedGraph &g, int v)
    {
        stack<int> st;
        vector<int> visited(g.V);
        dfs(g, visited, st, v);
        while (!st.empty())
        {
            cout << st.top() << " ";
            st.pop();
        }
    }

    另一种思路是得到所有顶点的入度,循环执行以下两个步骤直到不存在入度为0的顶点:

    (1)选择一个入度为0的顶点,输出

    (2)将该顶点其出边全部删除,同时更新出边所到达顶点的入度

    这种算法不需要太多代码判断是否存在有向环,只要最后输出的顶点数小于有向图的顶点数就说明了存在有向环。

    bool TopologicalSort(DirectedGraph &g, vector<int> &in_degree)
    {
        queue<int> qu;
        int cnt = 0;
        for (auto ite = in_degree.begin(); ite != end(); ++ite)
        {
            if (0 == *ite)
            {
                qu.push(*ite);
            }
        }
        while (!qu.empty())
        {
            int v = qu.front();
            qu.pop();
            cout << v << " ";
            ++cnt;
            for (const int &i : g.adj.at(v))
            {
                if (0 == --in_degree[i])
                {
                    qu.push(i);
                }
            }
        }
        return cnt < V ? false : true;
    }

     

    展开全文
  • 拓扑排序的作用,就是帮我们判断一个有向图是否有回路出现。 2. 拓扑排序的思想 其实拓扑排序的思想很简单: (1)在有向图中选择一个没有前驱(入度为0)的顶点输出; (2)从图中删除该顶点和所有以它为尾的弧;...

    1. 拓扑排序的用处

    对于有向图,我们有时候需要确保没有回路出现,如下面的例子:

    在这里插入图片描述
    学生学习的课程之间的优先关系构成了一个有向图,显然,该有向图不能出现回路,毕竟哪个学生也不想一直循环学习某几门课程不毕业。

    P.s:这种用顶点表示活动,有向边表示活动之间的关系的有向图成为AOV网。

    而拓扑排序的作用,就是帮我们判断一个有向图是否有回路出现。

    2. 拓扑排序的思想

    其实拓扑排序的思想很简单:

    (1)在有向图中选择一个没有前驱(入度为0)的顶点输出;

    (2)从图中删除该顶点和所有以它为尾的弧;

    (3)重复(1)、(2)两步,直至全部顶点均已输出,或者当前图中不存在无前驱的顶点为止。

    若所有顶点都被输出,则说明原有向图中没有回路;否则,说明有回路。

    【举例】

    在这里插入图片描述

    3. 代码实现

    代码实现也很简单,首先基于邻接表构造有向图,注意每个顶点结构体中需要加入一项int InDgree 表示该顶点的入度数(因为要把入度为0的顶点删除)。

    我用的是栈来暂时存储删除的顶点,其实用队列或者别的容器都行,只是为了临时存储。

    #include <iostream>
    #include <stack>
    #define MAX_VERTEX_NUM 20
    #define OK 1
    #define ERROR 0
    using namespace std;
    typedef char NumType;
    typedef int Status;
    
    //下面是邻接表构造有向图过程
    struct ArcNode
    {
        int AdjVex;
        ArcNode *NextArc;
    };
    struct VexNode
    {
        NumType data;
        int InDegree;
        ArcNode *FirstArc;
    };
    struct ALGraph
    {
        VexNode Vex[MAX_VERTEX_NUM];
        int VexNum;
        int ArcNum;
    };
    int Locate(ALGraph G,NumType v)
    {
        int i;
        for(i=0;i<G.VexNum;i++)
            if(v==G.Vex[i].data)return i;
        return -1;
    }
    void CreatALGraph(ALGraph &G)
    {
        cout<<"请输入顶点数和弧数:"<<endl;
        cin>>G.VexNum;cin>>G.ArcNum;
        int i;
        cout<<"请输入顶点数据:"<<endl;
        for(i=0;i<G.VexNum;i++)
        {
            cin>>G.Vex[i].data;
            G.Vex[i].FirstArc=0;
            G.Vex[i].InDegree=0;
        }
        NumType v1,v2;
        int j,k;
        cout<<"请输入弧:"<<endl;
        for(k=0;k<G.ArcNum;k++)
        {
            cin>>v1;cin>>v2;
            i=Locate(G,v1);j=Locate(G,v2);
            G.Vex[j].InDegree++;
            ArcNode *p=new ArcNode();
            *p={j,G.Vex[i].FirstArc};
            G.Vex[i].FirstArc=p;
        }
    }
    
    //上面是用邻接表构造有向图
    //下面是拓扑排序代码
    
    void TopoLogicalSort(ALGraph G)
    {
        ArcNode *p=0;
        stack<int> s;
        int i;
        for(i=0;i<G.VexNum;i++)
            if(G.Vex[i].InDegree==0)s.push(i);
        int t;
        int count0=0;
        while(!s.empty())
        {
            count0++;
            t=s.top();
            s.pop();
            cout<<G.Vex[t].data<<" ";
            for(p=G.Vex[t].FirstArc;p!=0;p=p->NextArc)
            {
                G.Vex[p->AdjVex].InDegree--;
                if(!G.Vex[p->AdjVex].InDegree)s.push(p->AdjVex);
            }
        }
    
        if(count0==G.VexNum){cout<<"YES";return;}
        cout<<"NO";
    }
    int main()
    {
        ALGraph G;
        CreatALGraph(G);
        TopoLogicalSort(G);
        return 0;
    }
    
    
    展开全文
  • 图的拓扑排序有向图),用一个矩阵存储,环境为VC6.0
  • 带你了解有向无环拓扑排序

    千次阅读 2020-04-09 19:19:42
    在图论中,如果一个有向图无法从某个顶点出发经过若干条边回到该点,则这个图是一个有向无环图(DAG图)。而提到DAG,就差不多会联想到拓扑排序拓扑排序是指由某个集合上的一个偏序得到该集合上的一个全序的操作。...
  • 用邻接矩阵实现的拓扑排序,如果不是DAG,会找出有向图中的一个环(NKU算法作业)
  • 1、定义 一幅有方向性的图(或有向图)是由一组顶点和一组有方向的边组成的,每条...有向图的数据结构和无向图的数据结构基本一样,区别在于无向图在addEdge时会将两个顶点互相连接,而有向图只能按照指定方向将这两...
  • 一个有向无环(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑...
  • 拓扑排序

    2020-12-22 12:22:13
    有向无环,则可进行拓扑排序拓扑排序的结果为DFS后序遍历的倒序。选课是拓扑排序的经典应用场景之一,即:选修一门课程之前须先修完该课程的前置课程。 class Graph(object): def __init__(self, points_...
  • 有向图中,用顶点表示活动,用有向边<Vi,Vj>表示活动i是活动j的必须条件,这种有向图为顶点表示活动的网简称为AOV网络。 在AOV网络中,如果活动Vi 必须在Vj 之前进行,则存在有向边<Vi,Vj>,并称Vi是...
  • 拓扑排序检测有向图中是否有环

    千次阅读 2021-09-02 10:26:13
    提示:由于拓扑排序的检测方式不涉及到边权或点权,所以拓扑序列中的正环和负环都能够被检测出来。检测可达负环可以用Bellman-Ford或者SPFA。 算法主要步骤 1. 记录每个结点的入度,设置一个队列,专门存放入度为0...
  • AOV网,判断网中是否存在环 否则打印出拓扑序列
  • 有向图拓扑排序 C语言

    千次阅读 2020-11-04 21:52:43
    这种用顶点表示活动,用弧表示活动间的优先关系的有向图称为顶点表示活动的网(Activity On Vertex Network),简称AOV-网。 按照我的理解是:AOV-网是不带权值且没有回路的有向图。 完整代码如下: #include <...
  • NULL 博文链接:https://128kj.iteye.com/blog/1675685
  • 有向图拓扑排序 Kahn算法
  • 用邻接表的方式创建有向图,然后再邻接表的基础上采用静态链表的存储结构实现拓扑排序
  • 如果要使用拓扑排序解决优先级问题,需要先保证有向图中没有环! API: 检测有向环的过程: 判 在API中添加了onStack[] 布尔数组,索引为图的顶点,当我们深度优先搜索时: 在如果当前顶点正在搜索,则把对应的on...
  • 请输出任意一个该有向图拓扑序列,如果拓扑序列不存在,则输出-1。 若一个由图中所有点构成的序列A满足:对于图中的每条边(x, y),x在A中都出现在y之前,则称A是该图的一个拓扑序列。 输入格式 第一行包含两个...
  • 拓扑排序有向图的拓扑序列)

    千次阅读 2021-02-02 23:55:00
    拓扑排序一、有向图的拓扑序列二、代码实现 一、有向图的拓扑序列 给定一个n个点m条边的有向图,点的编号是1到n,图中可能存在重边和自环。 请输出任意一个该有向图的拓扑序列,如果拓扑序列不存在,则输出-1。 若...
  • 4)若此时输出的顶点数小于有向图中的顶点数,则说明有向图中存在回路,否则输出的顶点的顺序即为一个拓扑序列。 基本要求:建立一个有向图,判断该图是否存在环,如果不存在环,输出它的拓扑有序序列;如存在环,给...
  • 大数据结构课程设计:有向图拓扑排序算法的实现.doc
  • 拓扑排序判断有向图中是否有环

    千次阅读 2022-02-24 14:10:31
    拓扑排序一个有向图构造拓扑序列,解决工程是否能顺利进行的问题。构造时有222种结果: 此图全部顶点被输出:说明说明图中无「环」存在, 是 AOV 网(有向无环图) 没有输出全部顶点:说明图中有「环」存在,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 35,230
精华内容 14,092
热门标签
关键字:

对下面的有向图进行拓扑排序