41.有向图的几个算法分析总结.doc

有向图的几个算法分析总结 简介 ? ? 前面讨论的很多文章里，都是针对无向图进行的分析。无向图的一个特性就是其中一旦两个节点a和b是相连的，这就意味着有路径从a到b，同时也有从b到a的。它具体对应的矩阵表达方式对应着一个对称矩阵。而这里重点是考察有向图。和无向图比起来，有向图更加多了一种出入度的概念。因为方向的有向性，很多以前在无向图里看起来比较简单的问题在这里会变得更加有意思。 ? 　　一个常用的有向图会如下图这样： 　　因为每个节点和节点之间对应着一定的方向关系，所以这里用一个箭头来表示从一个节点到另外一个节点的有向关系。在具体保存有向图定义的数据结构里，我们还是可以采用一样的链表组结构。只是因为是有向图，所以加入元素的时候不用考虑对称节点的问题。在实现上其实也更加简化。 　　下面是一个关于有向图的简单定义实现： ? Java代码?? public?class?Digraph?{?? ????private?final?int?vertices;?? ????private?int?edges;?? ????private?ListLinkedListInteger?adj;?? ?? ????public?Digraph(int?vertices)?{?? ????????if(vertices??0)?throw?new?IllegalArgumentException(?? ????????????????Number?of?vertices?in?a?Digraph?must?be?nonnegative);?? ????????this.vertices?=?vertices;?? ????????this.edges?=?0;?? ????????adj?=?new?ArrayListLinkedListInteger();?? ????????for(int?i?=?0;?i??vertices;?i++)?{?? ????????????adj.add(new?LinkedListInteger());?? ????????}?? ????}?? ?? ????public?void?addEdge(int?v,?int?w)?{?? ????????if(v??0?||?v?=?vertices)??? ????????????throw?new?IndexOutOfBoundsException(?? ????????????????????vertex??+?v?+??not?in?bound.);?? ????????if(w??0?||?w?=?vertices)??? ????????????throw?new?IndexOutOfBoundsException(?? ????????????????????vertex??+?w?+??not?in?bound.);?? ????????adj.get(v).add(w);?? ????????edges++;?? ????}?? }?? 　这部分代码很简单，无需解释。 　有了这部分定义之后，我们再来考虑后面的几个典型的问题。 ? 环的存在和检测 　和前面无向图的过程有点类似，我们要检测一个图中间是否存在环，肯定也需要通过某种遍历的方式，然后对访问过的元素做标记。如果再次碰到前面访问过的元素，则说明可能存在环。这里，如何来检测环和如果这个环存在的话，我们要返回这个环。在无向图的时候，这个方法确实是很简单可行，我们可以通过广度或者深度优先遍历来解决。在有向图的情况下，前面的办法照搬过来就一定可行吗？ 　我们来看下面的一个示例： ? ? ? 在该图中，假设我们从节点１开始去遍历，当按照前面的仅仅是修改marked[] 数组的办法，可能先通过节点２到达节点６，于是就设定了marked[6] = true。如下图： ? 　　当再次遍历到节点６的时候，则如下图所示： 　　这个时候，如果去看marked[6]的话，它已经被标记为true了。可是，如果按照这个条件，我们就确定这种情况存在环，肯定不行。因为现在的这个情况实际上并不是一个环，它仅仅是访问到了一个前面访问过的节点。在这种情况下，要判断一个环的存在，和取得环所在元素的问题根源在于哪里呢？ 　　在前面的示例中，我们从节点１到２，然后到６，整个的过程里，这几个点被遍历了，但是光到这一步还没有构成一个环。按照深度优先遍历的过程，这个时候相当于２和６已经遍历完了，要去遍历节点１的另外一个边。实际上，这个时候就算从另外一个边可以遍历到前面的节点２或者６，因为这个时候能访问到２和６的是另外一组有向边了，它们和前面经过的那些有向边是不一定构成环的。 　　另外，从环的构成来说。如果我们按照深度优先的顺序访问到了一