Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Input
2.2.
Output
2.3.
Explanation
2.4.
Input
2.5.
Output
2.6.
Explanation
3.
Approach
3.1.
Algorithm
3.2.
Program
3.3.
Input
3.4.
Output
3.5.
Input
3.6.
Output
3.7.
Time Complexity
3.8.
Space Complexity
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

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

Author Anant Dhakad
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

In this blog, we will discuss a problem based on Breadth First Search of a graph. Breadth First Search is a widely asked topic in programming contests and technical interviews. We will take up a coding challenge which involves the concept of levels used in breadth first search. We will consider the nodes in each level one by one and explore its candidature for the answer to the problem.

Problem Statement

Ninja has given you a graph represented by a two-dimensional array of edges and an integer K. Each element in the array of edges represented by {edges[i][0], edges[i][1]} corresponds to an undirected edge between edges[i][0] and edges[i][1]. Your task is to find the node which is connected to the maximum number of nodes which are connected to the given node K.

Input

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

K = 1

Output

4

Explanation

The graph in adjacency-list representation:

1: 2, 3 

2: 1, 3, 4 

3: 1, 2, 4 

4: 2, 3 

As you can see, node 4 is connected to both second and third nodes which are connected to the first node, i.e., node 4 has the maximum number of common nodes with node 1.

Input

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

K = 1

Output

5

Explanation

The graph in adjacency-list representation:

1: 2, 3, 4

2: 1, 3, 4, 5

3: 1, 2, 4, 5

4: 1, 2, 3, 5

5: 2, 3, 4

As you can see, node 5 is connected to all second, third and fourth nodes which are connected to the first node, i.e., node 5 has the maximum number of common nodes with node 1.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
}

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!!

Previous article
Find the Height of a Generic Tree from Parent Array
Next article
Find minimum S-T cut in a flow network
Live masterclass