Associated Topics || Dr. Math Home || Search Dr. Math

```
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

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
Math Forum Home || Math Library || Quick Reference || Math Forum Search