GATE CSE 2016 Set 2 | Question: 41

Question

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?

• A. $\Theta\left(n^{2}\right)$
• B. $\Theta\left(n+m\right)$
• C. $\Theta\left(m^{2}\right)$
• D. $\Theta\left(n^{4}\right)$

Comments

@Pranavpurkar Palash’s method is no different than our usual adjacency list (or Linked List) implementation of Graph where we use hashing & chaining combined to store the vertices and their adjacent edges in chain.

---

check this out. 100% clarity

---

@chauhansunil20th amazing explanation and i was having doubt that adjacency list linked list will have different rep than usual, thanks for confirming it also.

Answer 1

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$

Comments

the only solution which i finally understood. Thanks

---

@sushmita still not understood. Can you please explain more :(

---

what would have been the time complexity if no extra space has been given ?

---

You can visualize better with the image below.

---

Actually what we are doing is storing addresses of nodes in adjacency list of supplied graph in 2D array during initial BFS traversal and then in the final BFS traversal we are using 2D array from initial BFS traversal which we can use to find the twin pointer address.

A[i][j] contains the twin pointer address for jth node in the adjacency list of node i.

1->2 edge twin is 2->1, node 2 in adjacency list of node 1 is pointing to node 1 in adjacency list of node 2, and vice-versa.

---

like if we do bfs, we start with some edge u-v, then we are on edge u itself, there it is linked to edge v so we get address of edge v then we update the 2d array at a[u][v]. till here its fine, but if we are at u itself, dont we know the address of u,? If we know the address of u, we can go to a[v][u] and put that address and its done ?

---

Since it is an undirected graph, representing it into directly Adjacency list,we can get twins as for ex: If there is an edge 1->2 in the undirected graph then we also say that there will definitely be an edge

2->1 hence we can just apply bfs on adjacency list which will give O(n+m), then why we need to consider storing it into the matrix and then doing all the procedure?

Answer 2

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.

Comments

Dfs can also be used here since it has same TC as Bsf

---

@Chhotu what if it was a complete graph?  then time complexity would be $\theta(n+m)=\theta(n+n^2)=\theta(n^2)$ ?

---

What would be time complexity if no extra space is given?

Answer 3

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 2^nd 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.

Answer 4

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)$

Comments

@Sumit1311

Can't understand what u r trying to explain. can u explain more detail on "every undirected edge is replaced by two directed edges one forward and one backward".