2013-12-09 15:35:39         来源：永无止境，上下求索

## 拓扑排序算法Java实现

### 图像(Graph)的Java抽象实现

``` enum Color {
WHITE, GRAY, BLACK
}

static class Vertex {
private String name;
private Color color;
private Vertex parent;
private int discover;
private int finish;

public Vertex(String name) {
this.name = name;
this.color = Color.WHITE;
}

public String getName() {
return name;
}

public void setName(String name) {
this.name = name;
}

public Color getColor() {
return color;
}

public void setColor(Color color) {
this.color = color;
}

public Vertex getParent() {
return parent;
}

public void setParent(Vertex parent) {
this.parent = parent;
}

public int getDiscover() {
return discover;
}

public void setDiscover(int discover) {
this.discover = discover;
}

public int getFinish() {
return finish;
}

public void setFinish(int finish) {
this.finish = finish;
}

@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((name == null) ? 0 : name.hashCode());
return result;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Vertex other = (Vertex) obj;
if (name == null) {
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
return true;
}
}

static class Graph {
private Set vertexSet = new HashSet();
// 相邻的节点
private Map adjacencys = new HashMap();

public Set getVertexSet() {
return vertexSet;
}

public void setVertexSet(Set vertexSet) {
this.vertexSet = vertexSet;
}

}

}
}```

### 深度优先算法

``` static class TimeRecorder {
private int time = 0;

public int getTime() {
return time;
}

public void setTime(int time) {
this.time = time;
}
}

public static Vertex[] topologicalSort(Graph graph) {
Set vertexSet = graph.getVertexSet();
if (vertexSet.size() < 2) {
return vertexSet.toArray(new Vertex[0]);
}

TimeRecorder recorder = new TimeRecorder();

for (Vertex vertex : vertexSet) {
if (vertex.color == Color.WHITE) {
visitVertex(graph, vertex, recorder, sortedList);
}
}

return sortedList.toArray(new Vertex[0]);
}

/**
* 深度优先搜索(Depth First Search)
*/
public static void visitVertex(Graph graph, Vertex vertex,
recorder.time += 1;
vertex.color = Color.GRAY;
vertex.discover = recorder.time;

}
}
}

recorder.time += 1;
vertex.color = Color.BLACK;
vertex.finish = recorder.time;
}```

### 构建图以及测试

```public static void main(String[] args) {
Graph graph = new Graph();
Set vertexSet = graph.getVertexSet();

Vertex twoVertex = new Vertex("2");
Vertex threeVertex = new Vertex("3");
Vertex fiveVertex = new Vertex("5");
Vertex sevenVertex = new Vertex("7");
Vertex eightVertex = new Vertex("8");
Vertex nineVertex = new Vertex("9");
Vertex tenVertex = new Vertex("10");
Vertex elevenVertex = new Vertex("11");

edgeMap.put(twoVertex, new Vertex[] { elevenVertex });
edgeMap.put(nineVertex, new Vertex[] { elevenVertex, eightVertex });
edgeMap.put(tenVertex, new Vertex[] { elevenVertex, threeVertex });
edgeMap.put(elevenVertex, new Vertex[] { sevenVertex, fiveVertex });
edgeMap.put(eightVertex, new Vertex[] { sevenVertex, threeVertex });

Vertex[] sortedVertexs = topologicalSort(graph);
printVertex(sortedVertexs);
}

public static void printVertex(Vertex[] Vertexs) {
for (Vertex vertex : Vertexs) {
System.out.println(vertex.getName() + "  discover time:"
+ vertex.getDiscover() + "  finish time:"
+ vertex.getFinish());
}
}```