Register

Cormen Edition 3 Exercise 22.1 Question 8 (Page No. 593)

454 views
0 0 votes
Suppose that instead of a linked list, each array entry $adj[u]$ is a hash table containing the vertices $v$ for which $(u,v) \in E$. If all edge lookups are equally likely, what is the expected time to determine whether an edge is in the graph? What disadvantages does this scheme have ? Suggest an alternate data structure for each edge list that solves these problems. Does your alternative have disadvantages compared to the hash table ?

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← Previous · REQUEST FOR SOLUTION...Next → · #arrays
← Previous in category · Cormen Edition 3 Exe...Next in category → · Vani Question Bank
Position:
Show:

Related questions

0 0 votes
0 0 answers
443
443 views
akash.dinkar12 asked Apr 7, 2019
443 views
Cormen Edition 3 Exercise 22.1 Question 6 (Page No. 593)
Most graph algorithms that take an adjacency-matrix representation as input require time $\Omega(V^2)$,but there are some exceptions. Show how to determine whether a dire...
0 0 votes
0 0 answers
435
435 views
akash.dinkar12 asked Apr 7, 2019
435 views
Cormen Edition 3 Exercise 22.1 Question 5 (Page No. 593)
The square of a directed graph $G=(V,E)$ is the graph $G^2=(V,E^2)$ such that $(u,v) \in E^2$ if and only $G$ contains a path with at most two edges between $u$ and $v$ ....
0 0 votes
1 1 answer
1.5k
1.5k views
akash.dinkar12 asked Apr 7, 2019
1,486 views
Cormen Edition 3 Exercise 22.1 Question 4 (Page No. 593)
Given an adjacency-list representation of a multi graph $G=(V,E)$, describe an $O(V+E)$ time algorithm to compute the adjacency-list representation of the “equivalent” un...
1 1 vote
1 1 answer
5.3k
5.3k views
akash.dinkar12 asked Apr 7, 2019
5,326 views
Cormen Edition 3 Exercise 22.1 Question 3 (Page No. 592)
The transpose of a directed graph $G=(V,E)$ is the graph $G^T=(V,E^T)$, where $E^T=\{(v,u) \in V * V :(u,v) \in E \ \}$ .Thus ,$G^T$ is $G$ with all its edges reversed . ...