Girth of graph

问题描述

    在前面的一篇文章中我们讲述过怎么去检测一个图形中间是否有环。对于很多图来说，它们确实存在环，而且可能存在的环长度也各不相同。这里，就引入了一个概念，叫做girth。对于一个不存在环的图来说，它的girth为无穷大，而对于一个存在环的图来说，它的girth为最小的环长度。

    我们以下面几个图为例：

    这个图正好形成了一个环，所以它的girth值就是环的长度，为6。而下图中它的girth值则为无穷大：

 

    所以，这里的问题就是给定一个图，求出它的girth值。

 

问题分析

    从前面的问题描述可以看到，要求一个图的girth，需要考虑几个点。一个是看它是否存在有环，如果没有环，则girth值为无穷大。另外一个就是如果它确实存在有环，就要求每个环的长度，然后取得最小环的长度。

    对于第一个部分来说，问题还好说，前面的文章里已经阐述过如果处理的办法了。通过一个标记数组，每次访问一个节点所关联的所有节点时，如果碰到一个以前曾经访问过的节点，除去那个按照遍历方法到达当前节点的前置节点，那么说明存在有一个环。

 

寻找回路

    现在对于第二个问题，就是前面的方法找到了存在回路，该如何把这个回路的所有元素以及它的长度给找出来呢？结合前面判断图中间存在环问题的解法，我们来这么考虑。

    首先，判断图中间是否存在环，是通过一种遍历图的方法。在不管是通过dfs还是bfs遍历的时候。每个节点对应数组boolean[] marked中的一个。当节点被访问过，则对应位置被设置为true。这样后面再次遍历到的时候，如果发现这个位置已经被设置为true，这说明了什么呢？前面的遍历都是基于某一个单点来开始的，所以当我们将某个节点设置为true的时候，表示从一个给定的单点到这个节点是连通的。而第二次碰到这个原来被访问的节点时候呢？说明从第二次碰到这个节点的点到源节点也是连通的。这不就至少说明了，从源节点，到这个两次被碰到的节点以及第二次碰到这个节点前的这个点构成了一个环吗？以下图为例：

 

     假设我们第一次访问到目的节点t的时候，是通过节点s1，因为这个时候是以s为源节点开始遍历的。不管怎么说，肯定可以确定的就是节点s到s1到t是连通的。当我们通过第二次访问到节点t时，通过的是节点sk，如下图：

    基于前面同样的道理，sk可以连接到t，s也肯定可以连接到sk。这个时候，从s到s1到t再到sk，加上s到sk的这一段，不就正好构成了一个回路了么？

 

比对所有环路

    现在，按照这种思路确实可以找到回路。我们从一个单独的点出发，在图整个是连通的情况下，这一个点就完全遍历了整个图。按照前面的方法找到的回路，是不是就有最佳的呢？我们来看一个如下的具体图：

 

    假定我们从节点1开始作为源节点，它确实可以遍历所有节点。比如说当我们遍历到节点10的时候，我们会发现它被从6过来的节点访问过。另外，它也被从7过来的节点访问过。如果按照前面的思路来说，6和源节点1是连通的，7和1也是连通的。那么1到6,加上6到10,10到7,再加上7到1,这就构成了一个环。这个环结构如下：{1, 2, 6, 10, 7, 4, 3, 1} 。可是从直观的角度我们可以看到，这里最小的那个环应该是{6, 10, 7}这个。这说明了什么呢？我们前面检测环的这个过程，只是保证找到所有包含源节点在内的环，并不包含这些个不包含源节点的环。所以，光通过遍历一个节点来比对得出的环只是整个图中间存在环的一部分。按照原来的思路会遗漏一部分。所以，如果要找到所有的环进行比对的话，我们必须要通过所有的节点来做一遍前面的环检测，然后将最小的那个环返回回来。

 

实现

    有了前面这么些讨论，现在可以细化实现的代码了。我们这里一个个考虑过来。

1. 首先这里要通过所有的节点进行遍历，来查找环。那么，用哪种遍历方式呢？

    这里我们采用广度优先遍历的方法。

2. 如何判断节点是否被访问过？

    用一个boolean[] marked节点，长度和节点数一样，访问一次后对应的节点设置为true.

