精华内容
下载资源
问答
  • 有向图的拓扑排序算法(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 }
    复制代码
    展开全文
  • 一,问题描述给定一个有向图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 }
    复制代码

     

    展开全文
  • 大致题目为从一个字符串中按顺序抽取一些单字符,给出一些这样排列,然后让你恢复这个隐藏字符串,给出排列是能确定一个唯一字符串。 如给出 {'t','u','p'}, {'w','h','i'}, {'...

    这是一道Codewar上的题,地址为

    https://www.codewars.com/kata/53f40dff5f9d31b813000774

    大致题目为从一个字符串中按顺序抽取一些单字符,给出一些这样的排列,然后让你恢复这个隐藏的字符串,给出的排列是能确定一个唯一的字符串的。

    如给出

          {'t','u','p'},
          {'w','h','i'},
          {'t','s','u'},
          {'a','t','s'},
          {'h','a','p'},
          {'t','i','s'},
          {'w','h','s'}

    这样一些序对,然后恢复出字符串whatisup


     

    可以把给出的每个序对看成一些约束,从而构建一个有向图,如给出{'t','u','p'},则约束为字符串中t必须在u,p前面,u必须在p前面,从而构建三个顶点,如果a字符必须要在b字符前出现,则从a连接一条到b的边。

    知道这道题考的是什么时候就很简单了,接下来直接套用图的拓扑排序算法就可以了。

    拓扑排序在数学中可以看成一种给出偏序关系然后输出任意一个全序关系,主要有两种算法,一种是一直删除没有入度的节点,一种是一直删除没有出度的顶点。

    两者大同小异,原理也很简单,如果一个节点没有入度,那么他排在第一个当然没有什么问题,因为他前面没有东西,然后这样递归思考,每次删掉没有入度的节点以及他往外连接的边,这样一直运行直到没有节点,就给出了一个可能的全序排列,或者该图存在一个环则无法给出答案。

    接下来上代码

    /**
     * 一个简易的代表有向图节点的类
     */
    class LetterNode {
        public Character letter;
        //所有的连接到该节点的节点
        public LinkedList<LetterNode> parents = new LinkedList<>();
        //所有的从该节点连出去的节点
        public LinkedList<LetterNode> childs = new LinkedList<>();
    
        public LetterNode(Character letter) {
            this.letter = letter;
        }
    
        public void linkTo(LetterNode letterNode) {
            letterNode.parents.add(this);
            this.childs.add(letterNode);
        }
    }
    public static String recoverSecret(char[][] triplets) {
    
        //从输入的三元组建立有向图,同时为了快速从字符查询到对应的节点,使用hashmap保存字符到节点的映射
        HashMap<Character, LetterNode> map = new HashMap<>();
        for (int y = 0; y < triplets.length; y++) {
            for (int x = 0; x < triplets[y].length; x++) {
                Character c = triplets[y][x];
                //如果该字符表示的节点不存在则创建他
                map.putIfAbsent(c, new LetterNode(c));
            }
            //按照三元组的顺序进行连接,第一个节点连到第二个节点,第二个节点连到第三个节点,同时因为传递关系这里已经隐含了第一个节点要排在第三个节点前面了
            map.get(triplets[y][0]).linkTo(map.get(triplets[y][1]));
            map.get(triplets[y][1]).linkTo(map.get(triplets[y][2]));
        }
    
        //用StringBuilder来连接单字符返回需要输出的字符串
        StringBuilder builder = new StringBuilder();
        //循环直到删完所有的节点
        while (map.keySet().size() > 0)
            for (Character character : map.keySet()) {
                LetterNode node = map.get(character);
                //找到一个没有parent,即没有入度的顶点
                if (node.parents.size() == 0) {
                    //追加到需要输出的字符串后面
                    builder.append(node.letter);
                    //删除他到所有从这出去的顶点的链接
                    node.childs.forEach(i -> {
                        i.parents.remove(node);
                    });
                    //删除这个顶点
                    map.remove(character);
                    break;
                }
            }
        return builder.toString();
    
    }

     

    算法过程已经注释的很清楚了,由于题目已经确定这些三元组会确定一个且只有一个隐藏的字符串,所以可以不用做一些找不到没有入度的顶点,图出现环怎么办之类的处理。

    说实话第一眼没有把他和图的拓扑排序联系起来,这就是为什么我觉得不能光看一些算法书不上手实际做一些题目的原因,你没法把一个基础的算法和实际结合起来,就没有办法在看到实际应用时把这个东西套进去。

     

    展开全文
  • #include #include #include //该结构体用来表示从某个顶点可以到达其他顶点 struct ENode {  int secPoint;//顶点号  ENode *next;//指向下一个顶点指针 };
  • 有向图的拓扑排序 Kahn算法
  • 图的拓扑排序定义: 给定一幅有向图, 对图中各顶点排序, 使得对于图中的任意有向边v−>wv->wv−>w, 均满足节点vvv出现在节点www之前. 我们可以很容易证明, 存在环路的有向图无法进行排序. 假设当前有向图...
  • PAGE 数据结构课程设计 设计说明书 有向图拓扑排序算法的实现 学生姓名 樊佳佳 学号 1318064017 ...数据结构课程设计 课程设计题目 图的拓扑排序算法的实现 完 成 期 限 自 2015年 12月20日至 2016年 1 月 3 日共 2 周
  • 思路: 用数组模拟链表,首先如果能用拓扑排序则其一定是有向无...请输出任意一个该有向图的拓扑序列,如果拓扑序列不存在,则输出-1。 若一个由图中所有点构成的序列A满足:对于图中的每条边(x, y),x在A中都出现在y之
  • 对一个有向无环(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得中任意一对顶点u和v,若<u,v> ∈E(G),则u在线性序列中出现在v之前。 通常,这样线性序列称为...
  •  对一个有向无环(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得中任意一对顶点u和v,若 ∈E(G),则u在线性序列中出现在v之前。  通常,这样线性序列称为满足...
  • 图的拓扑排序算法

    2018-01-05 21:55:00
    什么是图的拓扑排序? 在实际应用中,有向图的边可以看做是顶点之间制约关系的描述。把顶点看作是一个个任务,则对于有向边<Vi,Vj>表明任务Vj的启动需等到任务Vi完成...这样的一个序列就称为有向图的拓扑序列...
  • 对AOV网进行拓扑排序的基本思路是:从AOV网中选择一个入度为0顶点输出,然后删除此顶点,并删除以此顶点为尾弧,继续重复此步骤,直到输出全部顶点或者在AOV网中不存在入度为0顶点为止。 这里使用数据...
  • 表示活动i是活动j必须条件,这种有向图为顶点表示活动网简称为AOV网络。 在AOV网络中,如果活动Vi 必须在Vj 之前进行,则存在有向边<Vi,Vj>,并称Vi是Vj直接前驱,Vj是Vi直接后继;这种前驱与后继...
  • 如果一个有向图的任意顶点都无法通过一些有向边回到自身,那么称这个有向图为有向无环图。 不含环路的有向图必包含入度为零的顶点—因此一定存在拓扑排序 拓扑排序的应用 图是否存在环 拓扑排序具体算法 拓扑...
  • 一、以下为有向图 经过拓扑排序如下: 二、实现代码,首先实现拓扑排序如下: package com.tool.wpn.quicksort; ... * 图-有向图拓扑排序 */ public class GraphTopo { private fin
  • 也可以检验有向图是否存在回路。这里处理对象是邻接表。 bool ToplogicalSort(Graph G){ InitStack(S); for(int i=0;i&lt;G.vexnum;i++)//初始化栈,存储入度为0顶点 if(indegree[i]==0)Push(S,i); int ...
  • 请输出任意一个该有向图的拓扑序列,如果拓扑序列不存在,则输出-1。 若一个由图中所有点构成的序列A满足:对于图中的每条边(x, y),x在A中都出现在y之前,则称A是该图的一个拓扑序列。 输入格式 第一行包含两个...
  • #File Name : 图的拓扑排序算法.py #拓扑排序:在任何一个节点之前,所依赖的节点都做完 #找到所有入度为0的节点,这些节点代表不需要任何的依赖 #删除这些,又有新的入度为0的节点,删掉代表已经做完 #要求有向图且...
  • 有向图的拓扑排序

    2014-12-18 16:31:00
    有向图的拓扑排序 拓扑排序是可以用图模拟的另外一种操作,他可以用于表示一种情况,某些事件必须按照特定的顺序排列或者发生。,比如说课程的优先关系。 拓扑排序算法思想不一般但是算法很简单 1:找到一个没有...
  • http://blog.csdn.net/derkampf/article/details/57414185,这一篇进行拓扑排序算法的实现。 一.概念 由偏序得到全序操作称为拓扑排序。在拓扑排序之后,有向图每一个顶点都会按照一定次序进行输出。 二....
  • https://blog.csdn.net/qq_35644234/article/details/60578189拓扑排序的实现步骤在有向图中选一个没有前驱顶点并且输出从图中删除该顶点和与它有关边重复上述两步,直至所有顶点输出,或者当前图中不存在无前驱...
  • 有向图拓扑排序

    2021-05-27 21:22:40
    本文介绍有向图拓扑排序算法的思路及代码实现,首先讲解什么是拓扑排序,其次介绍实现拓扑排序需要的检测有向图是否有环的算法及顶点排序算法,最终实现有向图的拓扑排序。 一、什么是拓扑排序? 给定一副有向图,...
  • 对于有向图的结构,和无向图类似,甚至更简单,有疑问请留言。 1>有向图的数据结构 package graphTheory; /** * @author : 罗正 * @date time:2016年9月19日 下午9:26:21 **/ public class Digraph { private ...
  • 图的基础介绍和基础算法深度优先搜索,广度优先搜索在我前两篇博文中。  http://blog.csdn.net/xinzhi8/article/details/62222154 图介绍与深度优先...   当图的边有方向时,即有向图,这时图的搜索策略将发生变化

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,492
精华内容 596
关键字:

有向图的拓扑排序算法