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

the question is basically asking that if edge u and v are neighbours , then v's twin pointer should to be added to u's adjacency list and u's twin pointer should be added in v's adjacency list.

---

See you can refer to the answers for a better conceptual explanation .But if you are blank in exam hall you can try this approach .see we need to traverse the nodes of a graph.What are the two traversals DFS and BFS and both take o(n+m) time and then you need to compare this two l;ists whioch agains requires a traversal of o(n+m) so in short we are traversing o(n+M) time

---

Answer: B. Θ(n+m)\Theta(n + m)Θ(n+m)

Why: traverse every adjacency-list entry once (there are 2m2m2m entries) and use a hash table (or array of buckets keyed by the unordered pair (min⁡(u,v),max⁡(u,v))(\min(u,v),\max(u,v))(min(u,v),max(u,v)) or by edge ID) to match the twin when you first see its partner. Each adjacency entry causes O(1) expected work (hash insert or lookup), so total time is Θ(n+m)\Theta(n + m)Θ(n+m) (or more precisely Θ(m)\Theta(m)Θ(m) plus the cost to scan the vertex heads, hence Θ(n+m)\Theta(n+m)Θ(n+m)).

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

wait i dont get it. do we store adress  of the edge node or the vertex. is twi connected two edge ddress tht represent same vertex r what

---

I think we don't need any bfs or dfs traversal to put twin pointer if we simply traverse over the adjacency list then we can easily put twin pointer because in undirected graph if u is connected to v then v is also connected to u

It will also take same time complexity O(n+M)

---

We can do it in only O(V) extra space with hash table by storing end pointer for each list.

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.

Comments

Bro, but we are traversing each edge twice right so we will ve theta(n+2m) right?

---

people still have a doubt : why not DFS here's why

say a simple undirected Graph

A-------B
|       |
|       |
|       |
C-------D------S

if we applied DFS, one of the DFS traversal's among 2 will look like 
A -> B -> D -> S ->C, with this we can't make entries in A[i][j] (refer best answer)
A->B (twin entry of A and B possible)

B->D (twin entry of B and D possible)

D->S (twin entry possible)

now backtarck to D, D->C (twin entry possible)

backtrack to D to B to A
but what about twin entry b/w A and C ???

whereas BFS traversal would look like A -> B ->C ->D -> S

BFS we'll have every twin entry

also a subtle hint by the question 

memory is not a constraint, in DFS memory grows linearly whereas in BFS it grows exponentially so along with the hash array/table we are using BFS also uses more memory than DFS

---

Can anyone make me understand whose addressing we're storing where, it's so confusing. I'm trying to understand this from last 30 mins. Please make me understand

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".

 

Answer 5

We are given an undirected simple graph $ G = (V, E) $ with $ n = |V| $ vertices and $ m = |E| $ edges, stored as an adjacency list. Since the graph is undirected, each edge $ \{u, v\} $ appears twice: once as $ v $ in $ u $’s list and once as $ u $ in $ v $’s list. These two entries are called twins, and the goal is to set a twin pointer from each entry to its twin.

A brute-force method searching for the twin by scanning the neighbor’s list could take $ O(\deg(v)) $ per entry, leading to $ O(m^2) $ time in the worst case. However, we can achieve optimal performance using a hash table.

 

Efficient Algorithm Using a Hash Table:

We process each of the $ 2m $ adjacency list entries exactly once. For an entry representing the directed pair $ (u, v) $, we create a canonical key for the undirected edge:
$$
k = (\min(u,v),\ \max(u,v))
$$
This ensures that both $ (u,v) $ and $ (v,u) $ map to the same key.

We maintain a hash table that maps each key $ k $ to the first adjacency-list node seen for that edge. When we encounter the second occurrence (the twin), we link the two nodes with twin pointers.

The steps are:

• Initialize an empty hash table $ H $.
• For each vertex $ u \in V $:
•   For each neighbor $ v $ in $ u $’s adjacency list:
  •   Let $ k = (\min(u,v), \max(u,v)) $.
  •   If $ k \notin H $, store a pointer to this list node in $ H[k] $.
•   Else, retrieve the stored node from $ H[k] $, and set mutual twin pointers between the two nodes.

Each operation (hash lookup, insertion, pointer assignment) takes $ O(1) $ expected time. The total number of entries processed is $ 2m $, and we also iterate over $ n $ vertices to access their lists.

Thus, the total time complexity is $ \Theta(n + m) $.

Example of Hash Table Usage

Consider a graph with edges $ \{1,2\}, \{2,3\} $. The adjacency lists are:

1. Vertex 1: [2]  
2. Vertex 2: [1, 3]  
3. Vertex 3: [2]

As we process each entry, the hash table evolves as follows:

$$
\begin{array}{|c|c|c|}
\hline
\text{Step} & \text{Entry Processed} & \text{Hash Table } H \\
\hline
1 & (1,2) & \{ (1,2) \mapsto \text{node}_{1\to2} \} \\
2 & (2,1) & \text{Twin found! Link } \text{node}_{2\to1} \leftrightarrow \text{node}_{1\to2} \\
3 & (2,3) & \{ (1,2) \mapsto \cdots,\ (2,3) \mapsto \text{node}_{2\to3} \} \\
4 & (3,2) & \text{Twin found! Link } \text{node}_{3\to2} \leftrightarrow \text{node}_{2\to3} \\
\hline
\end{array}
$$

After processing all entries, every adjacency list node has its twin pointer correctly set.

The algorithm runs in linear time relative to the input size, which is $ \Theta(n + m) $. This is optimal, as we must examine every vertex and every edge at least once.

$$
\boxed{\text{B. } \Theta(n + m)}
$$

Answer 6

Do BFS traversal and create Adjaceny List(or Dictionary) with key having Vertex and item with Node address like
1->100
2->200
3->300....

Here 100 is address of node 1, 200 is address of node 2,etc

Now, do BFS on adjaceny List of graph and if node 1 has neighbor like 3,5,6 then add address of node 1 i.e 100 (which we got using our created Dictionary) and add it to 3,5,6 and then go to node 2 and add address of node 2 i.e 200 for all its neighbor and so on.

Here also TC=V+E