主要为AOE网打下基础。AOE网：主要用在如何计算一个工程的完工时间，和优化工程方案减少工程完工时间
1、概念
-
AOV网：在现代化管理中，人们常用有向图来描述和分析一项工程的计划和实施过程，一个工程常被分为多个小的子工程，这些子工程被称为活动（Activity)，在有向图中若以顶点表示活动，有向边表示活动之间的先后关系，这样的图简称为AOV网。
-
拓扑排序：对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
2.png
2、排序算法
根据一下步骤：
- 从AOV网中选择一个没有前趋的顶点（即入度为零),并输出它
- 从网中删除该顶点，并且删除从该顶点发出的全部有向边
- 重复1和2
如下采用邻接表图解：
1.png
3、代码实现
import java.util.ArrayList;
import java.util.List;
/**
* AOV网与拓扑排序
* <p>
* author: bobo
* create time: 2019/1/9 3:42 PM
* email: jqbo84@163.com
*/
public class TopologicalSort<T> {
/**
* 拓扑排序算法
*
* @param graphAdjList 拓扑图数组集
* @return
*/
public List<T> topologicalSort(VertexNode[] graphAdjList) {
int top = 0; //栈顶指针, 对应索引值
int[] stack = new int[15];//用来存放入度为0的顶点，数组效率最高，存放顶点的下标索引值
//循环得到入度为0的所有顶点
for (int i = 0; i < graphAdjList.length; i++) {
VertexNode vertexNode = graphAdjList[i];
if (vertexNode.in == 0) {
stack[++top] = i;
}
}
//开始算法的逻辑
List<T> resultList = new ArrayList<>();
while (top != 0) {
int getTop = stack[top--];
resultList.add((T) graphAdjList[getTop].data);
//更新当前输出节点所有的出边（后继顶点）
for (EdgeNode e = graphAdjList[getTop].first; e != null; e = e.next) {
int index = e.index;
//入度减一
graphAdjList[index].in--;
if (graphAdjList[index].in == 0) {
stack[++top] = index;
}
}
}
return resultList;
}
/**
* 边表节点
*/
class EdgeNode {
int index; //用来存放顶点的下标索引值
EdgeNode next;
public EdgeNode(int index, EdgeNode next) {
this.index = index;
this.next = next;
}
}
/**
* 顶点表节点
*/
class VertexNode<T> {
int in;//入度
T data;
EdgeNode first;
public VertexNode(int in, T data, EdgeNode first) {
this.in = in;
this.data = data;
this.first = first;
}
}
}
4、测试
@Test
public void main() {
//根据上面的AOV网图来填写测试数据
VertexNode[] graphAdjList = new VertexNode[15];
EdgeNode a = new EdgeNode(3, null);
EdgeNode a2 = new EdgeNode(2, a);
EdgeNode a3 = new EdgeNode(1, a2);
graphAdjList[0] = new VertexNode(0, 1, a3);
graphAdjList[1] = new VertexNode(2, 2, null);
EdgeNode b1 = new EdgeNode(9, null);
EdgeNode b2 = new EdgeNode(8, b1);
EdgeNode b3 = new EdgeNode(6, b2);
EdgeNode b4 = new EdgeNode(5, b3);
graphAdjList[2] = new VertexNode(2, 3, b4);
EdgeNode c1 = new EdgeNode(7, null);
EdgeNode c2 = new EdgeNode(9, c1);
EdgeNode c3 = new EdgeNode(6, c2);
graphAdjList[3] = new VertexNode(2, 4, c3);
graphAdjList[4] = new VertexNode(1, 5, null);
graphAdjList[5] = new VertexNode(1, 6, null);
graphAdjList[6] = new VertexNode(3, 7, null);
graphAdjList[7] = new VertexNode(1, 8, null);
graphAdjList[8] = new VertexNode(1, 9, null);
EdgeNode d1 = new EdgeNode(10, null);
EdgeNode d2 = new EdgeNode(6, d1);
graphAdjList[9] = new VertexNode(2, 10, d2);
EdgeNode e1 = new EdgeNode(11, null);
graphAdjList[10] = new VertexNode(1, 11, e1);
graphAdjList[11] = new VertexNode(1, 12, null);
EdgeNode f1 = new EdgeNode(3, null);
EdgeNode f2 = new EdgeNode(13, f1);
graphAdjList[12] = new VertexNode(0, 13, f2);
EdgeNode g1 = new EdgeNode(14, null);
EdgeNode g2 = new EdgeNode(1, g1);
EdgeNode g3 = new EdgeNode(2, g2);
graphAdjList[13] = new VertexNode(1, 14, g3);
EdgeNode h1 = new EdgeNode(4, null);
graphAdjList[14] = new VertexNode(1, 15, h1);
//测试
TopologicalSort sort = new TopologicalSort();
List<Integer> result = (List<Integer>) sort.topologicalSort(graphAdjList);
for (int i = 0; i < result.size(); i++) {
System.out.print(" " + result.get(i));
}
}
5、结果
//根据上面的AOV网图测试结果
13 14 15 5 1 4 8 3 10 11 12 7 9 6 2
网友评论