- 浏览: 604155 次
- 来自: ...
文章分类
最新评论
-
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 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 9625如图:求出有向图的所有环。 import java.uti ... -
三种算法(Floyd、Dijkstra、SPFA)求单源点最短路径。
2012-11-05 13:15 1864题(HDU2544): 在每年的校赛里,所有进入决赛 ... -
Dijkstra算法解HDU1874
2012-11-05 10:15 1363Dijkstra算法是用来解 ... -
SPFA算法求单源最短路径
2012-11-04 23:00 1942很多时候,给定的图存在负权边,这时类似Dijkstra等算法 ... -
图解Bellman-Ford算法
2012-11-03 19:39 5940Bellman-Ford算法: ... -
Bellman-Ford算法教学PPT
2012-11-03 12:06 1455Dijkstra算法是处理单源最短路径的有效算法,但它 ... -
昆虫的同性恋
2012-11-01 19:21 1398题目大意: 输入一个数t,表示测试组数。然后每组第一行两 ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 4070一、什么是并查集 ... -
无前趋的顶点优先的拓扑排序方法(JAVA)
2012-10-28 20:20 1882无前趋的顶点优先的拓扑排序方法 该方法的每一步总是输 ... -
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(克鲁斯卡尔)算法需要对图的边进行访问 ...
相关推荐
拓扑排序则是在有向无环图(DAG)中对节点进行排序,使得对于图中任何一条边(u, v),节点u都在节点v之前。这一排序在解决工程依赖、课程安排等问题时非常有用,Kahn算法和DFS算法都是实现拓扑排序的有效方法。 ...
这些问题包括约瑟夫环问题、最长回文子串、0/1背包问题、拓扑排序等。通过这些实例,读者可以深入理解算法的本质和实现方法,提高解决问题的能力。该部分还介绍了一些常见的算法优化技巧,如空间换时间、分治策略等...
这些包括排序(快速排序、归并排序、堆排序)、搜索(二分查找、深度优先搜索、广度优先搜索)、图论(最短路径、最小生成树、拓扑排序)等。理解这些算法的工作原理,并能快速应用到实际问题中,是解决问题的关键。...
(7)掌握拓扑排序算法和欧拉回路算法。 教学难点: (1)掌握完全二叉树的数组实现和链式表示法。 (2)掌握二叉树的先序、后序和中序遍历和层次遍历。 (3)掌握图的 DFS 和 BFS 遍历。 (4)掌握拓扑排序...
2. 图论算法:最短路径(Dijkstra、Floyd-Warshall)、最小生成树(Prim、Kruskal)、拓扑排序等。 3. 贪心算法:在每一步选择局部最优解,以期望得到全局最优解,如活动安排、区间调度问题。 4. 回溯法:用于解决...
除了基本数据结构,还有高级数据结构如堆(用于优先队列)、哈希表(提供快速的查找和插入操作)和图算法(如最短路径算法Dijkstra和拓扑排序)。这些数据结构和算法在实际编程中有着广泛的应用,如数据库索引、搜索...
14. **一笔画问题**:图形理论问题,需要找到一个闭合路径,使得图形仅被一笔画出,可以使用拓扑排序或欧拉路径。 15. **城市遍历问题**:可能是指旅行商问题(TSP),寻找访问所有城市的最短路径,属于NP完全问题...
5. **第五题**:这可能是一个涉及算法的题目,比如图论问题(如最短路径、拓扑排序)或动态规划。也可能与数据结构的高级主题相关,如树(二叉树、红黑树等)或哈希表的操作。 6. **第六题**:第六题可能与对象导向...
3. **图论**:包括最小生成树(Prim或Kruskal)、最短路径(Dijkstra或Floyd-Warshall)、拓扑排序和网络流等,这些都是解决复杂关系网络问题的工具。 4. **动态规划**:动态规划是一种用于求解具有重叠子问题和最...
3. **图论**:包括最短路径问题(Dijkstra算法、Floyd-Warshall算法)、最小生成树(Prim算法、Kruskal算法),以及拓扑排序等,这些都是解决实际网络问题的关键。 4. **动态规划**:背包问题、最长公共子序列、...
图算法包括最短路径查找(Dijkstra算法、Bellman-Ford算法)、拓扑排序等。 9. **排序算法**:如冒泡排序、选择排序、插入排序、快速排序、归并排序等,它们用于将一组元素按特定顺序排列。 10. **查找算法**:如...
7. **图算法**:包括最短路径问题(如Dijkstra算法和Floyd算法)、拓扑排序、最小生成树(Prim和Kruskal算法)等。 8. **数据结构**:算法离不开数据结构的支持,如链表、栈、队列、树、图、哈希表等,书中会介绍...
6. **图论**:包括图的遍历、最小生成树(Prim或Kruskal)、最短路径(Dijkstra或Floyd-Warshall)、拓扑排序、网络流等。这些在解决复杂关系问题时非常有用。 7. **数据结构**:如链表、栈、队列、哈希表、树...
算法是解决问题的核心,常见的有排序(如冒泡、快速、归并排序)、查找(如二分查找)、图论(如最短路径、拓扑排序)等。数据结构如栈、队列、链表、树(二叉树、平衡树)和哈希表等,是实现高效算法的基石。理解...
2. **图论**:图的概念广泛应用于ACM竞赛中,包括最小生成树(Prim算法或Kruskal算法)、最短路径(Dijkstra算法或Floyd-Warshall算法)以及拓扑排序等。 3. **动态规划(Dynamic Programming, DP)**:DP是一种...
2. **图论**:如最短路径问题(Dijkstra算法、Floyd-Warshall算法)、最小生成树(Prim算法、Kruskal算法)、拓扑排序等,这些都是处理复杂关系网络的关键。 3. **动态规划**:动态规划能有效地解决具有重叠子问题...
DFS可以用来检查图中是否存在环,以及用于网络的拓扑排序。 #### 3. DFS的实际运用 DFS在解决许多图论问题中都十分有用,例如迷宫求解、电路检测、以及各种路径寻找问题。通过实践DFS算法,参赛者能加深对图和树的...
2. **算法基础**:蓝桥杯竞赛中常见的算法包括排序(如冒泡排序、快速排序、归并排序)、查找(如线性查找、二分查找)、图论(如最短路径问题、拓扑排序)和动态规划等。掌握这些基础算法有助于高效解题。 3. **...
深度优先搜索是图遍历的基本算法之一,通常用于拓扑排序和检测环等问题。 5. 图中的路径 路径算法部分关注如何在图中找到两点间最短路径。涉及到了距离的计算、广度优先搜索(BFS)、Dijkstra算法以及负权边和有向...
在"aoapc-bac2nd-master"这个压缩包中,我们可以期待找到各种不同类型的算法实现,如排序算法(快速排序、归并排序、冒泡排序等)、查找算法(二分查找、哈希查找等)、图算法(最短路径、拓扑排序等)、树算法...