当每个任务有前后置关系时,需要找到一种满足前后置关系的路线,将任务完成。
如果将每个任务看成一个节点,任务之间的前后置关系表示为有向图时,这种路线顺序叫做为图进行拓扑排序。也叫关键路径分析。
这里的图用邻接矩阵法表示,算法的关键是:
1 找到一个没有后继的顶点
2 在图中删除它,放入结果数组中
3 重复 步骤 1 ,步骤 2 直到图中没有多余的节点。
如果图中出现环装结构,则算法无法进行,因为此时任务之间循环成为前置。
关于邻接矩阵法请参见:Graph 图-邻接表法。
要注意的是:满足前后置关系的路径可能不止一条。这里仅仅得到其中的一条。
关键API:
int noNext():返回没有后继的节点的下标。
remove(int index):删除指定下标的节点,同时在邻接矩阵中删除相对应的行与列。
main:提供简单的测试。
代码如下:
class Vertex { //图中的节点
private Object value;
Vertex(Object value) {
this.value = value;
}
Object value() { return value; }
@Override public String toString() { return "" + value; }
}
class Topology { //用邻接矩阵法表示的图
private Vertex[] vertexs;
private Object[][] adjMat; //记载是否联通
private int length = 0;
private static Object CONN = new Object(); //标致是否联通
Topology(int size) {
vertexs = new Vertex[size];
adjMat = new Object[size][size];
}
void add(Object value) {
assert length <= vertexs.length;
vertexs[length++] = new Vertex(value);
}
void connect(int from, int to) {
assert from < length;
assert to < length;
adjMat[from][to] = CONN; //标志联通
}
void remove(int index) { //移除指定的顶点
remove(vertexs,index); //在顶点数组中删除指定位置的下标
for(Object[] bs: adjMat) remove(bs,index); //邻接矩阵中删除指定的列
remove(adjMat,index); //在邻接矩阵中删除指定的行
length--;
}
private void remove(Object[] a, int index) { //在数组中移除指定的元素,后面的元素补上空位
for(int i=index; i<length-1; i++) a[i] = a[i+1];
}
int noNext() { //寻找没有后继的节点
int result = -1;
OUT:
for(int i=0; i<length; i++) {
for(int j=0; j<length; j++) {
if(adjMat[i][j] == CONN)continue OUT; //如果有后继则从外循环继续寻找
}
return i; //如果没有与任何节点相连,则返回该节点下标
}
return -1; //否则返回-1
}
Object[] topo() {
Object[] result = new Object[length]; //准备结果数组
int index;
int pos = length;
while(length > 0) {
index = noNext(); //找到第一个没有后继的节点
assert index != -1 : "图中存在环";
result[--pos] = vertexs[index]; //放入结果中
remove(index); //从图中把它删除
}
return result;
}
public static void main(String[] args) {
Topology g = new Topology(20);
g.add('a');
g.add('b');
g.add('c');
g.add('d');
g.add('e');
g.add('f');
g.add('g');
g.add('h');
g.connect(0,3);
g.connect(0,4);
g.connect(1,4);
g.connect(2,5);
g.connect(3,6);
g.connect(4,6);
g.connect(5,7);
g.connect(6,7);
for(Object o: g.topo()) System.out.print(o + " ");
System.out.println();
}
}
分享到:
相关推荐
图 -Floyed算法 -Dijkstra算法 -拓扑排序算法
数据结构课程的课程设计,实现拓扑排序的算法
数据结构-拓扑排序.ppt该文档详细且完整,值得借鉴下载使用,欢迎下载使用,有问题可以第一时间联系作者~
非常好的源程序文件,用vc++6.0编写的拓扑排序 程序简单易懂,问题描述完善 非常有用
对于有向图进行拓扑排序,图使用邻接矩阵的存储结构。
拓扑排序------打印输出计算机本科专业4年每学期的课表 拓扑排序------打印输出计算机本科专业4年每学期的课表 拓扑排序------打印输出计算机本科专业4年每学期的课表
对各年级课程按照优先级用拓扑进行课表配置
课题二 拓扑排序 2.1 问题的提出2.1 问题的提出 任务:编写函数实现图的拓扑排序。 程序所实现的功能: 建立对应的邻接表,对该图进行拓扑排序,并显示排序结果。 输入: 顶点数, 边数及各顶点信息(数据格式为整形...
拓扑排序拓扑排序拓扑排序拓扑排序拓扑排序拓扑排序拓扑排序拓扑排序拓扑排序
C语言实现图的拓扑排序
任意给定一个有向图,设计一个算法,对它进行拓扑排序。拓扑排序算法思想:a.在有向图中任选一个没有前趋的顶点输出;b.从图中删除该顶点和所有以它为尾的弧;c.重复上述a、b,直到全部顶点都已输出,此时,顶点输出...
cpp代码-拓扑排序求最长路
基于邻接表存储的图的拓扑排序算法,学习C++和理解数据结构很有帮助
C# 图 拓扑排序
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑...
XXX大学数据结构课程设计,由个人完成,为大家提供参考。
图的最短路径、拓扑排序和关键路径相关算法描述,有c++code
实现图的拓扑排序,方法1:采用邻接表存储结构,按照堆栈的实现。 实现图的拓扑排序,方法2:采用邻接矩阵实现:
深度优先排序、广度优先排序和一种补充算法