We now present an algorithm to compute the length of the shortest cycle in a
graph. For directed graphs we want the shortest cycle of its underlying graph.
Thus DAGs may have a defined girth. Our algorithm will use a BFS approach from
each vertex of the graph. If a graph has a cycle (of length at least 3) then
it will be found by doing a BFS from one of the first 
vertices.
Whenever the BFS algorithm hits an already seen vertex then it has found a cycle
of length at most twice the current level (depth) of the search. The level of
the hit vertex (with respect to the BFS ``growing'' vertex) dictates whether
it is an odd or even length cycle. Note that an easy-to-implement DFS idea may
not work properly. For example, the DFS tree originating from vertex 0 of the
third graph of Example 21 finds only 6-cycles with the back-edges (even though
a 4-cycle exists using two of the back-edges). In the following java code we
decided to illustrate a slightly different programming style. Instead of calling
the BFS method directly (like we did above for our algorithm isAcyclic with
DFS) we modify the BFS code as needed. We also use the java BitSet class instead
of a boolean array (span) and use Vector and Enumeration classes instead of
our Queue class.
static public int girth(Graph Gin) // returns minimum girth >= 3
{
uGraph G = new uGraph(Gin); // compute undirected girth
int n=G.order();
int best = n+1; // girth n+1 if no cycles found
for (int i=0; i<n-2; i++) // look for a cycle from all but last two
{
BitSet span = new BitSet(n);
span.set(i);
int depth = 1; // do a BFS search keeping track of depth
Vector distList = new Vector();
distList.addElement( new Integer(i) );
while (depth*2 <= best && best > 3)
{
Vector nextList = new Vector();
for (Enumeration e = distList.elements(); e.hasMoreElements(); )
{
Vector nbrs = G.neighbors(((Integer) e.nextElement()).intValue());
for (int k=0; k < nbrs.size(); k++)
{
int u = ((Integer) nbrs.elementAt(k)).intValue();
if (!span.get(u))
{
span.set(u);
nextList.addElement(new Integer(u));
}
else // we have found some walk/cycle
{
// is there a cross edge at this level
//
if ( distList.contains(new Integer(u)) )
{
best = depth*2-1; break;
}
// else even length cycle (as an upper bound)
//
if ( nextList.contains(new Integer(u)) )
{
best = depth*2;
}
}
}
} // for vertices at current depth
distList = nextList; // next try set of vertices further away
depth++;
}
}
return best;
}
Note that we return 
if we do not find any cycles. Since
we are originating a BFS from all but two of the vertices we do not have to
separately worry about ensuring all components have been checked. The line
while (depth*2 <= best && best > 3)
indicates that we stop searching if the depth of the current BFS tree is greater
than an already found cycle. We also break out of a grow loop above if we find
a small cycle (a cross edge on the current level).