Breadth-First Search and Girth

Date: 11/13/2000 at 17:17:11
From: Donald
Subject: Graph Theory

Hi there,

I'm currently taking a graph theory course and was hoping you could 
help me out on a question that I'm stuck on:

Explain how to use a Breadth-First Search to compute the girth (length 
of shortest cycle) of a graph.

I've thought of applying Kruskal's Algorithm to get a spanning tree, 
and then using a BFS, but I run into problems.

How can I efficiently solve this problem using a BFS?

Thanks,
Donald

Date: 11/13/2000 at 17:35:49
From: Doctor Schwa
Subject: Re: Graph Theory

I'm not sure about "efficiently," but the simplest way to do it would 
be to make the adjacency matrix A of the graph and see if there are 
any nonzero numbers on the diagonal. Then square the matrix (find all 
the two-step paths) and see if there are any nonzero numbers on the 
diagonal. Then cube, etc., until you find a nonzero number on the 
diagonal. You know you have to go at most to the nth power, where n is 
the number of vertices of the graph, because any cycle can have at 
most n edges before returning to the starting point.

- Doctor Schwa, The Math Forum
  http://mathforum.org/dr.math/   

Date: 11/13/2000 at 17:57:40
From: Lanka Fernando
Subject: Re: Graph Theory

Hi,

Thanks for your answer, but how would I accomplish this using a 
breadth-first search?

Thanks again.

Date: 11/13/2000 at 19:16:14
From: Doctor Schwa
Subject: Re: Graph Theory

This *is* a breadth-first search: it tests ALL the possible paths of 
length 2 before it tries any paths of length 3, for example.

If you need to know only the girth, this is a pretty good way to do 
it.

- Doctor Schwa, The Math Forum
  http://mathforum.org/dr.math/