senting G that allows us to implement the operations areAdjacent Cu,v) and incid
ID: 666429 • Letter: S
Question
senting G that allows us to implement the operations areAdjacent Cu,v) and incident Edges (u). Let n be the number of vertices and m be the number of edges. Which of the following is true? (A) An edge list (an array storing all edges of the graph) allows us to perform incidentEdges (u) in O(degree (u)) time and areAdjacent (u,v) in O(1) time. (B) With an adjacency list areAdjacent Cu,v) can be implemented in O(1) time and incident Edges (u) in O(degree (u)) time (C) An adjacency matrix allows us to implement both operations in O(1) time. (D) An adjacency list allows us to implement both operations in O(1) time. (E) An adjacency matrix can implement areAdjacent (u,v) in O(1) time and incidentEdges (u,v) in O(n) time.Explanation / Answer
(A)
False.
Explanation: areAdjacent(u, v) will take min(deg(u),deg(v)) using adjaceny list
(B)
False.
Explanation: areAdjacent(u, v) will take min(deg(u),deg(v)) using adjaceny list
(C)
False.
Explanation: incidentEdges(u) will take O(n) time using adjacency matrix
(D)
False.
Explanation: areAdjacent(u, v) will take min(deg(u),deg(v)) using adjaceny list.
incidentEdges(u) will take O(degree(u)) time using adjacency list
(E)
True
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.