精华内容
下载资源
问答
  • PAGE 数据结构课程设计 设计说明书 有向图拓扑排序算法的实现 学生姓名 樊佳佳 学号 1318064017 班级 网络工程1301 成绩 指导教师 申静 数学与计算机科学学院 2016年1月4日 课程设计任务书 20152016学年第一学期 ...
  • 有向图拓扑排序

    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;
        }
    }
    
    展开全文
  • 有向图拓扑排序算法(java实现) import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class TopologicalOrder{ static class Node{ int pos; int val; Node next;...

    有向图的拓扑排序算法(java实现)

    由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步,直到不存在入度为0的顶点为止。
    (1) 选择一个入度为0的顶点并输出之;
    (2) 从网中删除此顶点及所有出边。

    循环结束后,若输出的顶点数小于网中的顶点数,则输出“有回路”信息,否则输出的顶点序列就是一种拓扑序列。

    拓扑排序的应用场景很好理解,比如在内存中运行着很多任务,某个任务A的执行依赖于另外一个任务B,那么在A执行完之前,B一定不能被清理。而另外一些任务是没有关联的,如何来安排这些任务被清理的顺序就需要依赖拓扑排序。

    在这里插入图片描述

    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Scanner;
    
    
    
    public class TopologicalOrder{
    	
    	static class Node{
    		int pos;
    		int val;
    		Node next;
    	}
    	static int n ,m;
    	static int N = 100010;
    	
    	static Node[] h = new Node[N];
    	
    	//每个节点的入度
    	static int [] d = new int[N];
    	//答案数组
    	static int [] ans = new int[N];
    	//p插入u为头节点邻接表
    	static void insert(int u,int p){
    		Node hh = h[u];
    		Node newNode = new Node();newNode.pos = p;newNode.next = hh.next;
    		hh.next = newNode;
    	}
    	public static void main(String[] args) {
    		Scanner in = new Scanner(System.in);
    		String  [] s =in.nextLine().split(" ");
    		n = Integer.parseInt(s[0]);
    		m = Integer.parseInt(s[1]);
    		//初始化n个顶点
    		for(int i=1;i<=n;i++) {Node n = new Node();n.pos = i;h[i] = n;}
    		for(int i=1;i<=m;i++){
    			String [] ss = in.nextLine().split(" ");
    			int x = Integer.parseInt(ss[0]);
    			int y = Integer.parseInt(ss[1]);
    			insert(x,y);
    			//统计入读
    			d[y]++;
    		}
    		search();
    	}
    	static void search() {
    		Queue<Integer> q = new LinkedList<Integer>();
    		//队列中初始化入读为零的点
    		for(int i=1;i<=n;i++){
    			if(d[i]==0) q.add(i);
    		}
    		int size = 0;
    		while(!q.isEmpty()){
    			int p = q.poll();
    			//输出
    			ans[size++] = p;
    			while(h[p].next!=null){
    				Node f = h[p].next;
    				h[p].next = f.next;
    				int fp = f.pos;
    				if(--d[fp]==0) q.add(fp);
    			}
    		}
    		if(size == n) for(int i=0;i<n;i++) System.out.print(ans[i]+" ");
    		else System.out.println(-1);
    	}
    }
    
    

    https://www.cnblogs.com/bigsai/p/11489260.html 详细了解拓扑排序算法戳这儿

    算法:

    • 实现算法运用了邻接表
    • 通过入度的是否为零判断能否加入队列中

    主要流程:

    • 把所有入度为0的节点添加到队列中
    • 如果队列不为空
      1.取队首元素 h 输出元素
      2.遍历该元素的所有边 h->j
      3.使j节点的入读减1
      如果j的入度为0 把j加入到队列中

    输出的顺序即为拓扑顺序

    展开全文
  • 有向图拓扑排序算法JAVA实现

    千次阅读 2017-11-17 09:47:42
    给定一个有向图G=(V,E),将之进行拓扑排序,如果图有环,则提示异常。 要想实现图的算法,如拓扑排序、最短路径……并运行看输出结果,首先就得构造一个图。由于构造图的方式有很多种,这里假设图的数据存储在一...

    一,问题描述

    给定一个有向图G=(V,E),将之进行拓扑排序,如果图有环,则提示异常。

    要想实现图的算法,如拓扑排序、最短路径……并运行看输出结果,首先就得构造一个图。由于构造图的方式有很多种,这里假设图的数据存储在一个文件中,

    每一行包含如下的信息:
    LinkID,SourceID,DestinationID,Cost
    其中,LinkID为该有向边的索引,SourceID为该有向边的起始顶点的索引,DestinationID为该有向边的终止顶点的索引,Cost为该有向边的权重。

    0,0,1,1
    1,0,2,2
    2,0,3,1
    3,2,1,3
    4,3,1,1
    5,2,3,1
    6,3,2,1

    (以上示例引用自网上,该图仅用来表示存储图信息的文件内容的格式,对拓扑排序而言,上图显然存在环)

    对于以下的拓扑排序程序,只用到了SourceID,和DestionatinID这两个字段。拓扑序列以顶点的索引表示。后续会实现无向图的最短路径算法,就会用到Cost这个字段啦!!!

     

    二,算法实现思路

    拓扑排序,其实就是寻找一个入度为0的顶点,该顶点是拓扑排序中的第一个顶点序列,将之标记删除,然后将与该顶点相邻接的顶点的入度减1,再继续寻找入度为0的顶点,直至所有的顶点都已经标记删除或者图中有环。

    从上可以看出,关键是寻找入度为0的顶点。

    一种方式是遍历整个图中的顶点,找出入度为0的顶点,然后标记删除该顶点,更新相关顶点的入度,由于图中有V个顶点,每次找出入度为0的顶点后会更新相关顶点的入度,因此下一次又要重新扫描图中所有的顶点。故时间复杂度为O(V^2)

    由于删除入度为0的顶点时,只会更新与它邻接的顶点的入度,即只会影响与之邻接的顶点。但是上面的方式却遍历了图中所有的顶点的入度。

    改进的另一种方式是:先将入度为0的顶点放在栈或者队列中。当队列不空时,删除一个顶点v,然后更新与顶点v邻接的顶点的入度。只要有一个顶点的入度降为0,则将之入队列。此时,拓扑排序就是顶点出队的顺序。该算法的时间复杂度为O(V+E)

    三,拓扑排序方法的实现

    该算法借助队列来实现时,感觉与 二叉树的 层序遍历算法很相似啊。说明这里面有广度优先的思想。

    第一步:遍历图中所有的顶点,将入度为0的顶点 入队列。

    第二步:从队列中出一个顶点,打印顶点,更新该顶点的邻接点的入度(减1),如果邻接点的入度减1之后变成了0,则将该邻接点入队列。

    第三步:一直执行上面 第二步,直到队列为空。

    复制代码
     1     public void topoSort() throws Exception{
     2         int count = 0;//判断是否所有的顶点都出队了,若有顶点未入队(组成环的顶点),则这些顶点肯定不会出队
     3         
     4         Queue<Vertex> queue = new LinkedList<>();// 拓扑排序中用到的栈,也可用队列.
     5         //扫描所有的顶点,将入度为0的顶点入队列
     6         Collection<Vertex> vertexs = directedGraph.values();
     7         for (Vertex vertex : vertexs)
     8             if(vertex.inDegree == 0)
     9                 queue.offer(vertex);
    10         //度为0的顶点出队列并且更新它的邻接点的入度
    11         while(!queue.isEmpty()){
    12             Vertex v = queue.poll();
    13             System.out.print(v.vertexLabel + " ");//输出拓扑排序的顺序
    14             count++;
    15             for (Edge e : v.adjEdges) 
    16                 if(--e.endVertex.inDegree == 0)
    17                     queue.offer(e.endVertex);
    18         }
    19         if(count != directedGraph.size())
    20             throw new Exception("Graph has circle");
    21     }
    复制代码

    第7行for循环:先将图中所有入度为0的顶点入队列。

    第11行while循环:将入度为0的顶点出队列,并更新与之邻接的顶点的入度,若邻接顶点的入度降为0,则入队列(第16行if语句)。

    第19行if语句判断图中是否有环。因为,只有在每个顶点出队时,count++。对于组成环的顶点,是不可能入队列的,因为组成环的顶点的入度不可能为0(第16行if语句不会成立).

    因此,如果有环,count的值 一定小于图中顶点的个数。

     

    四,完整代码实现

    DirectedGraph.java中定义了图 数据结构,(图的实现可参考:数据结构--图 的JAVA实现(上))。并根据FileUtil.java中得到的字符串构造图。

    构造 图之后,topoSort方法实现了拓扑排序。

    复制代码
     1 import java.util.Collection;
     2 import java.util.LinkedHashMap;
     3 import java.util.LinkedList;
     4 import java.util.List;
     5 import java.util.Map;
     6 import java.util.Queue;
     7 
     8 /*
     9  * 用来实现拓扑排序的有向无环图
    10  */
    11 public class DirectedGraph {
    12 
    13     private class Vertex{
    14         private String vertexLabel;// 顶点标识
    15         private List<Edge> adjEdges;
    16         private int inDegree;// 该顶点的入度
    17 
    18         public Vertex(String verTtexLabel) {
    19             this.vertexLabel = verTtexLabel;
    20             inDegree = 0;
    21             adjEdges = new LinkedList<Edge>();
    22         }
    23     }
    24 
    25     private class Edge {
    26         private Vertex endVertex;
    27 
    28         // private double weight;
    29         public Edge(Vertex endVertex) {
    30             this.endVertex = endVertex;
    31         }
    32     }
    33 
    34     private Map<String, Vertex> directedGraph;
    35 
    36     public DirectedGraph(String graphContent) {
    37         directedGraph = new LinkedHashMap<String, DirectedGraph.Vertex>();
    38         buildGraph(graphContent);
    39     }
    40 
    41     private void buildGraph(String graphContent) {
    42         String[] lines = graphContent.split("\n");
    43         Vertex startNode, endNode;
    44         String startNodeLabel, endNodeLabel;
    45         Edge e;
    46         for (int i = 0; i < lines.length; i++) {
    47             String[] nodesInfo = lines[i].split(",");
    48             startNodeLabel = nodesInfo[1];
    49             endNodeLabel = nodesInfo[2];
    50             startNode = directedGraph.get(startNodeLabel);
    51             if(startNode == null){
    52                 startNode = new Vertex(startNodeLabel);
    53                 directedGraph.put(startNodeLabel, startNode);
    54             }
    55             endNode = directedGraph.get(endNodeLabel);
    56             if(endNode == null){
    57                 endNode = new Vertex(endNodeLabel);
    58                 directedGraph.put(endNodeLabel, endNode);
    59             }
    60             
    61             e = new Edge(endNode);//每读入一行代表一条边
    62             startNode.adjEdges.add(e);//每读入一行数据,起始顶点添加一条边
    63             endNode.inDegree++;//每读入一行数据,终止顶点入度加1
    64         }
    65     }
    66 
    67     public void topoSort() throws Exception{
    68         int count = 0;
    69         
    70         Queue<Vertex> queue = new LinkedList<>();// 拓扑排序中用到的栈,也可用队列.
    71         //扫描所有的顶点,将入度为0的顶点入队列
    72         Collection<Vertex> vertexs = directedGraph.values();
    73         for (Vertex vertex : vertexs)
    74             if(vertex.inDegree == 0)
    75                 queue.offer(vertex);
    76         
    77         while(!queue.isEmpty()){
    78             Vertex v = queue.poll();
    79             System.out.print(v.vertexLabel + " ");
    80             count++;
    81             for (Edge e : v.adjEdges) 
    82                 if(--e.endVertex.inDegree == 0)
    83                     queue.offer(e.endVertex);
    84         }
    85         if(count != directedGraph.size())
    86             throw new Exception("Graph has circle");
    87     }
    88 }
    复制代码

     

    FileUtil.java负责从文件中读取图的信息。将文件内容转换成 第一点 中描述的字符串格式。--该类来源于网络

    复制代码
    import java.io.BufferedReader;
    import java.io.BufferedWriter;
    import java.io.Closeable;
    import java.io.File;
    import java.io.FileReader;
    import java.io.FileWriter;
    import java.io.IOException;
    
    public final class FileUtil
    {
        /** 
         * 读取文件并按行输出
         * @param filePath
         * @param spec 允许解析的最大行数, spec==null时,解析所有行
         * @return
         * @author
         * @since 2016-3-1
         */
        public static String read(final String filePath, final Integer spec)
        {
            File file = new File(filePath);
            // 当文件不存在或者不可读时
            if ((!isFileExists(file)) || (!file.canRead()))
            {
                System.out.println("file [" + filePath + "] is not exist or cannot read!!!");
                return null;
            }
    
            BufferedReader br = null;
            FileReader fb = null;
            StringBuffer sb = new StringBuffer();
            try
            {
                fb = new FileReader(file);
                br = new BufferedReader(fb);
    
                String str = null;
                int index = 0;
                while (((spec == null) || index++ < spec) && (str = br.readLine()) != null)
                {
                    sb.append(str + "\n");
    //                System.out.println(str);
    
                }
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            finally
            {
                closeQuietly(br);
                closeQuietly(fb);
            }
    
            return sb.toString();
        }
        /** 
         * 写文件
         * @param filePath 输出文件路径
         * @param content 要写入的内容
         * @param append 是否追加
         * @return
         * @author s00274007
         * @since 2016-3-1
         */
        public static int write(final String filePath, final String content, final boolean append)
        {
            File file = new File(filePath);
            if (content == null)
            {
                System.out.println("file [" + filePath + "] invalid!!!");
                return 0;
            }
    
            // 当文件存在但不可写时
            if (isFileExists(file) && (!file.canRead()))
            {
                return 0;
            }
    
            FileWriter fw = null;
            BufferedWriter bw = null;
            try
            {
                if (!isFileExists(file))
                {
                    file.createNewFile();
                }
    
                fw = new FileWriter(file, append);
                bw = new BufferedWriter(fw);
    
                bw.write(content);
            }
            catch (IOException e)
            {
                e.printStackTrace();
                return 0;
            }
            finally
            {
                closeQuietly(bw);
                closeQuietly(fw);
            }
    
            return 1;
        }
    
        private static void closeQuietly(Closeable closeable)
        {
            try
            {
                if (closeable != null)
                {
                    closeable.close();
                }
            }
            catch (IOException e)
            {
            }
        }
    
        private static boolean isFileExists(final File file)
        {
            if (file.exists() && file.isFile())
            {
                return true;
            }
    
            return false;
        }
    }
    复制代码

     

    测试类:TestTopoSort.java

    复制代码
     1 public class TestTopoSort {
     2     public static void main(String[] args) {
     3         String graphFilePath;
     4         if(args.length == 0)
     5             graphFilePath = "F:\\xxx";
     6         else
     7             graphFilePath = args[0];
     8         
     9         String graphContent = FileUtil.read(graphFilePath, null);//从文件中读取图的数据
    10         DirectedGraph directedGraph = new DirectedGraph(graphContent);
    11         try{
    12             directedGraph.topoSort();
    13         }catch(Exception e){
    14             System.out.println("graph has circle");
    15             e.printStackTrace();
    16         }
    17     }
    18 }
    复制代码
    展开全文
  • 给定一个n个点m条边的有向图,点的编号是1到n,图中可能存在重边和自环。 请输出任意一个该有向图拓扑序列,如果拓扑序列不存在,则输出-1。 若一个由图中所有点构成的序列A满足:对于图中的每条边(x, y),x在A...

    思路:

    用数组模拟链表,首先如果能用拓扑排序则其一定是有向无环图。
    所以我们应该先找到其入度为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;
    }
    

    原题链接

    展开全文
  • 一,问题描述给定一个有向图G=(V,E),将之进行拓扑排序,如果图有环,则提示异常。要想实现图的算法,如拓扑排序、最短路径……并运行看输出结果,首先就得构造一个图。由于构造图的方式有很多种,这里假设图的...
  • 也可以检验有向图是否存在回路。这里处理的对象是邻接表。 bool ToplogicalSort(Graph G){ InitStack(S); for(int i=0;i&lt;G.vexnum;i++)//初始化栈,存储入度为0的顶点 if(indegree[i]==0)Push(S,i); int ...
  • https://blog.csdn.net/qq_35644234/article/details/60578189拓扑排序的实现步骤在有向图中选一个没有前驱的顶点并且输出从图中删除该顶点和与它有关的边重复上述两步,直至所有顶点输出,或者当前图中不存在无前驱...
  • 有向图拓扑排序 Kahn算法
  • 对一个有向无环(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得中任意一对顶点u和v,若<u,v> ∈E(G),则u在线性序列中出现在v之前。 通常,这样的线性序列称为...
  • #File Name : 图的拓扑排序算法.py #拓扑排序:在任何一个节点之前,所依赖的节点都做完 #找到所有入度为0的节点,这些节点代表不需要任何的依赖 #删除这些,又有新的入度为0的节点,删掉代表已经做完 #要求有向图且...
  • 转载自C++ 拓扑排序算法 有向无环图 如果一个有向图的任意顶点都无法通过一些有向边回到自身,那么称这个有向图为有向无环图。 不含环路的有向图必包含入度为零的顶点—因此一定存在拓扑排序 拓扑排序的应用 图...
  • 图的拓扑排序定义: 给定一幅有向图, 对图中各顶点排序, 使得对于图中的任意有向边v−>wv->wv−>w, 均满足节点vvv出现在节点www之前. 我们可以很容易证明, 存在环路的有向图无法进行排序. 假设当前有向图...
  •  对一个有向无环(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得中任意一对顶点u和v,若 ∈E(G),则u在线性序列中出现在v之前。  通常,这样的线性序列称为满足...
  • 拓扑排序算法判别有向图中是否存在有向环。 实验课上写的,绝对可用!!
  • 拓扑排序算法

    2012-11-22 22:25:13
    编程实现拓扑排序算法,研究生课程-软件技术基础作业。
  • http://blog.csdn.net/derkampf/article/details/57414185,这一篇进行拓扑排序算法的实现。 一.概念 由偏序得到全序的操作称为拓扑排序。在拓扑排序之后,有向图中的每一个顶点都会按照一定的次序进行输出。 二....
  • 拓扑排序会对有向图的所有顶点进行排序,使有向边从前面的顶点指向后面的顶点。拓扑排序算法与深度优先搜索类似。不同的是,拓扑排序算法不会立即输出已访问的顶点,而是访问当前顶点邻接表中的所有相邻顶点,直到这...
  • Kahn算法 拓扑排序
  • //拓扑排序 void TopSort(struct Map *mp) {  int iPoint,iNoInPoint;  int noInPoint[20];  int curPoint;  struct ENode *pNode; //将初始状态入度为0的节点放入数组  for(iPoint=0,...
  • 有向图拓扑排序

    万次阅读 多人点赞 2016-03-15 23:01:41
     有向图拓扑排序的基本思想是:首先在有向图中选取一个没有前驱的顶点,将其输出,从有向图中删除该顶点,并且删除以该顶点为尾的所有有向图的边。重复以上的步骤,直到图中的所有顶点均输出或是图中的顶点均没有...
  • C++ 拓扑排序算法

    千次阅读 2017-08-18 10:29:05
     如果一个有向图的任意顶点都无法通过一些有向边回到自身,那么称这个有向图为有向无环图。 拓扑排序  拓扑排序是将有向无环图G的所有顶点排成一个线性序列,使得对图G中的任意两个顶点u、v,如果存在边u->v...
  • 1、定义 一幅有方向性的图(或有向图)是由一组顶点和一组有方向的边组成的,每条...有向图的数据结构和无向图的数据结构基本一样,区别在于无向图在addEdge时会将两个顶点互相连接,而有向图只能按照指定方向将这两...
  • 上次我们介绍了的最短路径算法的实现,这次介绍基于邻接表的拓扑排序算法的实现。还是老规矩:程序在码云上可以下载。 地址:https://git.oschina.net/601345138/DataStructureCLanguage.git本次拓扑排序程序共用...
  • 请输出任意一个该有向图拓扑序列,如果拓扑序列不存在,则输出-1。 若一个由图中所有点构成的序列A满足:对于图中的每条边(x, y),x在A中都出现在y之前,则称A是该图的一个拓扑序列。 输入格式 第一行包含两个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 20,910
精华内容 8,364
关键字:

有向图拓扑排序算法