Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/   
    
Associated Topics:
College Discrete Math
High School Discrete Mathematics

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/