精华内容
下载资源
问答
  • 有向图拓扑排序

    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;
        }
    }
    
    展开全文
  • 拓扑排序一、有向图的拓扑序列二、代码实现 一、有向图的拓扑序列 给定一个n个点m条边的有向图,点的编号是1到n,图中可能存在重边和自环。 请输出任意一个该有向图的拓扑序列,如果拓扑序列不存在,则输出-1。 若...


    一、有向图的拓扑序列

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

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

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

    二、代码实现

    #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 100010;
    
    int n, m;
    int h[N], e[N], ne[N], idx;
    int d[N];
    int q[N];
    
    void add(int a, int b)
    {
        e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
    }
    
    bool topsort()
    {
        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])
            {
                int j = e[i];
                if (-- d[j] == 0)
                    q[ ++ tt] = j;
            }
        }
    
        return tt == n - 1;
    }
    
    int main()
    {
        scanf("%d%d", &n, &m);
    
        memset(h, -1, sizeof h);
    
        for (int i = 0; i < m; i ++ )
        {
            int a, b;
            scanf("%d%d", &a, &b);
            add(a, b);
    
            d[b] ++ ;
        }
    
        if (!topsort()) puts("-1");
        else
        {
            for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);
            puts("");
        }
    
        return 0;
    }
    

    展开全文
  • 拓扑排序:有向无环图(拓扑图) 拓扑序列是顶点活动网中将活动按发生的先后次序进行的一种排列 前提: 有向无环图→\rightarrow→ ...有向图的拓扑序列:https://www.acwing.com/problem/content/850/ #include<

    拓扑排序:有向无环图(拓扑图) 拓扑序列是顶点活动网中将活动按发生的先后次序进行的一种排列
    前提: 有向无环图\rightarrow 一定存在入度为0的点
    思路: 先将入度为0的点入队;出队一点,按bfs的思路 每到下一点,就将这一点的度减1,当此点的度为0时,再将此点入队 ,当队尾指针tt(初始化为-1)的值为n-1时,表示此图可以拓扑排序。此时,q[0~n-1]的值即为拓扑序

    有向图的拓扑序列:https://www.acwing.com/problem/content/850/

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    const int N=1e5+5;
    int h[N], e[N], ne[N],idx;
    int q[N], d[N];
    int n,m;
    void add(int a, int b){
    	e[idx]=b, ne[idx]=h[a], h[a]=idx++;  //idx在这里表示边
    }	                                     //有指针的作用
    
    
    bool topsort(){
    	int hh=0, tt=-1;
    	for(int i=1;i<=n;i++)
    		if(!d[i]) q[++tt]=i;  //如果入度为0 
    	
    	while(hh<=tt){
    		int t=q[hh++];
    		for(int i=h[t];i!=-1;i=ne[i]){
    			int j=e[i];
    			d[j]--;
    			if(!d[j]) q[++tt]=j;  //说明它前面的点已经入队 
    		}
    	} 
    	return tt==n-1; 
    }
    
    int main(){
    	cin>>n>>m;
    	memset(h,-1,sizeof(h));
    	for(int i=0;i<m;i++){
    		int a,b;
    		cin>>a>>b;
    		add(a,b);
    		d[b]++; 
    	}
    	if(topsort()){
    		for(int i=0;i<n;i++) cout<<q[i]<<' ';
    		puts("");	
    	}
    	else puts("-1");
    	
    	return 0;
    }
    
    
    展开全文
  • BFS - 有向图拓扑序列 给定一个n个点m条边的有向图,点的编号是1到n,图中可能存在重边和自环。 请输出任意一个该有向图拓扑序列,如果拓扑序列不存在,则输出-1。 若一个由图中所有点构成的序列A满足:对于图中...

    BFS - 有向图的拓扑序列

    给定一个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


    分析:

    BFS0BFS的思想,不断地将度为0的点入队即可。

    nn1最终队列中的元素应当是n个,队尾指针应当指向n-1。否则不存在拓扑序列。

    代码:

    #include<iostream>
    #include<cstring>
    
    using namespace std;
    
    const int N=100010;
    
    int n,m,e[N],ne[N],h[N],idx,d[N];
    int q[N],hh=0,tt=-1;
    
    void add(int a,int b)
    {
        e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    }
    
    bool topsort()
    {
        for(int i=1;i<=n;i++)
            if(!d[i])
                q[++tt]=i;
                
        while(hh<=tt)
        {
            int u=q[hh++];
            
            for(int i=h[u];~i;i=ne[i])
            {
                int j=e[i];
                d[j]--;
                if(d[j]==0) q[++tt]=j;
            }
        }
        
        return tt==n-1;
    }
    
    int main()
    {
        
        memset(h,-1,sizeof h);
        cin>>n>>m;
        for(int i=0;i<m;i++)
        {
            int a,b;
            cin>>a>>b;
            add(a,b);
            d[b]++;
        }
        
        if(topsort())
        {
            for(int i=0;i<n;i++) cout<<q[i]<<' ';
            cout<<endl;
        }
        else puts("-1");
        
        return 0;
    }
    
    展开全文
  • AcWing - 有向图的拓扑序列(拓扑排序)

    千次阅读 2019-08-16 08:17:39
    请输出任意一个该有向图拓扑序列,如果拓扑序列不存在,则输出-1。 若一个由图中所有点构成的序列A满足:对于图中的每条边(x, y),x在A中都出现在y之前,则称A是该图的一个拓扑序列。 输入格...
  • 只有有向图才有拓扑序,当有向图存在拓扑序且按照拓扑序排好之后,直观来讲它的拓扑序列点边指向都是从前指向后的,即拓扑序列中的每条边,起点都在终点的前面。 只要有环,就不存在拓扑序。可证明,一个有向无环图...
  • 有向图拓扑排序 给定一个n个点m条边的有向图,点的编号是1到n,图中可能存在重边和自环。 请输出任意一个该有向图的拓扑序列,如果拓扑序列不存在,则输出-1。 若一个由图中所有点构成的序列A满足:对于图中的每条...
  • 题目:AcWing848 有向图拓扑序列 题解目录前言一、题目陈述二、解决思路三、代码实现总结 前言 BFS搜索图的应用除了求最短路,还有求拓扑序列。可以证明,一个有向无环图一定存在一个拓扑序列,所以说有向无环图...
  • 用【有向图】表示一个【工程的施工图】或【程序的数据流图】,则图中不允许出现回路 例子: 【回路】 打地基-&amp;amp;amp;amp;amp;gt;做房子结构-&amp;amp;amp;amp;amp;gt;砌墙-&amp;amp;amp;amp;...
  • 思路: 用数组模拟链表,首先如果能用拓扑排序则其一定是有向无...请输出任意一个该有向图的拓扑序列,如果拓扑序列不存在,则输出-1。 若一个由图中所有点构成的序列A满足:对于图中的每条边(x, y),x在A中都出现在y之
  • 有向图拓扑排序

    万次阅读 多人点赞 2016-03-15 23:01:41
     有向图拓扑排序的基本思想是:首先在有向图中选取一个没有前驱的顶点,将其输出,从有向图中删除该顶点,并且删除以该顶点为尾的所有有向图的边。重复以上的步骤,直到图中的所有顶点均输出或是图中的顶点均没有...
  • 有向图拓扑排序 Method Example 给定一个n个点m条边的有向图,图中可能存在重边和自环。 请输出任意一个该有向图的拓扑序列,如果拓扑序列不存在,则输出-1。 若一个由图中所有点构成的序列A满足:对于图...
  • 拓扑排序算法:给出有向图邻接矩阵 1.逐列扫描矩阵,找出入度为0且编号最小的顶点v 2.输出v,并标识v已访问 3.把矩阵第v行全清0 重复上述步骤,直到所有顶点输出为止 –程序要求-- 若使用C++只能include一个头文件...
  • 有向图拓扑排序

    万次阅读 2018-10-20 23:06:53
    有向图 在无向图中,边没有方向,两条边之间的顶点是单向可达的,而有向图的边是单向的。虽然边的性质不同,但我们仍然可以用邻接表来表示有向图。对有向图的结构定义如下: #include <map> #include <...
  • [code="c"] #include "stdio.h" #include "stdlib.h"...//两全局变量提供拓扑排序使用 .../*输入有向图的数据,输出该有向图的拓扑序列 test data 5 4 0 4 2 4 3 3 1 0 3 2 0 2 3...
  • 有向图拓扑序列

    2021-04-27 20:33:44
    有向图拓扑序列 给定一个 n 个点 m 条边的有向图,点的编号是 1 到 n,图中可能存在重边和自环。 请输出任意一个该有向图拓扑序列,如果拓扑序列不存在,则输出 −1。 若一个由图中所有点构成的序列 A 满足:...
  • {// 有向图G采用邻接表储存,若G无回路生成拓扑序列topo{]返回ok,否则返回-1 stack<int> S; int i,k; ArcNode *p; for(i=0; i; i++) if(indegree[i]==0) S.push(i); int m = 0; // 对输出顶点计数,初始...
  • 请输出任意一个该有向图拓扑序列,如果拓扑序列不存在,则输出-1。 若一个由图中所有点构成的序列A满足:对于图中的每条边(x, y),x在A中都出现在y之前,则称A是该图的一个拓扑序列。 输入格式 第一行包含两个...
  • 这种用顶点表示活动,用弧表示活动间的优先关系的有向图称为顶点表示活动的网(Activity On Vertex Network),简称AOV-网。 按照我的理解是:AOV-网是不带权值且没有回路的有向图。 完整代码如下: #include <...
  • 有向图拓扑排序

    2016-11-29 21:39:42
    有向图拓扑排序拓扑排序是可以用图模拟的另一种操作。它可以用于表示一种情况,即某些项目或事件必须按照特定的顺序排列或发生。 如:课程的优先关系 有向图: 图可以表示这类关系,然而,图需要有一种前面...
  • 1.有向图拓扑排序 2.关键路径  2.1.邻接链表存储AOE网  2.1.1拓扑排序: bool TopologicalOrder(): 2.1.2关键路径:bool CriticalPath() 求关键路径的完整代码与测试用例: 无向图、有向图判环...
  • 文章目录拓扑排序 拓扑排序 有向无环常常应用于工程规划中,通过拓扑排序可以有效分析出一个中是否有环,如果不存在,那么他的拓扑序列是什么。
  • 有向图 G=(V, E) 的拓扑排序

    千次阅读 2020-08-13 20:55:21
    拓扑排序有向图中全部顶点的一种线性排序,只有有向图中入度为0的顶点才能成为拓扑排序的第一个顶点,不断重复地寻找入度为0的顶点,即可得到拓扑排序结果,具体方法可以通过深度优先搜索或广度优先搜索来解决有向...
  • 这是我在准备武汉理工初试时 反复练习几次的题,解决的也是最简单的输出一条拓扑排序序列。也曾考过初试,我有个同学在公司笔试时也考过。 是图编程难度算不大的题 问题描述:对于一个有n个节点的有向图,判断其...
  • 有向图拓扑序列 描述 问题转化为:给定一个n个点m条边的有向图,点的编号是1到n,图中可能存在重边和自环。 请输出任意一个该有向图拓扑序列,如果拓扑序列不存在,则输出-1。 若一个由图中所有点构成的序列A...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 16,053
精华内容 6,421
关键字:

有向图拓扑排序序列