Find Node Having Maximum Number of Common Nodes with a Given Node K

Approach

Brute Force Approach:

We can solve the programming problem using Breadth First Search. We can store all the nodes which are connected to the given source node in a boolean array. The value at index i will be true if it is connected to the given source node. Now, we can perform breadth-first search on the graph and as we encounter each node in the subsequent levels, we will count the number of its immediate neighbours which are also connected to the source node. If the count is greater than the maximum value so far, we update our answer to the current node.

Efficient Approach

As you can observe in the above approach we are considering all the nodes in the graph. Is it really necessary to consider all the nodes in the graph for their candidature? The answer is NO. Little attention to detail is required here. We only need to consider those nodes in the breadth first traversal which are either at level 1 or 2. The source vertex is assumed to be at level 0. It is because from level 3, the nodes will not be connected to any node which is common with the given source node.

Algorithm

1. Create maxCommon = 0 and answerNode variables for holding the maximum common number of nodes and the answer node.
2. Create a queue vertexQue and insert the source vertex into it.
3. Create a boolean visited array and mark source vertex as true implying it is already inserted into the queue.
4. Create a level array of size N and in this array we will store the level of each node in the breadth-first search.
5. Mark the level of the source vertex as 0.
6. Create an adjacency list representation of the given graph in the 2-d array adjGraph.
7. Pop an element from the queue and do the following if its level is less than 2:
   1. Iterate through the nodes connected to the element and if it is not visited, mark it visited and push it into the queue.
   2. As you push a node to the queue, update its level in the level array as well.
   3. Now, for the popped out node, check how many nodes which are connected to it are also connected to the source node.
   4. If the number of common nodes comes out to be greater than maxCommon, update maxCommon and answerNode accordingly.
8. Output answerNode + 1 as we have assumed 0-numbering of the nodes.

Program

#include<bits/stdc++.h>
using namespace std;

int main(){
   // Edges in the graph.
   vector<vector<int>> edges = {{1, 2}, {1, 3}, {2, 3}, {3, 4}, {2, 4}};
   // Number of nodes in the graph.
   int N = 4;
   // The source vertex.
   int K = 1;
   vector<vector<int>> adjGraph(N);
   // Nodes which are connected to the source vertex.
   vector<bool> isConnected(N, false);
   // Create adjacency list representation.
   for(int i = 0; i < edges.size(); i++)
   {
       adjGraph[edges[i][0] - 1].push_back(edges[i][1] - 1);
       adjGraph[edges[i][1] - 1].push_back(edges[i][0] - 1);
       // If any one of the nodes in the edge is the source vertex, mark the other one as connected.
       if(edges[i][0] == K){
           isConnected[edges[i][1] - 1] = true;
       }
       else if(edges[i][1] == K){
           isConnected[edges[i][0] - 1] = true;
       }
   }
   // The queue as described in the approach.
   queue<int> vertexQue;
   //  Push the source vertex in 0-numbering format.
   vertexQue.push(K - 1);
   // Visited array as described in the approach.
   vector<bool> visited(N, false);
   // Level array to hold the levels of the nodes in the breadth first search.
   vector<int> level(N, 0);
   // Mark the source vertex as visited.
   visited[K - 1] = true;
   // Utility variables declaration.
   int maxCommon = 0, answerNode = -1;
   while(!vertexQue.empty())
   {
       // Pop a vertex from the queue.
       int s = vertexQue.front();
       vertexQue.pop();
       // Iterate its adjacency list.
       for(int i = 0; i < adjGraph[s].size(); i++){
           // Node v is connected to node s.
           int v = adjGraph[s][i];
           // Level of node v.
           int levelNode = level[s] + 1;
           // As described in the approach.
           if(visited[v] || levelNode >= 3) continue;
           // Mark as visited and push it to the queue.
           visited[v] = 1;
           // Update the level of the node.
           level[v] = levelNode;
           vertexQue.push(v);
       }
       // Count the common nodes.
       int count = 0;
       if(s != K - 1){
           for(auto node:adjGraph[s]){
               if(isConnected[node]){
                   count++;
               }
           }
       }
       // Update if necessary.
       if(count > maxCommon){
           maxCommon = count;
           answerNode = s;
       }
   }

   // Output after adding one as we have following 0-numbering.
   cout<<answerNode + 1<<endl;
}

You can also try this code with Online C++ Compiler

Run Code

Input

Edges: {{1, 2}, {1, 3}, {2, 3}, {3, 4}, {2, 4}}

K = 1

Output

4

Input

Edges: {{1, 2}, {1, 3}, {1, 4}, {2, 3}, {3, 4}, {2, 4}, {5, 2}, {5, 3}, {5, 4}}

K = 1

Output

5

Time Complexity

The time complexity of the above approach is O(V + E) where V is the number of nodes in the graph and E is the number of edges. It is because it contains a Breadth first search of the given graph.

Space Complexity

The space complexity of the above approach is O(V) where V is the number of nodes in the graph. It is because the queue and arrays take utmost O(V) space.

FAQs

1. What is the time complexity of Breadth-First Search?
   The time complexity of BFS is O(V + E) where V is the number of nodes in the graph and E is the number of edges.
    
2. What are the different forms to represent a graph?
   A graph can be represented as an array of edges or using an adjacency list or in the form of a V x V matrix where (i, j) is non-zero if i and j are connected in the graph. This form is also called adjacency matrix representation.
    
3. What are the different applications of BFS?
   BFS search can be used to find the shortest path between a source vertex and all other vertices in the graph if the edges are either 0/1 weighted.
   It can be used to find cycles in a graph and with slight modifications it can be used as multi-source bfs as well.
    
4. What is the time complexity of BFS search with adjacency matrix representation?
   The time complexity of BFS with adjacency matrix representation is O(V^2) where V is the number of nodes in the graph.

Key Takeaways

Cheers if you reached here!! 

This article aimed to discuss an intriguing problem using graph BFS. We saw an exciting application of the BFS technique in this article. BFS-related coding problems are sometimes simple to implement, but finding an efficient approach on the basis of certain observations remains difficult.

Check out this problem - Connect Nodes At Same Level

Yet learning never stops, and there is a lot more to learn. So head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Learning!!