3. 如何保存遍历过的节点呢？

    用一个edgeTo[]节点，比如说通过节点u到节点v的时候，就将edgeTo[v] = u。这样我们根据一个节点的edgeTo[]节点就可以找到它前面的一个节点。这样一路倒推可以找到源节点。

4. 如何保存最小的环以及环所包含的节点呢？

    我们可以考虑用一个数字int来表示环的长度，并用一个集合，比如LinkedList或者ArrayList来保存这个环中间所有的节点。

    有了前面这些讨论，我们通过一个节点遍历得到通过该节点的最小环代码如下：

private void bfs(Graph g, int s) {
        Queue<Integer> q = new LinkedList<Integer>();
        for(int v = 0; v < g.v(); v++) distTo[v] = INFINITY;
        distTo[s] = 0;
        marked[s] = true;
        q.add(s);
        while(!q.isEmpty()) {
            int v = q.remove();
            for(int w : g.adj(v)) {
                if(!marked[w]) {
                    edgeTo[w] = v;
                    distTo[w] = distTo[v] + 1;
                    marked[w] = true;
                    q.enqueue(w);
                } else if(edgeTo[w] != v) {
                    updateGirth(w, v);
                }
            }
        }
    }

    这是在广度优先遍历算法的基础上做了一些修改。distTo[]数组保存的是从源节点到当前节点的距离，这样计算环长度的时候就更简单了，只要distTo[u] + distTo[v] + 1就是了。代码里关键的部分是updateGirth()方法。它的实现如下：

private void updateGirth(int w, int v) {
        if(distTo[w] + distTo[v] + 1 < girthSize) {
            girthSize = distTo[w] + distTo[v] + 1;
            girthPath.clear();
            for(Integer i : pathTo(w)) {
                girthPath.add(i);
            }
            for(int x = v; distTo[x] != 0; x = edgeTo[x]) {
                girthPath.add(x);
            }
        }
    }

     girthSize是表示环长度的值。最开始设置为最大整数值。所以前面要比较这个环的长度和girthSize，如果比这个girthSize小才有意义。这里用了两个循环，第一个部分是记录了从源节点到w节点的这一段路径。第二部分因为是要从v倒退到源节点，所以不用去遍历的取pathTo()方法里的元素。而pathTo()方法的实现如下：

public Iterable<Integer> pathTo(int v) {
        if(!hasPathTo(v)) return null;
        Stack<Integer> path = new Stack<Integer>();
        int x;
        for(x = v; distTo[x] != 0; x = edgeTo[x])
            path.push(x);
        return path;
    }

   详细的代码里还封装了包含当前源节点在内的最短环路径和路径长度。详细的代码实现可以见附件。

    附件里的代码实现了一个从某个节点开始去遍历得到的最小环。实际上，因为前面要得到整体的最小，所以还需要一个循环，构造出BreadthFirstPaths对象，然后取得其中最小的。这部分就没有详细写出来了，因为很简单，这里只是写一个大概：

public get minPath(Graph g) {
    int minSize = Integer.MAX_VALUE;
    for(int i : g.v()) {
        bfp = new BreadthFirstPaths(g, i); 
        if(bfp.getGirthSize() < minSize) {
            minSize = bfp.getGirthSize();
            minPath = bfp.getGirthPath();
        }
    }
    return minPath;
}

 

总结

     Girth这个词本身的意思是指一个东西的围长，相当于一个人的腰围或者一个桶的周长。只是结合它在图论里的定义，更多的像是木桶原理里指的那个短板。所以一时还不知道该用什么词来描述它好。这个问题相当于在找一个图中间存在环的问题基础上更进一步。找一个路径长度最小的环。我们这里通过遍历每个节点查找通过该节点的环，然后从中间筛选出最小的那个。实际上，在通过中间的一个或者若干个节点，保证可以覆盖整个图的时候，我们就可以得到一些中间节点访问过的信息，如果能够充分利用好这些信息，也许可以不用去通过所有节点来作遍历。不过目前只是一个想法，不知道是否可行。以后可以试试。

 

参考材料

Algorithms

https://github.com/jaspervdj/Genus/blob/master/src/genus/FindGirth.java

http://stackoverflow.com/questions/12890106/find-the-girth-of-a-graph

http://webcourse.cs.technion.ac.il/234247/Winter2003-2004/ho/WCFiles/Girth.pdf