edited by
19,517 views
93 votes
93 votes

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?

  1. $\Theta\left(n^{2}\right)$
  2. $\Theta\left(n+m\right)$
  3. $\Theta\left(m^{2}\right)$
  4. $\Theta\left(n^{4}\right)$
edited by

4 Answers

Best answer
69 votes
69 votes

We can take extra array of size $V^2$ as memory is not a constraint.

Do the BFS traversal and for each edge $u-v$ in advance list in graph store the $v$ node address in $a[i][j].$

For e.g., if we find $1\to 2$ as an edge, then store node $2$ node address in location $a[i][j].$

Now once we have stored all the edge $(u-v)$ addresses, then do BFS again.

Now when we encounter $1\to 2,$ then goto $a[2][1]$ which is having twin address and set this twin pointer for node $2$ in list $1.$

Do for all edges similarly.


Remember, we have not initialized memory as we will use only slots we need. If we initialize memory it can take $O(V^2)$ time. We can also use one hash table per node to store the node address while doing first traversal.The key to has table for Node $u$ is the vertex $v$ (for edge $u-v$ means in $u$ table it has edge to $v$ and  we are storing $v$ address) and value will be $v$ address.

Correct Answer: $B$

selected by
68 votes
68 votes

Applying BFS on undirected graph gives you twin pointer. Visit every vertex level-wise. For every vertex, fill adjacent vertex in the adjacency list. BFS takes $\Theta\left(n+m\right)$ time.

Take extra field for storing number of linked lists for particular vertex. Take extra $m+n$ time( $m$ vertex and $n$ edges).

So, option B is the answer.

edited by
8 votes
8 votes

I have read all comments and students have many doubts:

Let me clear it for you.

Doubt 1: visualization of twin pointers

Doubt 2: optimized algorithm with extra space as space is not a constraint.

X 106 108 110
101 X 109 111
102 104 X 112
103 105 107 X

 

Lets us take an example of a complete graph ‘G’ with 4 nodes. The above diagram shows the linked list representation of G.

initialize a matrix add[1 to 4][1 to 4]  keep a record of the address of each node while traversing for the first time.

Ex: If are starting from 1 then store ‘101’ in add[2][1]. Similarly, do for all nodes.

The time complexity of doing this step is O(m+n).

Now do 2nd traversing, and fill the address of twins for each node by using matrix.

Ex: for a node with 101 address fill the twin pointer with add[1][2] i.e 106.

The time for doing this will be O(n+m).

Overall time complexity = O(n+m)

Note: Here we are not traversing the matrix but only directly accessing specific elements of the matrix.

Doubt 3: Many students are using BFS and DFS. Honestly speaking you can use anything BFS, DFS, or simple traversing like I have used it. It will give the same time complexity.

Use of BFS is done to reduce the number of traversing of adjacency list as while filling the matrix u can fill twin pointers too at the same time.

4 votes
4 votes
Can we use this approach not sure about this?

We will consider a directed graph with every undirected edge is replaced by two directed edges one forward and one backward. Then we do DFS-like traversal on this graph and set the twin pointer of as it's parent pointer. So the time complexity will be $ \theta(m+n)$
Answer:

Related questions

49 votes
49 votes
8 answers
1