Suppose we construct a tree on a graph G with breadth-first search (BFS) and determine that there is no edge in the graph that connects nodes that belong to the same layer in the BFS tree. Does that mean that the graph has no cycle?
Asked
Active
Viewed 251 times
2
Michael Laszlo
- 12,009
- 2
- 29
- 47
Farhan Mazhar
- 21
- 4
-
Is this a DAG or undirected? – WestCoastProjects Sep 16 '15 at 17:25
-
A useful link: http://stackoverflow.com/questions/2869647/why-dfs-and-not-bfs-for-finding-cycle-in-graphs – displayName Sep 16 '15 at 17:40
-
Thank you Micheal Laszlo for the answer – Farhan Mazhar Sep 19 '15 at 04:04
1 Answers
0
No, it does not. Consider the following directed graph:
If we start BFS from node 1, the search ends at node 3. Each vertex is in a separate layer, so there is no edge in the graph that connects nodes belonging to the same layer. However, the graph contains a cycle.
We can also construct a counterexample for undirected graphs:
The first layer contains node 1. The second layer contains nodes 2 and 4. The third layer contains node 3. The only layer with more than one node is the second layer, and its two nodes are not connected by an edge. Once again, there is no edge in the graph between nodes in the same layer, yet the graph contains a cycle.
Michael Laszlo
- 12,009
- 2
- 29
- 47