Tree Structures in DFS and BFS Algorithms
Explore the concepts of DFS and BFS trees, including properties, edge types, and ancestor relationships. Learn about tree edges, forward edges, back edges, and cross edges in the context of directed and undirected graphs. Discover the layering strategy in BFS trees and the importance of ancestor positions in DFS/BFS trees.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CS330 Discussion 5 Spring 2017
BFS Tree In lecture, we discussed a DFS tree. Given a DFS run on graph ? edge ?,? is in the DFS tree if ? is first arrived at using (?,?). We can define a BFS tree using the exact same definition.
Properties of BFS trees When we run BFS and get a BFS tree, we can create a layering on the graph. We start by saying layer 0 consists of the root of the BFS. Then, layer 1 is all vertices which are adjacent to the root. Layer 2 is all vertices adjacent to vertices in layer 1, except the root. Continuing the pattern, layer ? is all vertices adjacent to vertices in layer ? 1, that do not appear in any previous layers.
Properties of BFS trees Claim: Let (?,?) be an edge in a directed graph. If we run a BFS and split the vertices into layers, the layer of ? cannot exceed the layer of ? by more than 1. Why? What s the equivalent claim for an undirected graph?
Properties of DFS trees ? is an ancestor of ? in a DFS/BFS tree if ? is on the path in the tree from the root of the DFS/BFS to ?. Claim: If (?,?) is an edge in an undirected graph, then in any DFS either ? is an ancestor of ?, or ? is an ancestor of ?. Why? Is there an equivalent claim for a directed graph?
Edge types in a DFS/BFS tree Given a DFS/BFS tree, we can define different types of edges. First, all edges which are a part of the DFS/BFS tree are referred to as tree edges.
Edge types in a DFS/BFS tree Edges may exist in the graph but not be included in the DFS/BFS tree (i.e. not be tree edges). These edges are split into three types. (?,?) is a forward edge if ? is an ancestor of ? (?,?) is a back edge if ? is an ancestor of ? (?,?) is a cross edge if ? is not an ancestor of ? and ? is not an ancestor of ?
Edge types in a DFS/BFS tree Consider a directed graph, and a DFS/BFS for the graph. For both DFS and BFS, if the graph has edges then clearly we will always have tree edges. Whether the other types will exist is not so apparent. In a DFS, can we have a cross edge? A forward edge? A back edge? In a BFS, can we have a cross edge? A forward edge? A back edge?
A note on undirected graphs We can also define tree, forward, back, and cross edges for DFS/BFS on a directed graph. However, the definition of forward/back becomes a bit less clear since the edge does not have a direction. To resolve this, we ll assign each edge whichever direction the DFS/BFS first explores that edge in. So if we try to visit ? from ? before visiting ? from ? in the DFS/BFS, we ll treat the edge as being directed from ? to ?.
Graph Algorithm Practice Problem 1 You are given a directed graph ?(?,?) with unweighted edges, as well as two vertices ?,? and a subset of vertices ? which does not include either ? or ?. Write an algorithm to find the shortest path from ? to ? that passes through at least one vertex in ?.
Graph Algorithm Practice Problem 2 You are given a graph ?(?,?) with unweighted edges, and two disjoint subsets of ?, ? and ?. Write an algorithm to determine the shortest path from any vertex in ? to any vertex in ?. Also provide its runtime.
