Problem:
Which of the following statements hold? (As usual n and m denote the number of vertices and edges, respectively, of a graph.) [Check all that apply.]
Solution:
Breadth-first search can be used to compute the connected components of an undirected graph in $ O(m+n) $ time.
Depth-first search can be used to compute the strongly connected components of a directed graph in $ O(m+n) $ time.
Breadth-first search can be used to compute shortest paths in $ O(m+n) $ time (when every edge has unit length).
Depth-first search can be used to compute a topological ordering of a directed acyclic graph in $ O(m+n) $ time.
All of these options are correct and all of them are just standard results.
Which of the following statements hold? (As usual n and m denote the number of vertices and edges, respectively, of a graph.) [Check all that apply.]
Solution:
Breadth-first search can be used to compute the connected components of an undirected graph in $ O(m+n) $ time.
Depth-first search can be used to compute the strongly connected components of a directed graph in $ O(m+n) $ time.
Breadth-first search can be used to compute shortest paths in $ O(m+n) $ time (when every edge has unit length).
Depth-first search can be used to compute a topological ordering of a directed acyclic graph in $ O(m+n) $ time.
All of these options are correct and all of them are just standard results.
No comments:
Post a Comment