Suppose that instead of a linked list, each array entry Adj[u]is a hash table co

Question

Suppose that instead of a linked list, each array entry Adj[u]is a hash table containing the vertices v for which (u,v) belongsto E. If all edge lookups are equally likely: -what is the expected time to determine whether an edge is inthe graph? -what disadvantages does this scheme have? -suggest an alternate data structure for each edge list thatsolves these problems. Suppose that instead of a linked list, each array entry Adj[u]is a hash table containing the vertices v for which (u,v) belongsto E. If all edge lookups are equally likely: -what is the expected time to determine whether an edge is inthe graph? -what disadvantages does this scheme have? -suggest an alternate data structure for each edge list thatsolves these problems.

Explanation / Answer

Let G={V,E) be a diagraph with n=[V] and let e=[E]. We willassume that the vertices fo G are indexed{1,2,……,n}

An adjancy matrix is a nxn matrix defined for 1<v,w<n;

An adjancy list is an array Adj[1…n] of pointers where for1<v<n, Adj[v] points to a linked list containing the verticeswhich are adjactent to v.

You can download complete solution for your problem from

Vulms.vu.edu.pk/library/library.aspx

Please download cs502 handout and your solution is at page116..

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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