- 浏览: 604189 次
- 来自: ...
文章分类
最新评论
-
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 1679POJ 2197题意: 给定n个城市及其之间的距离,以及距 ... -
图的练习题(有解答)
2012-12-27 22:23 26581. 填空题 ⑴ 设无向图G ... -
邻接表实现图的广搜和深搜(java模板)
2012-12-11 17:04 2463//邻接表实现图的广搜和深搜(java模板) impor ... -
邻接矩阵实现图的广搜和深搜(java模板)
2012-12-10 20:37 1919经常要用到,放到这里备用!! //邻接矩阵实现图的广搜和深搜 ... -
如何求无向图的最小环
2012-11-13 19:02 2797POJ1734 题意:给定一个N个点的无向图,求一个最小环(各 ... -
深度优先搜索输出有向图中的所有环(JAVA)
2012-11-06 14:22 9626如图:求出有向图的所有环。 import java.uti ... -
三种算法(Floyd、Dijkstra、SPFA)求单源点最短路径。
2012-11-05 13:15 1865题(HDU2544): 在每年的校赛里,所有进入决赛 ... -
Dijkstra算法解HDU1874
2012-11-05 10:15 1364Dijkstra算法是用来解 ... -
SPFA算法求单源最短路径
2012-11-04 23:00 1943很多时候,给定的图存在负权边,这时类似Dijkstra等算法 ... -
图解Bellman-Ford算法
2012-11-03 19:39 5941Bellman-Ford算法: ... -
Bellman-Ford算法教学PPT
2012-11-03 12:06 1456Dijkstra算法是处理单源最短路径的有效算法,但它 ... -
昆虫的同性恋
2012-11-01 19:21 1398题目大意: 输入一个数t,表示测试组数。然后每组第一行两 ... -
拓扑排序入门练习
2012-11-01 16:51 1582拓扑排序简单来说 ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 4070一、什么是并查集 ... -
Kruskal算法和prim算法求最小生成树学习小结(JAVA)
2012-10-26 14:02 5051prim算法是用来实现图最小生成树的2种常用方法之一,P ... -
图的邻接表存储及遍历(JAVA)
2012-10-10 10:58 5427为图的每个顶点所发出的边建立一个单链表,用一顶点数组存储 ... -
弗洛伊德(Floyd)算法求任意两点间的最短路径
2012-10-01 07:46 6304Floyd-Warshall算法(Floyd-Warsha ... -
单源最短路径( Dijkstra算法)JAVA实现
2012-09-14 14:30 9127单源最短路径问题,即在图中求出给定顶点到其它任一顶 ... -
深度优先搜索与有向无环图的拓扑排序(java实现)
2012-09-11 13:05 5543当每个任务有前后置关系时,需要找到一种满足前后置关系的路 ... -
最小生成树:Kruskal(克鲁斯卡尔)算法实现(java)
2012-09-01 20:50 2635算法描述:Kruskal(克鲁斯卡尔)算法需要对图的边进行访问 ...
相关推荐
### 拓扑排序Java实现知识点详解 #### 一、拓扑排序概念 拓扑排序是一种针对有向无环图(DAG)进行排序的方法,主要用于确定任务执行的顺序。在实际应用中,例如项目管理中的任务调度、依赖关系解析等场景下非常...
对于给定的"本周算法图的拓扑排序Java开发Java经验技巧共6页.pdf.zip"文件,很可能是包含了一篇关于拓扑排序在Java编程实践中的详细教程或指南,内容可能包括理论解释、代码示例、常见问题以及优化技巧。通过阅读这...
数据结构中的拓扑排序是一种对有向无环图(DAG)进行排序的方法,使得所有有向边都从排序序列中的较前位置指向较后位置。在这个课程设计中,使用Java语言实现了拓扑排序算法。 拓扑排序的目标是将DAG的顶点排成线性...
拓扑排序是对有向无环图的顶点进行线性排序的一种方式,使得对于图中的每一条有向边 (u, v),顶点 u 的排序位置都位于顶点 v 之前。换句话说,如果存在一条从节点 A 到节点 B 的路径,那么在拓扑排序的结果中,A ...
拓扑排序是一种对有向无环图(DAG,Directed Acyclic Graph)进行线性排序的方法,使得对于图中的每一条有向边uv,都有u出现在排序结果的前面。 紧缩图的邻接表是一种优化的图存储结构,它将原邻接表中每个顶点的...
拓扑排序是对有向无环图的顶点的一种线性排序,使得对于图中的每条有向边 (u, v),顶点 u 在排序结果中都出现在顶点 v 之前。如果存在多种满足条件的排序,那么所有这些排序都是正确的。 在实际应用中,拓扑排序...
DFS适合查找路径或进行拓扑排序,而BFS则更适合寻找最短路径或检查连通性。在Java中,通过适当的递归或迭代算法结合数据结构(如栈或队列),我们可以有效地实现这两种遍历方法,从而在各种图形应用中解决问题。
- 拓扑排序:在有向无环图中,优先队列可以用来找到入度为零的顶点并按顺序处理它们。 - Dijkstra最短路径算法:用于找到图中两个节点之间的最短路径,每次从优先队列中取出距离源点最近的节点进行扩展。 - ...
另一方面,拓扑排序是将有向无环图(DAG)的顶点线性排列的一种方式,如果存在环,则无法进行拓扑排序,因此可以借此判断图中是否有环。 在`Graph.java`中,可能会有一个名为`detectCycle`的函数,它使用DFS进行...
- 拓扑排序:在有向无环图(DAG)中,DFS可以用于拓扑排序,确定节点的顺序。 5. **代码示例**: 在Java中,使用递归实现二叉树的DFS遍历(前序、中序、后序)如下: ```java class TreeNode { int val; ...
拓扑排序是对于有向无环图(DAG)的操作,它返回一个线性的顶点序列,使得对于每条有向边 (u, v),顶点u都在顶点v之前。Kahn算法是一种常见的拓扑排序实现,它通过选择入度为零的顶点并移除,然后更新其他顶点的入度...
在实际应用中,DFS寻找环的算法广泛应用于各种场景,如检测图的连通性、解决拓扑排序问题、查找图的强连通分量等。了解并熟练掌握这种算法对于IT从业者来说是非常重要的,因为它可以帮助解决很多实际问题,例如在...
3. **拓扑排序**:在有向无环图(DAG)中,DFS可以用来进行拓扑排序,将所有节点按照没有前驱的顺序排列。 4. **迷宫求解**:DFS也可以应用于二维数组表示的迷宫问题,从起点开始,不断尝试所有可能的路径,直到找到...
在Java中,我们可以采用两种主要方法来实现拓扑排序:深度优先搜索(DFS)和广度优先搜索(BFS)。接下来,我们将详细讨论这两种方法。 1. 深度优先搜索(DFS)实现: DFS是一种递归的搜索策略,它首先访问一个节点...
2. **构建拓扑排序**:利用拓扑排序,我们可以将无向图的顶点按照入度(指向该顶点的边数)排序。对于强连通分量,其所有顶点的入度和出度都是相同的。 3. **判断强连通性**:遍历排序后的顶点,如果发现一个顶点的...
理解并掌握DFS算法对于解决计算机科学中的许多问题至关重要,包括图的遍历、最短路径问题、拓扑排序等。 通过深入学习DFS,Java开发者可以更好地处理与图和树相关的复杂问题,提升编程能力和算法理解。此外,掌握...
有向无环图(DAG)常用于表示事件的先后关系,如拓扑排序和关键路径。 查找是指在一个数据集合中查找满足某些条件的数据元素。顺序查找是最简单的一种查找方法,折半查找则是基于有序数组的高效查找方法。查找树如...
拓扑排序是对有向无环图(DAG,Directed Acyclic Graph)的顶点的一种线性排序,其中对于每条有向边 `(u, v)`,顶点 `u` 总是出现在顶点 `v` 之前。给定的有向图 G 可以通过深度优先搜索(DFS)或广度优先搜索(BFS...