For each of the six questions in parts (a -c), answer in terms of big-Oh and the

Question

For each of the six questions in parts (a -c), answer in terms of big-Oh and the number of vertices in the graph|V|.

(a) Suppose a graph has no edges.

i. What is the asymptotic space cost of storing the graph as an adjacency list?

ii. What is the asymptotic space cost of storing the graph as an adjacency matrix?

(b) Suppose a graph has every possible edge.

i. What is the asymptotic space cost of storing the graph as an adjacency list?

ii. What is the asymptotic space cost of storing the graph as an adjacency matrix?

(c) Suppose an undirected graph has one node A that is connected to every other node and the graph has no other edges.

i. What is the asymptotic space cost of storing the graph as an adjacency list?

ii. What is the asymptotic space cost of storing the graph as an adjacency matrix?

(d) Is an adjacency list faster or slower than an adjacency matrix for answering queries of the form,"is edge (u,v) in the graph"?

(e) Is an adjacency list faster or slower than an adjacency matrix for answering queries of the form,re there any directed edges with u as the source node"

Explanation / Answer

(a)

i).O(|V|)

ii).O(|V^2|)

(b)

i)O(|V^2|)

   ii)O(|V^2|)

(c)

   i)O(|V|)

   ii)O(|V^2|)

(d)slower than an adjacent matrix for answering the queries of the form ,'is edge (u,v) in the graph.

(e)Faster than a adjacent matrix for answerng queries of the form

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.