- 浏览: 583856 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
拓扑排序简单来说就是把一个图的所有节点排序,使得每一条有向边(u,v)对应的u都排在v的前面。 拓扑排序最大的用途就是判断一个有向图是否有环。
无前趋的顶点优先的拓扑排序方法
该方法的每一步总是输出当前无前趋(即人度为零)的顶点,其抽象算法可描述为:
NonPreFirstTopSort(G){//优先输出无前趋的顶点
while(图G中有人度为0的顶点)do{
从G中选择一个人度为0的顶点v且输出之;
从G中删去v及其所有出边;
}
if(输出的顶点数目<|V(G)|)
//若此条件不成立,则表示所有顶点均已输出,排序成功。
Error("G中存在有向环,排序失败!");
}
性质
1、 拓扑排序在有向无环图中才能排出有效的序列,否则能判断该有向图有环。
2、如果输入的有向图中的点,不存在入度为0的点,则该有向图存在回路
3、如果存在的入度为0的点大于一个,则该有向图肯定不存在一个可以确定的拓扑序列但并不妨碍拓扑排序
例: 有N个比赛队(1<=N<=500),编号依次为1,2,3,。。。。,N进行比赛,比赛结束后,裁判委员会要将所有参赛队伍从前往后依次排名,但现在裁判委员会不能直接获得每个队的比赛成绩,只知道每场比赛的结果,即P1赢P2,用P1,P2表示,排名时P1在P2之前。现在请你编程序确定排名。
Input
输入有若干组,每组中的第一行为二个数N(1<=N<=500),M;其中N表示队伍的个数,M表示接着有M行的输入数据。
接下来的M行数据中,每行也有两个整数P1,P2表示即P1队赢了P2队。
Output
给出一个符合要求的排名。输出时队伍号之间有空格,最后一名后面没有空格。
其他说明:符合条件的排名可能不是唯一的,此时要求输出时编号小的队伍在前;
输入数据保证是正确的,即输入数据确保一定能有一个符合要求的排名。
Sample Input
4 3
1 2
2 3
4 3
Sample Output
1 2 4 3
典型的拓扑排序算法
无前趋的顶点优先的拓扑排序方法
该方法的每一步总是输出当前无前趋(即人度为零)的顶点,其抽象算法可描述为:
NonPreFirstTopSort(G){//优先输出无前趋的顶点
while(图G中有人度为0的顶点)do{
从G中选择一个人度为0的顶点v且输出之;
从G中删去v及其所有出边;
}
if(输出的顶点数目<|V(G)|)
//若此条件不成立,则表示所有顶点均已输出,排序成功。
Error("G中存在有向环,排序失败!");
}
性质
1、 拓扑排序在有向无环图中才能排出有效的序列,否则能判断该有向图有环。
2、如果输入的有向图中的点,不存在入度为0的点,则该有向图存在回路
3、如果存在的入度为0的点大于一个,则该有向图肯定不存在一个可以确定的拓扑序列但并不妨碍拓扑排序
例: 有N个比赛队(1<=N<=500),编号依次为1,2,3,。。。。,N进行比赛,比赛结束后,裁判委员会要将所有参赛队伍从前往后依次排名,但现在裁判委员会不能直接获得每个队的比赛成绩,只知道每场比赛的结果,即P1赢P2,用P1,P2表示,排名时P1在P2之前。现在请你编程序确定排名。
Input
输入有若干组,每组中的第一行为二个数N(1<=N<=500),M;其中N表示队伍的个数,M表示接着有M行的输入数据。
接下来的M行数据中,每行也有两个整数P1,P2表示即P1队赢了P2队。
Output
给出一个符合要求的排名。输出时队伍号之间有空格,最后一名后面没有空格。
其他说明:符合条件的排名可能不是唯一的,此时要求输出时编号小的队伍在前;
输入数据保证是正确的,即输入数据确保一定能有一个符合要求的排名。
Sample Input
4 3
1 2
2 3
4 3
Sample Output
1 2 4 3
典型的拓扑排序算法
import java.util.*; 方法一:(邻接矩阵实现图存储) public class Main { private int n, m; private int[] indegree;// 顶点的入度 private int[] result;// 保存最后排好序的结果 private int[][] G;// 邻接矩阵存储 private Queue<Integer> que;//存入入度为0的顶点 public Main(int n,int m,int[] indegree,int[][] G){ this.n=n; this.m=m; this.indegree=indegree; this.G=G; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int[][] G; int[] indegree; int n,m; while (sc.hasNext()) { n = sc.nextInt(); m = sc.nextInt(); G = new int[n + 1][n + 1]; indegree = new int[n + 1]; while (m-- > 0) { int u = sc.nextInt(); int v = sc.nextInt(); if (G[u][v] == 0) {// 这个条件一定要,避免重边的情况比如a b可能出现两次的情况 indegree[v]++; G[u][v] = 1; } } Main ma=new Main(n,m,indegree,G); ma.topsort(); } } private void topsort() { result = new int[n + 1]; que = new PriorityQueue<Integer>();//同名次时,序号小的排前,所以用优先队列 int index = 0; for (int i = 1; i <= n; i++) {//找出图中所有入度为O的顶点 if (indegree[i] == 0) que.add(i);//编号小的在前 } while (!que.isEmpty()) { int u = que.poll(); result[++index] = u; for (int i = 1; i <= n; i++) { if (G[u][i] == 1) { indegree[i]--;//模拟删除顶点,i的入度减1 if (indegree[i] == 0) que.add(i); } } } // 输出 System.out.print(result[1]); for (int i = 2; i <= n; i++) { System.out.print(" "+result[i]); } System.out.println(); } } import java.util.*; 方法二:拓扑排序(使用邻接表实现) public class Main{ private int n, m; private int[] indegree;// 顶点的入度 private int[] result;// 保存最后排好序的结果 private List<ArrayList<Integer>> G;// 邻接表。 private Queue<Integer> que; public Main(int n,int m,int[] indegree,List<ArrayList<Integer>> G){ this.n=n; this.m=m; this.indegree=indegree; this.G=G; } public static void main(String[] args) { int n,m; int[] indegree; List<ArrayList<Integer>> G; Scanner sc = new Scanner(System.in); while (sc.hasNext()) { n = sc.nextInt(); m = sc.nextInt(); G = new ArrayList<ArrayList<Integer>>(); for(int i = 1;i<=n+1;i++) G.add(new ArrayList<Integer>());//初始化邻接表 indegree = new int[n + 1]; while (m-- > 0) { int u = sc.nextInt(); int v = sc.nextInt(); if (!G.get(u).contains(v)) {// 这个条件一定要,避免重边的情况比如a b可能出现两次的情况 indegree[v]++; G.get(u).add(v); } } Main ma=new Main(n,m,indegree,G); ma.topsort(); } } private void topsort() { result = new int[n + 1]; que = new PriorityQueue<Integer>(); int index = 0; for (int i = 1; i <= n; i++) { if (indegree[i] == 0) que.add(i); } while (!que.isEmpty()) { int v = que.poll(); result[++index] = v; for (int i : G.get(v)) { indegree[i]--; if (indegree[i] == 0) que.add(i); } } // 输出 System.out.print(result[1]); for (int i = 2; i <= n; i++) { System.out.print(" " + result[i]); } System.out.println(); } }
- hdu1285.zip (1.8 KB)
- 下载次数: 3
发表评论
-
图的深搜+回溯练习题:POJ2197
2013-01-18 15:53 1526POJ 2197题意: 给定n个城市及其之间的距离,以及距 ... -
图的练习题(有解答)
2012-12-27 22:23 26111. 填空题 ⑴ 设无向图G ... -
邻接表实现图的广搜和深搜(java模板)
2012-12-11 17:04 2405//邻接表实现图的广搜和深搜(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 1865很多时候,给定的图存在负权边,这时类似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,表示测试组数。然后每组第一行两 ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 3986一、什么是并查集 ... -
无前趋的顶点优先的拓扑排序方法(JAVA)
2012-10-28 20:20 1785无前趋的顶点优先的拓扑排序方法 该方法的每一步总是输 ... -
Kruskal算法和prim算法求最小生成树学习小结(JAVA)
2012-10-26 14:02 4963prim算法是用来实现图最小生成树的2种常用方法之一,P ... -
图的邻接表存储及遍历(JAVA)
2012-10-10 10:58 5355为图的每个顶点所发出的边建立一个单链表,用一顶点数组存储 ... -
弗洛伊德(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 2594算法描述:Kruskal(克鲁斯卡尔)算法需要对图的边进行访问 ...
相关推荐
拓扑排序拓扑排序拓扑排序拓扑排序拓扑排序拓扑排序拓扑排序拓扑排序拓扑排序
课题二 拓扑排序 2.1 问题的提出2.1 问题的提出 任务:编写函数实现图的拓扑排序。 程序所实现的功能: 建立对应的邻接表,对该图进行拓扑排序,并显示排序结果。 输入: 顶点数, 边数及各顶点信息(数据格式为整形...
任意给定一个有向图,设计一个算法,对它进行拓扑排序。拓扑排序算法思想:a.在有向图中任选一个没有前趋的顶点输出;b.从图中删除该顶点和所有以它为尾的弧;c.重复上述a、b,直到全部顶点都已输出,此时,顶点输出...
对于有向图进行拓扑排序,图使用邻接矩阵的存储结构。
C语言实现图的拓扑排序
拓扑排序
拓扑排序与关键路径.pptx拓扑排序与关键路径.pptx拓扑排序与关键路径.pptx拓扑排序与关键路径.pptx拓扑排序与关键路径.pptx拓扑排序与关键路径.pptx拓扑排序与关键路径.pptx拓扑排序与关键路径.pptx拓扑排序与关键...
拓扑排序源码,程序简单易懂,注释详细。希望对学习数据结构的朋友有所帮助。
拓扑排序关键路径算法C语言完整代码,vs2013下编译运行通过
C# 图 拓扑排序
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑...
拓扑排序
c语言拓扑排序算法
拓扑排序 拓扑排序
数据结构课设报告,包括完整源代码,用拓扑排序算法安排有先后制约关系的课程的教学计划。
C实现的拓扑排序,有详细注释,有问题的我们一起讨论
阅读了《数据结构(C语言)》的经典著作后...本次算法课程设计运用所学的图论的拓扑排序和关键路径,去实现工程中的花费时间和顺利进行问题。拓扑排序主要用于检验工程能否施工,关键路径主要用于看出工程施工时间消耗。
C语言实现拓扑排序 数据结构 C语言实现拓扑排序 数据结构
利用拓扑排序判断有向图是否存在一个简单又向回路,若存在,输出该回路
数据结构拓扑排序