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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.