一级压一级 将0入度的输出，之后入度为入度为0的，入度减1，直到入度为0才能输出
通过邻接表与栈实现
-
算法准备
a. 邻接表
b. 最小权值数组least
c. 上一个顶点下标数组lastIndex
d. 最小权值和sum
-
算法思路 a. 创建栈，用于保存入度为0的邻接元素下标
b. 循环邻接数组，将入度为0的压入栈中
c. 循环栈，弹出栈顶下标，输出该顶点值
d. 循环边元素，取得边的出度顶点下标，通过下标取得邻接表顶点值
e. 将出度顶点的入度数-1，如果此时入度为0，则将该下标压入栈中
public class Graph<T extends Comparable<T>> {
// 顶点数组
private T[] vertexs;
// 邻接表元素数组
private VertexNeighborNode<T>[] neighborArray;
// 邻接矩阵
private int[][] matrix;
// 泛型对象的类文件
private Class<T> Class;
// 顶点数量
private int size;
// 常亮：未连接
public static final int NO_LINK = -1;
/**
* 拓扑排序方法
* @throws Exception
*/
public void Topologic() throws Exception {
// 创建栈，用于添加入度为0的邻接元素下标
Stack<Integer> zero = new Stack<Integer>();
// 创建拓扑排序数量
int count = 0;
// 循环邻接表元素数组
for (int i = 0; i < size; i++) {
// 如果当前元素的入度数量为0
if (neighborArray[i].getIn() == 0) {
// 将当前元素的下标压入栈中
zero.push(i);
}
}
// 如果栈不为空，遍历栈
while (!zero.isEmpty()) {
// 弹出栈顶的下标
int zeroIndex = zero.pop();
// 输出该顶点的下标和值
System.out.println(zeroIndex + ":" + vertexs[zeroIndex]);
// 拓扑数量自增
count++;
// 遍历入度为0的邻接表元素的度元素
for (EdgeNode e = neighborArray[zeroIndex]
.getFirstEdge(); e != null; e = e.getNext()) {
// 取得弧尾顶点的下标（顶点的出度顶点）
int nextIndex = e.getIndex();
// 通过下标取得邻接表数组元素
VertexNeighborNode<T> v = neighborArray[nextIndex];
// 将该元素的入度减1，证明该元素的入度有一个已遍历过
v.setIn(v.getIn() - 1);
// 如果该元素的当前入度为0，则
if (v.getIn() == 0) {
// 将该元素的下标压入栈中
zero.push(nextIndex);
}
}
}
// 如果遍历过的顶点数量不是全部顶点数量
if (count != size) {
// 则代表拓扑失败，有回环
throw new Exception("拓扑失败！有回环");
}
}
}
邻接表元素类
/**
*
* ClassNameCh 邻接表元素
* ClassNameEn VertexNeighborNode
* Description 邻接表数组的元素，包括该顶点的第一条边
* Company
* @author Naah
* @date 2017年8月17日 下午9:25:59
* @param <T>
*/
public class VertexNeighborNode<T> {
// 入度数
private int in;
// 边节点
private EdgeNode firstEdge;
public VertexNeighborNode(int in) {
super();
this.in = in;
}
public int getIn() {
return in;
}
public void setIn(int in) {
this.in = in;
}
public EdgeNode getFirstEdge() {
return firstEdge;
}
public void setFirstEdge(EdgeNode firstEdge) {
this.firstEdge = firstEdge;
}
@Override
public String toString() {
return "[in=" + in + ", firstEdge=" + firstEdge + "]";
}
}
边界点类
/**
*
* ClassNameCh 边节点
* ClassNameEn EdgeNode
* Description 边节点 ，用于记录该顶点的出度顶点
* Company
* @author Naah
* @date 2017年8月17日 下午9:27:19
*/
public class EdgeNode {
// 出度顶点下标
private int index;
// 下一个出度顶点的引用
private EdgeNode next;
// 权值
private int weight;
public EdgeNode(int index) {
super();
this.index = index;
}
public EdgeNode(int index, int weight) {
super();
this.index = index;
this.weight = weight;
}
public int getIndex() {
return index;
}
public void setIndex(int index) {
this.index = index;
}
public EdgeNode getNext() {
return next;
}
public void setNext(EdgeNode next) {
this.next = next;
}
@Override
public String toString() {
return "EdgeNode [index=" + index + ", next=" + next + ", weight="
+ weight + "]";
}
}
