精华内容
下载资源
问答
  • 拓扑排序实例
    2016-03-16 15:56:03
    本题主要运用拓扑排序来解题,将每个队伍作为一个节点,如果两个队友有比赛,胜者作为负者的入度。如果负者输于多个队伍,则进行入度加运算,如果出去的是它的入度,则进行入度减一运算,每次取入度为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>

    更多相关内容
  • 本文实例为大家分享了C++实现拓扑排序的具体代码,供大家参考,具体内容如下 一、思路 先扫描所有顶点,把入度为0的顶点(如C,E)进栈。然后,取栈顶元素,退栈,输出取得的栈顶元素v(即入度为0的顶点v)。接着,...
  • 拓扑排序实例

    千次阅读 2016-03-09 10:31:47
    》中介绍了拓扑排序,这里看两道相关题目 1.Course Schedule There are a total of n courses you have to take, labeled from 0 to n - 1. Some courses may have prerequisites, for example to take course 0 y

    在前面的文章《深度优先搜索》中介绍了拓扑排序,在《深度优先实现拓扑排序--java》中给出了一种Java实现,其实现方式是从出度为0的点(也就是它不依赖任何其他点)逆向遍历的。其实还可以正向遍历,过程在前一篇文章的伪代码中给出。这里看两道相关题目加深理解应用。

    1.Course Schedule

    There are a total of n courses you have to take, labeled from0 ton - 1.

    Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair:[0,1]

    Given the total number of courses and a list of prerequisitepairs, is it possible for you to finish all courses?

    For example:

    2, [[1,0]]

    There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

    2, [[1,0],[0,1]]

    There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

    Note:
    The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more abouthow a graph is represented.

    这显然是拓扑排序问题,不过本题只需要判断有无环即可,具体思路可以参考开头给出的文章链接。可以用广度优先搜索,也可以用深度优先搜索。深度优先搜索可以用递归,也可以模拟递归。直接用递归,效率比较低,本题目的话会超时。下面程序中的global数组用于记录元素的全局使用情况。有人可能会想到从所有 入度为0的点开始遍历,或者从出度为0的点逆向遍历,这都能得到正确的解,但是没有必要。

    下面给出递归与非递归版本

    递归:

    public class Solution {
        boolean[] used;
        boolean[] global;
    //    LinkedList<Integer> res = new LinkedList<Integer>();
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            ArrayList[] graph = new ArrayList[numCourses];
            for(int[] pre:prerequisites){
                if(graph[pre[0]] == null) graph[pre[0]] = new ArrayList<Integer>();
                graph[pre[0]].add(pre[1]);
            }
            used = new boolean[numCourses];
            global = new boolean[numCourses];
            for(int i = 0;i < numCourses;i++){
                if(global[i]) continue;
                Arrays.fill(used,false);
                if(!dfs(graph,i)) return false;
            }
            return true;
        }
        public boolean dfs(List<Integer>[] graph,int x){
            boolean res = true;
            used[x] = true;
            global[x] = true;
            if(graph[x] == null) return true;
            for(int y:graph[x]){
                if(used[y]) return false;
    //          res.addFirst(y);
                res = res & dfs(graph,y);
                used[y] = false;
            }
            return res;
        }
    }

    非递归版本

    public class Solution {
        boolean[] used;
        boolean[] global;
    //  LinkedList<Integer> res = new LinkedList<Integer>();
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            ArrayList[] graph = new ArrayList[numCourses];
            for(int[] pre:prerequisites){
                if(graph[pre[0]] == null) graph[pre[0]] = new ArrayList<Integer>();
                graph[pre[0]].add(pre[1]);
            }
            global = new boolean[numCourses];
            used = new boolean[numCourses];
            LinkedList<Integer> stack = new LinkedList<Integer>();
            for(int i = 0;i < numCourses;i++){
                Arrays.fill(used,false);
                if(global[i]) continue;
                stack.addLast(i);
                used[i] = true;
                global[i] = true;
                if(graph[i] == null) {stack.removeLast();used[i] = false;continue;}
                boolean flag = false;
                while(stack.size() > 0){
                    int course = stack.getLast();
                    if(graph[course] == null){stack.removeLast(); used[course] = false;continue;}
                    flag = false;
                    Integer index = null;
                    for(int j = 0;j < graph[course].size();j++){
                        index = (Integer)(graph[course].get(j));
                        if(used[index]) return false;
                        if(global[index]) continue;
                        global[index] = true;
                        used[index] = true;
                        stack.addLast(index);
                        flag = true;
                        break;
                    }
                    if(!flag) {index = stack.removeLast();used[index] = false;}
                }
            }
            return true;
        }
    }

    2.Course Schedule II

    There are a total of n courses you have to take, labeled from0 ton - 1.

    Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair:[0,1]

    Given the total number of courses and a list of prerequisitepairs, return the ordering of courses you should take to finish all courses.

    There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

    For example:

    2, [[1,0]]

    There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is[0,1]

    4, [[1,0],[2,0],[3,1],[3,2]]

    There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is[0,1,2,3]. Another correct ordering is[0,2,1,3].

    Note:
    The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more abouthow a graph is represented.

    同上题一样,只不过这里要求给出结果。关于这道题由于Java不允许创建泛型数组,所以需要强制转换工作。另外,Java的对象数组创建数组后,相应的对象并未创建,使用数组的时候需要注意先创建对象。

    代码如下:

    public class Solution {
        public int[] findOrder(int numCourses, int[][] prerequisites) {
            ArrayList[] g = new ArrayList[numCourses];
            for(int[] pre:prerequisites){
                if(g[pre[0]] == null) g[pre[0]] = new ArrayList<Integer>();
                g[pre[0]].add(pre[1]);
            }
            int k = 0;
            int cur = 0;
            int[] res = new int[numCourses];
            if(prerequisites.length == 0 && numCourses > 0){
                for(int i = 0;i < numCourses;i++) res[i] = i;
                return res;
            }
            LinkedList<Integer> stack = new LinkedList<Integer>();
            boolean[] global = new boolean[numCourses];
            for(int i = 0;i < numCourses;i++){
                if(global[i]) continue;
                global[i] = true;
                if(g[i] == null) {res[k++] = i; continue;}
                boolean[] used = new boolean[numCourses];
                stack.addLast(i);
                used[i] = true;
                while(stack.size() > 0){
                    int cour = stack.getLast();
                    if(g[cour] == null){cur = stack.removeLast(); used[cur] = false; res[k++] = cur; continue;}
                    boolean flag = false;
                    for(int index = 0;index < g[cour].size();index++){
                        int c = (Integer)(g[cour].get(index));
                        if(used[c]) return new int[0];
                        if(global[c]) continue;
                        used[c] = true;
                        global[c] = true;
                        stack.addLast(c);
                        flag = true;
                        break;
                    }
                    if(!flag){cur = stack.removeLast(); used[cur] = false; res[k++] = cur;}
                }
            }//
            return res;
        }
    }







    展开全文
  • 拓扑排序(附例题)

    千次阅读 2021-11-23 15:19:06
    ACWING848 拓扑排序 给定一个 n nn 个点 m mm 条边的有向图,点的编号是 1 11 到 n nn,图中可能存在重边和自环。 请输出任意一个该有向图的拓扑序列,如果拓扑序列不存在,则输出 − 1 -1−1。 若一个由图中所有点...

    思想

    拓扑排序本质上就是把一个有向无环图(DAG)变成一个线性序列,给定DAG中两个点u,v,若<u,v>∈E(G),那么在线性序列中,u一定在v前面。
    有向无环图一定可以拓扑排序,有向有环图一定不能拓扑排序。

    例题

    ACWING848 拓扑排序
    在这里插入图片描述

    输入样例:

    3 3
    1 2
    2 3
    1 3
    

    输出样例:

    1 2 3
    

    AC代码

    #include <bits/stdc++.h>
    using namespace std;
    const int N = 1e5 + 10;
    int h[N], e[N], ne[N], q[N], d[N], idx, n, m;
    void add(int a, int b)
    {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    int 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])
            {
                int j = e[i];
                d[j]--;
                if(!d[j])
                    q[++tt] = j;
            }
        }
        return tt == n - 1;
    }
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        int a, b;
        memset(h, -1, sizeof h);
        cin >> n >> m;
        while(m--)
        {
            cin >> a >> b;
            add(a, b);
            d[b]++;
        }
        if(toposort())
            for(int i = 0; i < n; i++)
                cout << q[i] << ' ';
        else
            cout << "-1" << '\n';
        return 0;
    }
    
    

    核心思想与注意点:

    • 调用toposort()函数后,如果队列中的元素个数等于给定图的元素个数,则说明该图是有向无环图,可以拓扑排序。
    • 每次输入一条有向边,就将有向边末尾的元素入度加一。
    • 拓扑排序时,先把入度为0的点全部入队,然后出队一个元素,bfs,把这个元素的邻接点入度全部减一,如果它的邻接点入度变为0,那么把它的邻接点也入队。
    展开全文
  • 既然是一种排序,那么肯定是按照某种规则进行排序,那么这么想的话,先了解基本知识,再来实战演练 1. AOV网(Activity On Vertex Network)【顶点——表示活动】 是一个——有向无回路的图 顶点——表示活动 用弧...

    一:引言

    既然是一种排序,那么肯定是按照某种规则进行排序,那么这么想的话,先了解基本知识,再来实战演练
    1. AOV网(Activity On Vertex Network)【顶点——表示活动】
    是一个——有向无回路的图
    顶点——表示活动
    用弧——表示活动间的优先关系的有向图称为-顶点表示活动的网
    即如果a->b,那么a是b的先决条件
    求拓扑序列就是AOV
    2.
    用邻接矩阵存储时 每一列表示这个顶点的入度(有向图中)

    二:上码

    /* 
    	1.
    		AOV网(Activity On Vertex Network)【顶点——表示活动】
    		是一个——有向无回路的图
    		顶点——表示活动
    		用弧——表示活动间的优先关系的有向图称为-顶点表示活动的网
    		即如果a->b,那么a是b的先决条件
    		求拓扑序列就是AOV
    	2.
    		用邻接矩阵存储时 每一列表示这个顶点的入度(有向图中)	
    */
    #include<bits/stdc++.h>
    using namespace std;
    
    typedef struct GNode* PtrGraph;
    typedef struct GNode{
    	int Nv;
    	int Ne;
    	int Date[100][100];
    }gnode;
    
    int cnt; //统计每个结点的入度 
    vector<int>v;//存入度的 
    vector<int>v1;//记录拓扑序列 
    
    //创建图
    void creatrGraph(PtrGraph G){
    	int N,M;
    	cin >> N >> M;
    	G->Nv = N;
    	G->Ne = M;
    	
    	//矩阵初始化
    	for( int i = 0; i < G->Nv; i++ ){
    		for(int j = 0; j < G->Nv; j++ ){
    			G->Date[i][j] = 0;
    		}
    	} 
    	 
    	//矩阵赋值
    	for(int i = 0; i < G->Ne; i++ )
    	{
    		int a,b;
    		cin >> a >> b;
    		
    		G->Date[a][b] = 1;//有向图	
    	} 	
    } 
    //求取每一列的数据和即为该顶点的入度
    void degree(PtrGraph G){
    	
    	for(int j = 0; j < G->Nv; j++ ){
    	
    		cnt = 0;
    	
    		for( int i = 0; i < G->Nv; i++ ){
    			if(G->Date[i][j] == 1)
    			 cnt++;
    		}
    	    
    	    v.push_back(cnt);
    	}
    }  
    //求拓扑序列
    
    void topology( PtrGraph G ){
    	
    	queue<int>q;
    	int count = 0;//用于计算度数为0的结点的个数 
    	
    	for( int i = 0; i < G->Nv; i++ )
    	{
    		if(v[i] == 0)
    		q.push(i);//将入度为0的入队		
    	} 
    		
    	//这里就是处理每次去掉一个度数为0的点和其有关系的顶点度数减一 
    	while( !q.empty() ){
    		
    		int temp = q.front();
    		q.pop();
    		
            v1.push_back(temp); 
    		
    		count++;
    		
    		for( int j = 0; j < G->Nv; j++ ){//列 
    			
    			if( G->Date[temp][j] == 1  ){//在 temp 这一行中 等于 1的 j 需要入度减一 	
    				v[j]--;//其入度减一
    				
    				if( v[j] == 0 ){
    				q.push(j);// 将入度为0的入度 
    			}
    					 	
    			}
    		}
    	} 
    	
    	if( G->Nv  == count ){//没有环 
    		for( int i = 0; i < v1.size(); i++ )
              	cout << v1[i] << ' '; 	
    	}else{
    		cout << "此图有环"; 
    	} 
    	
    	
    } 
    
    
    int main(){
    	
    	PtrGraph G = (PtrGraph)malloc(sizeof(struct GNode));
    	creatrGraph(G);
    	degree(G);
    	topology(G);
    
    	
    } 
    
    
    //5 6
    //0 1
    //0 2
    //1 3
    //2 1
    //2 4
    //3 4
    //拓扑序列为:0 2 1 3 4
    

    在这里插入图片描述
    加油boy 冲呀

    展开全文
  • 拓扑排序(图)

    2021-11-06 10:24:38
    拓扑排序原理(本质是图): 用顶点表示活动的网络 (AOV网络) 计划、施工过程、生产流程、程序流程等都是“工程”。除了很小的工程外,一般都把工程分为若干 个叫做“活动”的子工程。完成了这些活动,这个工程就...
  • 14.2 拓扑排序DFS算法

    2022-04-06 23:43:59
    详细介绍了拓扑排序的DFS方法,使用三色标记代替递归哦。
  • 记录拓扑排序在实际项目中的应用
  • 超详细讲解实现拓扑排序、关键路径

    千次阅读 多人点赞 2022-03-26 11:07:49
    今天,小编带着大家来学习图中非常重要的一环,拓扑排序和关键路径! 首先,我们需要知道的是,拓扑排序是关键路径的基础,正因如此,当我们知道了关键路径在生活中的应用,相信大家也就明白这两个算法的重要性了!...
  • 拓扑排序dfs实现

    千次阅读 2020-06-14 12:05:46
    如果没有环的话一定可以存在一条这样的链,但是如果有环就不能进行拓扑排序。这个例子就是不能 a > b 且 b > a; 使用dfs 进行 伪代码 //判断是否有环 bool dfs(u) { 本趟节点标记; for(遍历以u为入弧的定点)...
  • 基于Python的拓扑排序

    千次阅读 2019-08-28 23:35:47
    什么是拓扑排序? 在图论中,拓扑排序(Topological Sorting)是一个有向无环图(DAG, Directed Acyclic Graph)的所有顶点的线性序列,该序列必须满足下列两个条件: 1. 每个顶点仅出现一次 2. 若存在一条从...
  • Java中的拓扑排序

    2021-03-20 21:32:00
    Java中的拓扑排序 弗拉基米尔·巴托坎宁(VladimirBatoćanin)•0评论 介绍 穿衣服时,就像您一样,您很可能没有以下思路: 哦,穿上裤子先穿好内裤可能是个好主意。 这是因为我们习惯于按拓扑对动作...
  • dfs深度优先搜索有一个特点,那就是在一个连通子图上,每个顶点只会被搜索一次,要将搜索过的顶点进行排序,只需要将搜索的顶点放入到线性序列的数据结构中即可 此处用栈存顶点,栈是后进先出,压栈时是由递归出口...
  • 拓扑排序概念

    千次阅读 2018-12-27 22:43:41
    拓扑排序,顾名思义,就是一种排序方法。这是一种什么排序?这种排序的作用?然后怎么去实现这种排序算法?现在就让我们仔细研究下。 1、什么是拓扑排序,也就是拓扑排序的概念 实际上,拓扑排序是一种图论算法,...
  • 拓扑排序-求关键路径 首先,我们来了解一下,什么是拓扑排序。百度百科这样说:对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若...
  • 拓扑排序(DFS)

    千次阅读 2020-03-12 11:03:09
    根据拓扑排序的定义可以知道,只有图没有环路时才有拓扑排序,由上述DFS生成树可知,当图的DFS生成树没有反祖边时没有环路,这时就可以找出图的拓扑排序(建议画一张图,然后用DFS遍历一遍,就能理解为什么得出拓扑...
  • 拓扑排序(邻接表)

    2021-12-03 18:04:51
    (3)通过本实验的具体应用实例,灵活应用拓扑排序并进一步巩固队列/栈的运用。 2.实验内容 用邻接表形式存储以下有向无环图,进行拓扑排序,输出相应拓扑序列。若图中每个顶点都在拓扑序列中,说明图中无环...
  • 拓扑排序详解

    2021-12-06 19:34:29
    拓扑排序 参考文章: 拓扑排序,YYDS Java 简单好理解的拓扑排序 1. 简介 对一个有向无环图(Directed Acyclic Graph简称DAG) G 进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边&...
  • 拓扑排序几乎在所有的项目,甚至日常生活,待完成的不同任务之间通常都会存在着某些依赖关系,这些依赖关系会为它们的执行顺序行程表部分约束。对于这种依赖关系,很容易将其表示成一个有向无环图(Directed Acyclic ...
  • 拓扑排序常用来确定一个依赖关系集中、事物发生的顺序。一个典型的应用场景就是在项目管理或工程实施中安排各种生产活动的计划,在考虑各种活动的依赖关系的基础上,安排各种活动的开始时间,使得项目或工程能够以...
  • 数据结构基础:P2.4-线性结构—>应用实例:多项式加法运算 数据结构基础:P2.5-线性结构—>应用实例:多项式乘法与加法运算-C实现 数据结构基础:P3.1-树(一)—>树与树的表示 数据结构基础:P3.2-树(一)—>...
  • 三、【图算法】DFS应用-拓扑排序

    千次阅读 2018-12-07 14:21:06
    深度优先搜索(DFS)算法是最重要的图遍历算法,基于DFS框架,可以导出大量的图算法,图的拓扑排序即为其中一个很典型的例子。 拓扑排序:给定一个有向图,如何在保证“每个顶点都不会通过边,指向其在此序列中的前驱...
  • 最后发现出队的元素个数是2(A,D),而图上的个数是5个(ABCDE),两者不相同证明有环,同时注意有环的时候是没有拓扑排序的即没有拓扑排序的 ----------------------------------------------------------------...
  • 拓扑排序的原理及实现

    万次阅读 多人点赞 2017-08-05 14:06:27
    拓扑排序,顾名思义,就是一种排序方法。这是一种什么排序?这种排序的作用?然后怎么去实现这种排序算法?现在就让我们仔细研究下。1、什么是拓扑排序,也就是拓扑排序的概念 实际上,拓扑排序是一种图论算法,该...
  • 在这个应用程序中,拓扑排序只是任务的有效序列。 当且仅当图形没有有向循环时,即如果它是有向无环图(DAG),则可以进行拓扑排序。 任何DAG都具有至少一个拓扑排序。这种用弧来表示活动之间的优先级关系的有向图...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,220
精华内容 4,488
关键字:

拓扑排序实例