文章目录有向图网络链接定义有向图是一副具有方向性的图是由一组顶点和一组有方向的边组成的每条方向的边都连着一对有序的顶点。相关术语一副有向图中两个顶点v和w可能存在以下四种关系有向图API设计代码实现1.------Digraph:拓扑排序拓扑排序定义给定一副有向图将所有的顶点排序使得所有的有向边均从排在前面的元素指向排在后面的元素此时就可以明确的表示出每个顶点的优先级。检测有向图中的环检测有向环的API设计检测有向环实现代码实现2. ----DirectedCycle顶点排序实现代码实现3. ------DepthFirstOrder拓扑排序实现API设计代码实现4. ------TopoLogical测试:有向图网络链接在实际生活中很多应用相关的图都是有方向性的最直观的就是网络可以从A页面通过链接跳转到B页面那么a和b连接的方向是a-b,但不能说是b-a,此时我们就需要使用有向图来解决这一类问题它和我们之前学习的无向图最大的区别就在于连接是具有方向的在代码的处理上也会有很大的不同。定义有向图是一副具有方向性的图是由一组顶点和一组有方向的边组成的每条方向的边都连着一对有序的顶点。相关术语出度由某个顶点指出的边的个数称为该顶点的出度。入度指向某个顶点的边的个数称为该顶点的入度。有向路径由一系列顶点组成对于其中的每个顶点都存在一条有向边从它指向序列中的下一个顶点。有向环一条至少含有一条边且起点和终点相同的有向路径。一副有向图中两个顶点v和w可能存在以下四种关系没有边相连存在从v到w的边v—w;存在从w到v的边w—v;既存在w到v的边也存在v到w的边即双向连接理解有向图是一件比较简单的但如果要通过眼睛看出复杂有向图中的路径就不是那么容易了。有向图API设计在api中设计了一个反向图其因为有向图的实现中用adj方法获取出来的是由当前顶点v指向的其他顶点如果能得到其反向图就可以很容易得到指向v的其他顶点。代码实现1.------Digraph:packagegraph;importjava.util.Queue;importjava.util.concurrent.ConcurrentLinkedDeque;publicclassDigraph{//顶点数目privatefinalintV;//边的数目privateintE;//邻接表privateQueueInteger[]adj;publicDigraph(intV){//初始化顶点数量this.VV;//初始化边的数量this.E0;//初始化邻接表this.adjnewQueue[V];for(inti0;iadj.length;i){adj[i]newConcurrentLinkedDeque();}}//获取顶点数目publicintV(){returnV;}//获取边的数目publicintE(){returnE;}//向有向图中添加一条边 v-wpublicvoidaddEdge(intv,intw){//只需要让顶点w出现在顶点v的邻接表中因为边是有方向的最终顶点v的邻接表中存储的相邻顶点的含义是 v-其他顶点adj[v].offer(w);E;}//获取由v指出的边所连接的所有顶点publicQueueIntegeradj(intv){returnadj[v];}//该图的反向图privateDigraphreverse(){//创建有向图对象DigraphrnewDigraph(V);for(intv0;vV;v){//获取由该顶点v指出的所有边for(Integerw:adj[v]){//原图中表示的是由顶点v-w的边r.addEdge(w,v);//w-v}}returnr;}}拓扑排序在现实生活中我们经常会同一时间接到很多任务去完成但是这些任务的完成是有先后次序的。以我们学习java学科为例我们需要学习很多知识但是这些知识在学习的过程中是需要按照先后次序来完成的。从java基础到jsp/servlet到ssm到springboot等是个循序渐进且有依赖的过程。在学习jsp前要首先掌握java基础和html基础学习ssm框架前要掌握jsp/servlet之类才行。为了简化问题我们使用整数为顶点编号的标准模型来表示这个案例此时如果某个同学要学习这些课程就需要指定出一个学习的方案我们只需要对图中的顶点进行排序让它转换为一个线性序列就可以解决问题这时就需要用到一种叫拓扑排序的算法。拓扑排序定义给定一副有向图将所有的顶点排序使得所有的有向边均从排在前面的元素指向排在后面的元素此时就可以明确的表示出每个顶点的优先级。检测有向图中的环如果学习x课程前必须先学习y课程学习y课程前必须先学习z课程学习z课程前必须先学习x课程那么一定是有问题了我们就没有办法学习了因为这三个条件没有办法同时满足。其实这三门课程x、y、z的条件组成了一个环因此如果我们要使用拓扑排序解决优先级问题首先得保证图中没有环的存在。检测有向环的API设计检测有向环实现在API中添加了onStack[] 布尔数组索引为图的顶点当我们深度搜索时在如果当前顶点正在搜索则把对应的onStack数组中的值改为true标识进栈如果当前顶点搜索完毕则把对应的onStack数组中的值改为false标识出栈如果即将要搜索某个顶点但该顶点已经在栈中则图中有环代码实现2. ----DirectedCyclepackagegraph;publicclassDirectedCycle{//索引代表顶点值表示当前顶点是否已经被搜索privateboolean[]marked;//记录图中是否有环privatebooleanhasCycle;//索引代表顶点使用栈的思想记录当前顶点有没有已经处于正在搜索的有向路径上privateboolean[]onStack;//创建一个检测环对象检测图G中是否有环publicDirectedCycle(DigraphG){//初始化marked数组this.markednewboolean[G.V()];//初始化hasCyclethis.hasCyclefalse;//初始化onStack数组this.onStacknewboolean[G.V()];//找到图中每一个顶点让每一个顶点作为入口调用一次dfs进行搜索for(intv0;vG.V();v){//判断如果当前顶点还没有搜索过则调用dfs进行搜索if(!marked[v]){dfs(G,v);}}}//基于深度优先搜索检测图G中是否有环privatevoiddfs(DigraphG,intv){//把顶点v表示为已搜索marked[v]true;//把当前顶点进栈onStack[v]true;//进行深度搜索for(Integerw:G.adj(v)){//判断如果当前顶点w没有被搜索过则继续递归调用dfs方法完成深度优先搜索if(!marked[w]){dfs(G,w);}//判断当前顶点w是否已经在栈中如果已经在栈中证明当前顶点之前处于正在搜索的状态那么现在又要搜索一次证明检测到环了if(onStack[w]){hasCycletrue;return;}}//把当前顶点出栈onStack[v]false;}//判断当前有向图G中是否有环publicbooleanhasCycle(){returnhasCycle;}}顶点排序实现在API的设计中我们添加了一个栈reversePost用来存储顶点当我们深度搜索图时每搜索完毕一个顶点把该顶点放入到reversePost中这样就可以实现顶点排序。代码实现3. ------DepthFirstOrderpackagegraph;importjava.util.Stack;publicclassDepthFirstOrder{//索引代表顶点值表示当前顶点是否已经被搜索privateboolean[]marked;//使用栈存储顶点序列privateStackIntegerreversePost;//创建一个检测环对象检测图G中是否有环publicDepthFirstOrder(DigraphG){//初始化marked数组this.markednewboolean[G.V()];//初始化reversePost栈this.reversePostnewStackInteger();//遍历图中的每一个顶点让每个顶点作为入口完成一次深度优先搜索for(intv0;vG.V();v){if(!marked[v]){dfs(G,v);}}}//基于深度优先搜索把顶点排序privatevoiddfs(DigraphG,intv){//标记当前v已经被搜索marked[v]true;//通过循环深度搜索顶点vfor(Integerw:G.adj(v)){//如果当前顶点w没有搜索则递归调用dfs进行搜索if(!marked[w]){dfs(G,w);}}//让顶点v进栈reversePost.push(v);}//获取顶点线性序列publicStackIntegerreversePost(){returnreversePost;}}拓扑排序实现前面已经实现了环的检测以及顶点排序那么拓扑排序就很简单了基于一幅图先检测有没有环如果没有环则调用顶点排序即可。API设计代码实现4. ------TopoLogicalimportjava.util.Stack;publicclassTopoLogical{//顶点的拓扑排序privateStackIntegerorder;//构造拓扑排序对象publicTopoLogical(DigraphG){//创建一个检测有向环的对象DirectedCyclecyclenewDirectedCycle(G);//判断G图中有没有环如果没有环则进行顶点排序创建一个顶点排序对象if(!cycle.hasCycle()){DepthFirstOrderdepthFirstOrdernewDepthFirstOrder(G);orderdepthFirstOrder.reversePost();}}//判断图G是否有环privatebooleanisCycle(){returnordernull;}//获取拓扑排序的所有顶点publicStackIntegerorder(){returnorder;}}测试:packagegraph;importjava.util.Stack;publicclassTopoLogicalTest{publicstaticvoidmain(String[]args){//准备有向图DigraphdigraphnewDigraph(6);digraph.addEdge(0,2);digraph.addEdge(0,3);digraph.addEdge(2,4);digraph.addEdge(3,4);digraph.addEdge(4,5);digraph.addEdge(1,3);//通过TopoLogical对象堆有向图中的顶点进行排序TopoLogicaltopoLogicalnewTopoLogical(digraph);//获取顶点的线性序列进行打印StackIntegerordertopoLogical.order();StringBuildersbnewStringBuilder();while(!order.empty()){sb.append(order.pop()-);}Stringstrsb.toString();strstr.substring(0,str.length()-2);System.out.println(str);}}