# 有向图的拓扑排序算法JAVA实现

+关注继续查看

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

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

 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     }

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

 1 import java.util.Collection;
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;// 顶点标识
16         private int inDegree;// 该顶点的入度
17
18         public Vertex(String verTtexLabel) {
19             this.vertexLabel = verTtexLabel;
20             inDegree = 0;
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);//每读入一行代表一条边
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.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);
// 当文件不存在或者不可读时
{
System.out.println("file [" + filePath + "] is not exist or cannot read!!!");
return null;
}

StringBuffer sb = new StringBuffer();
try
{

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;
}

// 当文件存在但不可写时
{
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;
}
}

 1publicclass TestTopoSort {
2publicstaticvoid main(String[] args) {
3        String graphFilePath;
4if)
5;
6else 7];
8 9null//从文件中读取图的数据10new DirectedGraph(graphContent);
11try{
12            directedGraph.topoSort();
13catch(Exception e){
14);
15            e.printStackTrace();
16        }
17    }
，如需转载请自行联系原作者

Java实现3DES加解密算法（2）
Java实现3DES加解密算法（2）
39 0
Java实现3DES加解密算法（1）
Java实现3DES加解密算法（1）
154 0
【Java设计模式】UML类图六大关系总结(含代码)（一）
【Java设计模式】UML类图六大关系总结(含代码)（一）
1410 0
Java Web技术总结

1115 0
【Java】归并排序算法

3011 0
Java排序算法 归并排序

774 0
+关注
2968

0