- 浏览: 580670 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
当每个任务有前后置关系时,需要找到一种满足前后置关系的路线,将任务完成。
如果将每个任务看成一个节点,任务之间的前后置关系表示为有向图时,这种路线顺序叫做为图进行拓扑排序。也叫关键路径分析。
比如有很多任务T1,T2,....
这些任务又是相互关联的,比如Tj完成前必须要求Ti已完成,这样T1,T2....序列关于这样的先决条件构成一个图,其中如果Ti必须要先于Tj完成,那么<Ti,Tj>就是该图中的一条路径,路径长度为1的就是一条边。拓扑排序就是把这些任务按照完成的先后顺序排列出来。显然,这样的顺序可能不是唯一的,比如Tk,Tl如果没有在一条路径上,那么他们之间的顺序是任意的。
当从某顶点v出发的DFS搜索完成时,v的所有后继必定均已被访问过(想像它们均已被删除),此时的v相当于是无后继的顶点,因此在DFS算法返回之前输出顶点v即可得到 DAG的逆拓扑序列。
其中第一个输出的顶点必是无后继(出度为0)的顶点,它应是拓扑序列的最后一个顶点。若希望得到的不是逆拓扑序列,同样可增加T来保存输出的顶点。假设T是栈。
利用DFS求拓扑序列的抽象算法可描述为:
void DFSTopSort(G,i,T){//i是搜索的出发点,T是栈
int j;
visited[i]=TRUE; //访问i
for(所有i的邻接点j)//即<i,j>∈E(G)
if(!visited[j])
DFSTopSort(G,j,T);
Push(&T,i); //从i出发的搜索已完成,输出i
}
看看下图的一个拓扑序列:
[c1, c4, c0, c2, c3, c5, c6, c7, c8]
下载源文件:
如果将每个任务看成一个节点,任务之间的前后置关系表示为有向图时,这种路线顺序叫做为图进行拓扑排序。也叫关键路径分析。
比如有很多任务T1,T2,....
这些任务又是相互关联的,比如Tj完成前必须要求Ti已完成,这样T1,T2....序列关于这样的先决条件构成一个图,其中如果Ti必须要先于Tj完成,那么<Ti,Tj>就是该图中的一条路径,路径长度为1的就是一条边。拓扑排序就是把这些任务按照完成的先后顺序排列出来。显然,这样的顺序可能不是唯一的,比如Tk,Tl如果没有在一条路径上,那么他们之间的顺序是任意的。
当从某顶点v出发的DFS搜索完成时,v的所有后继必定均已被访问过(想像它们均已被删除),此时的v相当于是无后继的顶点,因此在DFS算法返回之前输出顶点v即可得到 DAG的逆拓扑序列。
其中第一个输出的顶点必是无后继(出度为0)的顶点,它应是拓扑序列的最后一个顶点。若希望得到的不是逆拓扑序列,同样可增加T来保存输出的顶点。假设T是栈。
利用DFS求拓扑序列的抽象算法可描述为:
void DFSTopSort(G,i,T){//i是搜索的出发点,T是栈
int j;
visited[i]=TRUE; //访问i
for(所有i的邻接点j)//即<i,j>∈E(G)
if(!visited[j])
DFSTopSort(G,j,T);
Push(&T,i); //从i出发的搜索已完成,输出i
}
看看下图的一个拓扑序列:
[c1, c4, c0, c2, c3, c5, c6, c7, c8]
public enum VertexState { UNVISITED,VISITED,PASSED;//未访问,已访问,已经过 } import java.util.Set; import java.util.List; import java.util.HashSet; import java.util.ArrayList; import java.util.Collections; //顶点类 class Vertex { private String label; private VertexState state;//顶点状态 public Vertex(String lab) { label = lab; state = VertexState.UNVISITED; } public VertexState getState(){ return state; } public void setState(VertexState state){ this.state=state; } public String toString(){ return label; } } //有向图的邻接矩阵实现 class Graph { private final int MAX_VERTS = 30; private Vertex vertexList[]; // 存放顶点的数组 private int adjMat[][]; // 邻接矩阵 private int nVerts; // 当前的顶点数 public Graph() { vertexList = new Vertex[MAX_VERTS]; adjMat = new int[MAX_VERTS][MAX_VERTS]; nVerts = 0; for(int y=0; y<MAX_VERTS; y++) for(int x=0; x<MAX_VERTS; x++) adjMat[x][y] = 0; } public void addVertex(Vertex v)//在图中添加一个顶点 { vertexList[nVerts++] = v; } //在图中增加一条边,从start到end public void addEdge(int start, int end) { adjMat[start][end] = 1; } /** * 返回v顶点所关联的邻结点 * @param v * @return */ private Set<Vertex> getNeighbors(Vertex v){ Set<Vertex> vSet = new HashSet<Vertex>(); int index=getIndex(v); if(index==-1) return null; for(int i=0;i<nVerts;i++) if(adjMat[index][i]==1) vSet.add(vertexList[i]); return vSet; } //返回顶点在vertexList数组中的索引 private int getIndex(Vertex v){ for(int i=0;i<nVerts;i++) if(vertexList[i]==v) return i; return -1; } /** * 全部节点设为未访问 */ private void allUnVisted(){ Vertex v=null; int len = nVerts; for(int i = 0; i < len ; i++){ v = vertexList[i]; if(v.getState() != VertexState.UNVISITED){ v.setState(VertexState.UNVISITED); } } } private boolean containsVertex(Vertex v){ int index=getIndex(v); if(index!=-1) return true; else return false; } private VertexState getState(Vertex v){ return v.getState(); } private VertexState setState(Vertex v, VertexState state) { VertexState preState = v.getState(); v.setState(state); return preState; } /** * 深度优先遍历一个顶点 * @param * @param graph * @param v * @param checkCycle * @return */ public List<Vertex> dfs(Vertex v,boolean checkCycle){ allUnVisted(); List<Vertex> vList = new ArrayList<Vertex>(); dfsHandler(v,checkCycle,vList); return vList; } private void dfsHandler(Vertex v,boolean checkCycle,List<Vertex> vList){ Set<Vertex> neighbors = null; if(!containsVertex(v)){ throw new IllegalStateException("不存在该顶点"); } setState(v, VertexState.PASSED); neighbors = getNeighbors(v); VertexState state = null; for(Vertex neighbor : neighbors){ state = getState(neighbor); if(state == VertexState.UNVISITED){//未遍历, // System.out.println(neighbor+","); dfsHandler(neighbor, checkCycle, vList); }else if(state == VertexState.PASSED && checkCycle){// throw new IllegalStateException("存在一个环"); } } setState(v, VertexState.VISITED);//访问结束设为已访问 vList.add(v); // System.out.println("++"+v); } /** * 图的拓扑排序 */ public List<Vertex> topo(){ List<Vertex> vList = new ArrayList<Vertex>(); allUnVisted(); for(int i=0;i<nVerts;i++){ if(getState(vertexList[i]) == VertexState.UNVISITED){ try{ dfsHandler(vertexList[i], true, vList); }catch (IllegalStateException e) { throw new IllegalStateException("图有一个环"); } } } Collections.reverse(vList); return vList; } } public class DFSApp { public static void main(String[] args) { Graph theGraph = new Graph(); Vertex v1=new Vertex("c0"); Vertex v2=new Vertex("c1"); Vertex v3=new Vertex("c2"); Vertex v4=new Vertex("c3"); Vertex v5=new Vertex("c4"); Vertex v6=new Vertex("c5"); Vertex v7=new Vertex("c6"); Vertex v8=new Vertex("c7"); Vertex v9=new Vertex("c8"); theGraph.addVertex(v1); // 0 theGraph.addVertex(v2); // 1 theGraph.addVertex(v3); // 2 theGraph.addVertex(v4); // 3 theGraph.addVertex(v5); // 4 theGraph.addVertex(v6); // 5 theGraph.addVertex(v7); // 6 theGraph.addVertex(v8); // 7 theGraph.addVertex(v9); // 8 theGraph.addEdge(0, 6); // c0->c6 theGraph.addEdge(0, 2); // c0->c2 theGraph.addEdge(3, 5); // c3->c5 theGraph.addEdge(3, 8); // c3->c8 theGraph.addEdge(1, 2); // c1->c2 theGraph.addEdge(1, 4); // c1->c4 theGraph.addEdge(2, 3); // c2->c3 theGraph.addEdge(6, 7); // c6->c7 theGraph.addEdge(7, 8); // c7->c8 theGraph.addEdge(4, 3); // c4->c3 theGraph.addEdge(4, 5); // c4->c5 //theGraph.addEdge(3, 1); // c3->c1 System.out.print("Visits: "); List<Vertex> vl=theGraph.topo(); // List<Vertex> vl=theGraph.dfs(v1,false); System.out.println(vl); } }
下载源文件:
发表评论
-
图的深搜+回溯练习题:POJ2197
2013-01-18 15:53 1509POJ 2197题意: 给定n个城市及其之间的距离,以及距 ... -
图的练习题(有解答)
2012-12-27 22:23 26071. 填空题 ⑴ 设无向图G ... -
邻接表实现图的广搜和深搜(java模板)
2012-12-11 17:04 2394//邻接表实现图的广搜和深搜(java模板) impor ... -
邻接矩阵实现图的广搜和深搜(java模板)
2012-12-10 20:37 1826经常要用到,放到这里备用!! //邻接矩阵实现图的广搜和深搜 ... -
如何求无向图的最小环
2012-11-13 19:02 2737POJ1734 题意:给定一个N个点的无向图,求一个最小环(各 ... -
深度优先搜索输出有向图中的所有环(JAVA)
2012-11-06 14:22 9540如图:求出有向图的所有环。 import java.uti ... -
三种算法(Floyd、Dijkstra、SPFA)求单源点最短路径。
2012-11-05 13:15 1767题(HDU2544): 在每年的校赛里,所有进入决赛 ... -
Dijkstra算法解HDU1874
2012-11-05 10:15 1293Dijkstra算法是用来解 ... -
SPFA算法求单源最短路径
2012-11-04 23:00 1857很多时候,给定的图存在负权边,这时类似Dijkstra等算法 ... -
图解Bellman-Ford算法
2012-11-03 19:39 5805Bellman-Ford算法: ... -
Bellman-Ford算法教学PPT
2012-11-03 12:06 1388Dijkstra算法是处理单源最短路径的有效算法,但它 ... -
昆虫的同性恋
2012-11-01 19:21 1342题目大意: 输入一个数t,表示测试组数。然后每组第一行两 ... -
拓扑排序入门练习
2012-11-01 16:51 1526拓扑排序简单来说 ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 3972一、什么是并查集 ... -
无前趋的顶点优先的拓扑排序方法(JAVA)
2012-10-28 20:20 1770无前趋的顶点优先的拓扑排序方法 该方法的每一步总是输 ... -
Kruskal算法和prim算法求最小生成树学习小结(JAVA)
2012-10-26 14:02 4957prim算法是用来实现图最小生成树的2种常用方法之一,P ... -
图的邻接表存储及遍历(JAVA)
2012-10-10 10:58 5342为图的每个顶点所发出的边建立一个单链表,用一顶点数组存储 ... -
弗洛伊德(Floyd)算法求任意两点间的最短路径
2012-10-01 07:46 6210Floyd-Warshall算法(Floyd-Warsha ... -
单源最短路径( Dijkstra算法)JAVA实现
2012-09-14 14:30 9000单源最短路径问题,即在图中求出给定顶点到其它任一顶 ... -
最小生成树:Kruskal(克鲁斯卡尔)算法实现(java)
2012-09-01 20:50 2579算法描述:Kruskal(克鲁斯卡尔)算法需要对图的边进行访问 ...
相关推荐
图的几种常用算法(广度/深度优先搜索,最小生成树,弗洛伊德,拓扑排序....邻接矩阵),java实现。 注释清晰,代码简单易懂。
用Java描述的图,以邻接表存储,包含常用算法
拓扑排序-邻接矩阵存储-深度优先搜索算法 算法设计常用思想 [分治算法之合并排序] [动态规划法之装配站问题] Java 常见问题 [分布式锁-分段锁思想] Java NIO Android 常见问题 [JNI双进程保活] [Activity和Fragment...
功能 图的广度优先遍历,深度优先遍历 拓扑排序 深度优先生成森林 关键路径
(2)图的深度优先和广度优先遍历。 (3)无向图的连通性和最小生成树 (4)拓扑排序 (5)关键路径 (6)单源最短路径 5.散列表(哈希表) (1)散列表的概念 (2)散列表解决散列冲突的方法(开放地址法、链地址...
图论算法9.1 若干定义9.2 拓扑排序9.3 最短路径算法9.3.1 无权最短路径9.3.2 Dijkstra算法9.3.3 具有负边值的图9.3.4 无圈图9.3.5 所有点对最短路径9.3.6 最短路径的例子9.4 网络流问题9.5 最小生成树9.5.1 Prim算法...
连接的组件未加权的有向图(隐式边) 深度优先搜索广度优先搜索强连接组件拓扑排序循环检测加权无向图(显式边) 最小生成树普里姆克鲁斯卡尔加权有向图(显式边) 最短路径Dijkstra(无负权重) Bellman-Ford...
java编写的图的各种操作,包括建立图,深度优先遍历,广度优先遍历,最短路径,拓扑排序等,用于学习数据结构,可以运行
图论算法9.1 若干定义9.2 拓扑排序9.3 最短路径算法9.3.1 无权最短路径9.3.2 Dijkstra算法9.3.3 具有负边值的图9.3.4 无圈图9.3.5 所有点对最短路径9.3.6 最短路径的例子9.4 网络流问题9.5 最小生成树9.5.1 Prim算法...
深度优先搜索 最短的路径 Dijkstra的算法 贝尔曼福特 弗洛伊德·沃歇尔 约翰逊算法 最小生成树 克鲁斯卡尔算法 普里姆算法 网络流量 卡格算法 推送重新贴标签 埃德蒙兹·卡普 福特福克森 塔里安算法 拓扑排序 紧密...
有向无环图 双向匹配 铰接点,桥梁 欧拉之旅/路径 哈密顿环 稳定的婚姻问题 中国邮递员问题 2满意度 流算法 最大流量 最小切割 最小成本最大流量 最大二分匹配 顶点覆盖 动态编程 杆切割 最大总和(1D,2D) ...
图论算法9.1 若干定义9.2 拓扑排序9.3 最短路径算法9.3.1 无权最短路径9.3.2 Dijkstra算法9.3.3 具有负边值的图9.3.4 无圈图9.3.5 所有点对最短路径9.3.6 最短路径的例子9.4 网络流问题9.5 最小生成树9.5.1 Prim算法...
9.6 深度优先搜索的应用 9.6.1 无向图 9.6.2 双连通性 9.6.3 欧拉回路 9.6.4 有向图 9.6.5 查找强分支 9.7 NP完全性介绍 9.7.1 难与易 9.7.2 NP类 9.7.3 NP完全问题 小结 练习 参考文献 第10章 算法设计技巧 ...
0-1背包问题最长公共子序列最长递增子序列凸包广度优先搜索(BFS) 深度优先搜索(DFS) 弗洛伊德·沃歇尔/罗伊·弗洛伊德迪克斯特拉贝尔曼福特克鲁斯卡尔拓扑排序伪代码实现:1-6,8-25-@iuliagroza / 7-@...
9.3.4 无圈图 9.3.5 所有点对最短路径 9.3.6 最短路径的例子 9.4 网络流问题 9.5 最小生成树 9.5.1 prim算法 9.5.2 kruskal算法 9.6 深度优先搜索的应用 9.6.1 无向图 9.6.2 双连通性 9.6.3 ...
9.3.4 无圈图 9.3.5 所有点对最短路径 9.3.6 最短路径的例子 9.4 网络流问题 9.5 最小生成树 9.5.1 prim算法 9.5.2 kruskal算法 9.6 深度优先搜索的应用 9.6.1 无向图 9.6.2 双连通性 9.6.3 ...
9.5.2 Kruskal算法 9.6 深度优先搜索的应用 9.6.1 无向图 9.6.2 双连通性 9.6.3 欧拉回路 9.6.4 有向图 9.6.5 查找强分支 9.7 NP完全性介绍 9.7.1 难与易 9.7.2 NP类 9.7.3 NP完全问题 小结 ...
深度优先搜索, 广度优先搜索, 拓扑排序, Kosaraju-Sharir, 克鲁斯卡尔 总理, 迪基斯特拉, 贝尔曼-福特, 福特-福克森, LSD基数排序, MSD基数排序, 三路基数快速排序, 多路尝试, 三元搜索尝试, 克努斯-...