安允沃
概述:
在现代化管理中，人们常用有向图来描述和分析一项工程的计划和实施过程，一个工程常被分为多个小的子工程，这些子工程被称为活动（Activity)，在有向图中若以顶点表示活动，有向边表示活动之间的先后关系，这样的图简称为AOV网。
AOV网
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
简单的说,就是在一个工程中,我们要先做某事,完成后才能做另一件事,比如上图,
我们要先做1和13 ,然后才能做4.
这里的1,13,4就是工程中的活动.
顶点的入度就是活动的先决条件.
我们得到工程的实时路线,就是先做那个活动再做那个活动,直到完工.就得到一组拓扑序列.
如:
13 14 15 5 1 4 8 3 10 11 12 7 9 6 2
是上图的一组拓扑序列
得到这组拓扑序列的算法就是拓扑排序算法
拓扑排序
思路:
1.从AOV网中选择一个没有前趋的顶点（即入度为零),并输出它
2.从网中删除该顶点，并且删除从该顶点发出的全部有向边
3.重复1和2
数据结构:
邻接表
如上图:
我们用邻接表来表示AOV网中的顶点和边
表中每一个元素表示一个活动.
每一个元素有下标,in表示该顶点的入度
data表示顶点的值
first链接的一个链表,表示顶点的出度,链表中的结点有两个属性
first链表中的结点
data:表示改顶点在顶点数组中的下标
next:表示另一个出度顶点
步骤:
首先我们要找出入度为0的顶点,输出
我们将入度为0的顶点全部放入一个栈中.然后依次出栈输出
出栈后要改变顶点所链接的链表中所有元素的入度.
代码:
import org.junit.Test;
public class topologicSort {
/**
* 邻接链表结点
*/
class EdgeNode {
int data;//存放顶点在顶点数组中的下标
EdgeNode next;//next结点
public EdgeNode(int data, EdgeNode next) {
this.data = data;
this.next = next;
}
}
/**
* AOV网中的顶点
*/
class VertexNode {
int in;//入度
int data;//值
EdgeNode first;//出度领接链表的头结点
public VertexNode(int in, int data, EdgeNode first) {
this.in = in;
this.data = data;
this.first = first;
}
}
//准备AOV网
VertexNode[] graphAdjList = new VertexNode[15];
@Test
public void test() {
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();
}
private void topologicalSort() {
//初始化栈,用数组表示,存放顶点在graphAdjList中的下标
int top = 0;//栈的头指针
int[] stack = new int[15];
//找出入度为0的顶点,入栈
for (int i = 0; i < graphAdjList.length; i++) {
if (graphAdjList[i].in == 0) {
stack[++top] = i;//先将top上移一位,因为取出顶点时top会下移,避免取出最后一个顶点时top会为-1.
}
}
while (top != 0) {
//出栈,输出,修改邻接链表中结点的入度
int getTop = stack[top--];//取出stack中存放的下标,top下移一位
System.out.print(graphAdjList[getTop].data + " ");//输出
for (EdgeNode e = graphAdjList[getTop].first; e != null; e = e.next) {
int k = e.data;//取出领接链表中结点的值,即该顶点在顶点数组graphAdjList中的下标
graphAdjList[k].in--;//入度--
if (graphAdjList[k].in == 0) {//入度为0就入栈
stack[++top] = k;
}
}
}
}
}
网友评论