• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon

Suggested languages for you:

Americas

Europe

Q35E

Expert-verified
Found in: Page 796

### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095

# Explain how to use breadth-first search to find the length of a shortest path between two vertices in an undirected graph.

By using the breadth-first search it can get that the length of the shortest path between two vertices is an undirected graph.

See the step by step solution

## Step 1: Compare with the definition.

A spanning tree of a simple graph G is a subgraph of G that is a tree and that contains all vertices of G.

A tree is an undirected graph that is connected and does not contain any single circuit. And a tree with n vertices has n-1 edges.

## Step 2: The breadth-first search method.

In breadth-first search first, choose a root. Add all edges incident to the root. Then each of the vertices at level 1, add all edges incident with ta vertex not included in the tree yet. And repeat until all vertices were added to the tree.

## Step 3: Find the shortest path.

Let u,v are two vertices in an undirected graph G. Assume the graph to be finite and connected. Any two vertices can still be separated by the concept of distance. Then the length of the shortest path between u and v is the level number of u in a breadth-first search spanning tree of G rooted at v.

Therefore, It gets the way to find the length of the shortest path between two vertices in an undirected graph.