Discussion
In an adjacency list representation of an undirected simple graph \(G = (V,E)\), each edge \((u, v)\) has two adjacency list entries: [\(v\)] in the adjacency list of \(u\), and [\(u\)] in the adjacency list of \(v\). These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If \(|E| = m\) and \(|V| = n\), and the memory size is not a constraint, what is the time complexity of the most efficient algorithm to set the twin pointer in each entry in each adjacency list?
Answer: B
The most efficient algorithm runs in \(\Theta(n + m)\).
Any algorithm must at least read all \(n\) lists and all \(2m\) entries, so \(\Omega(n + m)\) is a lower bound. It can be met:
- For each entry [\(v\)] in the list of \(u\), form the key \((\min(u,v), \max(u,v))\); the two twins of an edge get the same key.
- Sort all \(2m\) entries by key with a two-pass bucket (radix) sort on vertex numbers, which takes \(O(n + m)\).
- Twins are now adjacent in the sorted order, so one pass sets each pair of twin pointers.
A hash table keyed on the vertex pair achieves the same expected bound, and memory is stated not to be a constraint. \(\Theta(n^{2})\) is what a full adjacency-matrix lookup costs, and \(\Theta(m^{2})\) comes from searching a twin’s whole list for every entry; both are slower than necessary.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development