- 浏览: 583809 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
无前趋的顶点优先的拓扑排序方法
该方法的每一步总是输出当前无前趋(即人度为零)的顶点,其抽象算法可描述为:
NonPreFirstTopSort(G){//优先输出无前趋的顶点
while(G中有人度为0的顶点)do{
从G中选择一个人度为0的顶点v且输出之;
从G中删去v及其所有出边;
}
if(输出的顶点数目<|V(G)|)
//若此条件不成立,则表示所有顶点均已输出,排序成功。
Error("G中存在有向环,排序失败!");
}
测试:
运行:
C:\>java GraphTest
拓扑排序的结果为:
4 2 1 3 5 0
下载源码
该方法的每一步总是输出当前无前趋(即人度为零)的顶点,其抽象算法可描述为:
NonPreFirstTopSort(G){//优先输出无前趋的顶点
while(G中有人度为0的顶点)do{
从G中选择一个人度为0的顶点v且输出之;
从G中删去v及其所有出边;
}
if(输出的顶点数目<|V(G)|)
//若此条件不成立,则表示所有顶点均已输出,排序成功。
Error("G中存在有向环,排序失败!");
}
import java.util.Arrays; import java.util.List; import java.util.ArrayList; import java.util.Stack; public class Graph { int vertexNum; //图的顶点数 ArrayList<ArrayList<Integer>> table; //图的邻接表,table.get(i)存放与i邻接的顶点 Stack<Integer> stack; //存放入度为0的顶点 int[] result; //拓朴排序的结果 int[] in;// 入度,in[i]表示顶点i的入度 /** * * 构造一个图 * * @param num * 图的顶点数 * */ public Graph(int num) { vertexNum = num; table = new ArrayList<ArrayList<Integer>> (vertexNum); for(int i=0;i<vertexNum;i++) table.add(new ArrayList<Integer>()); stack = new Stack<Integer>(); result = new int[vertexNum]; in = new int[vertexNum]; } /** * 向图中添加无向边 * * @param I * 边的一个顶点 * @param J * 边的另一个顶点 * @return 是否添加成功 */ public boolean addEdge(int I, int J) { /** * 判断用户输入的是否是一个顶点,如果是,则返回flase,添加不成功 */ if (J == I) { return false; } /** * 判断所输入的顶点值是否在图所顶点范围值内,如果不在,则提示顶点不存在 * */ if (I < vertexNum && J < vertexNum && I >= 0 && J >= 0) { /** * * 判断边是否存在 */ if (isEdgeExists(I, J)) { return false; } /** * 添加边,将孤头的入度加1 */ table.get(I).add(J); in[J]++; return true; } return false; } /** * 判断有向边是否存在 * * @param i * 要查询的有向边的一个孤尾 * @param j * 要查询的有向边的另一个孤头 * @return 边是否存在,false:不存在,true:存在 */ public boolean isEdgeExists(int i, int j) { /** * 判断所输入的顶点值是否在图所顶点范围值内,如果不在,则提示顶点不存在 * */ if (i < vertexNum && j < vertexNum && i >= 0 && j >= 0) { if (i == j) { return false; } /** * 判断i的邻接结点集是否为空 */ if (table.get(i) == null) { return false; } /** * 判断这条边是否存在,如果存在,则提示边已经存在 */ for (int q = 0; q < table.get(i).size(); q++) { if (((Integer) table.get(i).get(q)).intValue() == j) { System.out.println("顶点" +i+"和"+"顶点"+j+ "这两点之间存在边"); return true; } } } return false; } public void TopSort() { //无前趋的顶点优先的拓扑排序方法 for (int i = 0; i < vertexNum; i++) //无前趋的顶点入栈 if (in[i] == 0) stack.push(i); int k = 0; while (!stack.isEmpty()) { result[k] = (Integer) stack.pop(); //弹出一个无前趋的顶点,并放入拓扑排序的结果集 if (table.get(result[k]) != null) { //这个顶点的邻接表非空 for (int j = 0; j < table.get(result[k]).size(); j++) { int temp = (Integer) table.get(result[k]).get(j); //对result[k]每一个邻接点进行入度减1操作 if (--in[temp] == 0) { //如果temp的入度为0,进栈. stack.push(temp); } } } k++; } if (k < vertexNum) { System.out.println("有回路"); System.exit(0); } } public int[] getResult() { return result; } }
测试:
import java.util.List; public class GraphTest { public static void main(String args[]){ Graph graph = new Graph(6); graph.addEdge(1, 0); graph.addEdge(2, 0); graph.addEdge(3, 0); graph.addEdge(1, 3); graph.addEdge(2, 3); graph.addEdge(3, 5); graph.addEdge(4, 2); graph.addEdge(4, 3); graph.addEdge(4, 5); graph.TopSort(); int[] list = graph.getResult(); System.out.println("拓扑排序的结果为:"); for(int i : list){ System.out.print(i+" "); } } }
运行:
C:\>java GraphTest
拓扑排序的结果为:
4 2 1 3 5 0
下载源码
发表评论
-
图的深搜+回溯练习题:POJ2197
2013-01-18 15:53 1526POJ 2197题意: 给定n个城市及其之间的距离,以及距 ... -
图的练习题(有解答)
2012-12-27 22:23 26111. 填空题 ⑴ 设无向图G ... -
邻接表实现图的广搜和深搜(java模板)
2012-12-11 17:04 2404//邻接表实现图的广搜和深搜(java模板) impor ... -
邻接矩阵实现图的广搜和深搜(java模板)
2012-12-10 20:37 1839经常要用到,放到这里备用!! //邻接矩阵实现图的广搜和深搜 ... -
如何求无向图的最小环
2012-11-13 19:02 2740POJ1734 题意:给定一个N个点的无向图,求一个最小环(各 ... -
深度优先搜索输出有向图中的所有环(JAVA)
2012-11-06 14:22 9549如图:求出有向图的所有环。 import java.uti ... -
三种算法(Floyd、Dijkstra、SPFA)求单源点最短路径。
2012-11-05 13:15 1777题(HDU2544): 在每年的校赛里,所有进入决赛 ... -
Dijkstra算法解HDU1874
2012-11-05 10:15 1300Dijkstra算法是用来解 ... -
SPFA算法求单源最短路径
2012-11-04 23:00 1864很多时候,给定的图存在负权边,这时类似Dijkstra等算法 ... -
图解Bellman-Ford算法
2012-11-03 19:39 5819Bellman-Ford算法: ... -
Bellman-Ford算法教学PPT
2012-11-03 12:06 1398Dijkstra算法是处理单源最短路径的有效算法,但它 ... -
昆虫的同性恋
2012-11-01 19:21 1352题目大意: 输入一个数t,表示测试组数。然后每组第一行两 ... -
拓扑排序入门练习
2012-11-01 16:51 1531拓扑排序简单来说 ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 3985一、什么是并查集 ... -
Kruskal算法和prim算法求最小生成树学习小结(JAVA)
2012-10-26 14:02 4963prim算法是用来实现图最小生成树的2种常用方法之一,P ... -
图的邻接表存储及遍历(JAVA)
2012-10-10 10:58 5354为图的每个顶点所发出的边建立一个单链表,用一顶点数组存储 ... -
弗洛伊德(Floyd)算法求任意两点间的最短路径
2012-10-01 07:46 6219Floyd-Warshall算法(Floyd-Warsha ... -
单源最短路径( Dijkstra算法)JAVA实现
2012-09-14 14:30 9033单源最短路径问题,即在图中求出给定顶点到其它任一顶 ... -
深度优先搜索与有向无环图的拓扑排序(java实现)
2012-09-11 13:05 5467当每个任务有前后置关系时,需要找到一种满足前后置关系的路 ... -
最小生成树:Kruskal(克鲁斯卡尔)算法实现(java)
2012-09-01 20:50 2592算法描述:Kruskal(克鲁斯卡尔)算法需要对图的边进行访问 ...
相关推荐
任意给定一个有向图,设计一个算法,对它进行拓扑排序。拓扑排序算法思想:a.在有向图中任选一个没有前趋的顶点输出;b.从图中删除该顶点和所有以它为...或者直到图中没有无前趋的顶点为止,此情形表明有向图中存在环。
解决拓扑排序的方法如下: (1)在有向图中选一个没有前驱的顶点且输出之。 (2)从图中删除该顶点和所有以它为尾的弧。 重复上述两步,直至全部顶点均已输出,或者当前图中不存在无前驱的顶点为止。后一种情况则...
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑...
题目内容:输出有向网的拓扑排序序列。 拓扑排序的基本思想为: 1)从有向图中选出一个无前驱的顶点输出; 2)将此顶点和以他为起点的弧删除; 3)重复1)2)直到不存在无前驱的顶点; 4)若此时输出的顶点数小于有...
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑...
拓扑排序与关键路径,在日常生活中,一项大的工程可以看作是由若干个子工程(这些子工程称为“活动” )组成的集合,这些子工程(活动)之间必定存在一些先后关系,即某些子工程(活动)必须在其它一些子工程(活动...
图的拓扑排序(有向图),用一个矩阵存储,环境为VC6.0
使用c语言写的一个拓扑排序小程序,希望对大家的学习有用,包含有实验报告
对于有向图,若发现它是有环的,那么输出它的环,否则,就输出它的拓扑排序
aov网和拓扑排序PPT学习教案.pptx
题目:图的存储结构及拓扑排序 从键盘或文件读入有向图的顶点信息和弧信息(输入格式自拟); 建立有向图的十字链表存储结构; 利用拓扑排序方法判断该图是否为有向无环图。
对给定的AOV网判断网中是否存在环,检测的办法是对有向图构造其顶点的拓扑有序序列,若网中所有顶点都在它的拓扑有序序列中,则该AOV网中必定不存在环。在拓扑排序的基础上实现关键路径的的求解。
图的遍历#include #include #define max 100 //定义节点... printf("此拓扑排序树无环\n"); else printf("此拓扑排序树有环\n"); printf(" \n非递归深度优先遍历结果为:"); fdgsmap(maps); printf("\n"); }
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若,v> ∈E(G),则u在线性序列中出现在v之前。
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若,v> ∈E(G),则u在线性序列中出现在v之前。
或者直到图中没有无前趋的顶点为止,此情形表明有向图中存在环。 设计分析: 为实现对无权值有向图进行拓扑排序,输出拓扑序列,先考虑如何存储这个有向图。拓 扑排序的过程中要求找到入度为0的顶点,所以要采用邻接...
要求输出的拓扑排序结果用顶点序号或字母表示。输出结果需存于字符文件。输出结果中应显示全部拓扑排序序列的数目。如果DAG存在环(即拓扑排序失败),输出结果中应显示拓扑排序序列的数目为0。 课程设计报告要求给...
逆邻接表实现拓扑排序,能够更快速直接的计算顶点的入度,即终点指向结点,有几个边表,则代表入度是几
将凸包的顶点按逆时针的顺序排序,代码用java实现,已经亲测验证成功