Find node having maximum number of common nodes with a given node K

0 0 8 minutes read

Given a graph consisting of N nodes and an array edges[][] denoting an edge from edges[i][0] with edges[i][1]. Given a node K, the task is to find the node which has the maximum number of common nodes with K.

Examples:

Input: K = 1, N = 4, edges = {{1, 2}, {1, 3}, {2, 3}, {3, 4}, {2, 4}}
Output: 4
Explanation: The graph formed by given edges is shown below.
Given K = 1, Adjacent nodes to all the nodes are below
1: 2, 3
2: 1, 3, 4
3: 1, 2, 4
4: 2, 3
Clearly node 4 is having maximum common nodes with node 1. Therefore, 4 is the answer.

Input: K = 2, N = 3, edges = {{1, 2}, {1, 3}, {2, 3}}
Output: 3

Approach: This problem can be solved by using Breadth-First Search. Follow the steps below to solve the given problem.

The idea is to use BFS with the source as a given node (level 0).
Store all the neighbors of a given node in a list, let’s say al1 (level 1)
Now maintain another list al2 and store each level in BFS and count the common elements of al1 with al2.
Maintain variable max to maintain the count of maximum common friends and another variable mostAppnode to store answer of the given problem.
Return mostAppnode.

Below is the implementation of the above approach:

C++

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
// No. of nodes
int V;
 
// Adjacency Lists
vector<vector<int> > adj;
 
// Neighbours of given node stored in al1
vector<int> al1;
 
void create_Graph(int v)
{
  V = v;
  adj = {};
  for (int i = 0; i < v; ++i)
    adj.push_back({});
}
 
// Function to add an edge into the graph
void addEdge(int v, int w)
{
  adj[(v - 1)].push_back(w - 1);
  adj[(w - 1)].push_back(v - 1);
}
 
// find element in queue
bool contains(queue<int> q, int n)
{
  while (q.size()) {
    if (q.front() == n)
      return 1;
    q.pop();
  }
  return false;
}
int BFS(int s)
{
  // Mark all the vertices as not visited
  // (By default set as false)
  bool visited[V] = { 0 };
 
  // Create a queue for BFS
  queue<int> queue;
 
  // Mark the current node
  // as visited and enqueue it
  visited[s] = true;
 
  queue.push(s);
  int c = 0;
 
  // Max common nodes with given node
  int max = 0;
 
  int mostAppnode = 0;
  // To store common nodes
  int count = 0;
  while (queue.size() != 0) {
 
    // Dequeue a vertex from queue
    s = queue.front();
    queue.pop();
    // Get all adjacent nodes
    // of the dequeued node
    // If a adjacent has
    // not been visited, then
    // mark it visited and enqueue it
    c++;
 
    vector<int> al2;
    int i = 0;
 
    while (i < adj[s].size()) {
      int n = adj[s][i];
      if (c == 1)
        al1.push_back(n);
      else
        al2.push_back(n);
 
      // If node is not
      // visited and also not
      // present in queue.
      if (!visited[n] && !contains(queue, n)) {
        visited[n] = true;
        queue.push(n);
      }
      i++;
    }
    if (al2.size() != 0) {
      for (int frnd : al2) {
        if (find(al1.begin(), al1.end(), frnd)
            != al1.end())
          count++;
      }
      if (count > max) {
        max = count;
        mostAppnode = s;
      }
    }
  }
  if (max != 0)
    return mostAppnode + 1;
  else
    return -1;
}
 
// Driver Code
int main()
{
  int N = 4;
  create_Graph(4);
 
  addEdge(1, 2);
  addEdge(1, 3);
  addEdge(2, 3);
  addEdge(3, 4);
  addEdge(2, 4);
  int K = 1;
  cout << (BFS(K - 1)) << endl;
}
 
// This code is contributed by rj13to.

Java

// Java implementation of above approach
import java.io.*;
import java.util.*;
 
class Graph {
 
    // No. of nodes
    private int V;
 
    // Adjacency Lists
    private ArrayList<ArrayList<Integer> > adj;
 
    // Neighbours of given node stored in al1
    ArrayList<Integer> al1 = new ArrayList<>();
 
    // Constructor
    Graph(int v)
    {
        V = v;
        adj = new ArrayList<>();
 
        for (int i = 0; i < v; ++i)
            adj.add(new ArrayList<Integer>());
    }
 
    // Function to add an edge into the graph
    void addEdge(int v, int w)
    {
        adj.get(v - 1).add(w - 1);
        adj.get(w - 1).add(v - 1);
    }
    private int BFS(int s)
    {
        // Mark all the vertices as not visited
        // (By default set as false)
        boolean visited[] = new boolean[V];
 
        // Create a queue for BFS
        LinkedList<Integer> queue
            = new LinkedList<Integer>();
 
        // Mark the current node
        // as visited and enqueue it
        visited[s] = true;
 
        queue.add(s);
        int c = 0;
 
        // Max common nodes with given node
        int max = 0;
 
        int mostAppnode = 0;
 
        // To store common nodes
        int count = 0;
        while (queue.size() != 0) {
 
            // Dequeue a vertex from queue
            s = queue.poll();
 
            // Get all adjacent nodes
            // of the dequeued node
            // If a adjacent has
            // not been visited, then
            // mark it visited and enqueue it
            c++;
 
            ArrayList<Integer> al2
                = new ArrayList<>();
            Iterator<Integer> i
                = adj.get(s).listIterator();
            while (i.hasNext()) {
                int n = i.next();
                if (c == 1)
                    al1.add(n);
                else
                    al2.add(n);
 
                // If node is not
                // visited and also not
                // present in queue.
                if (!visited[n]
                    && !queue.contains(n)) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
            if (al2.size() != 0) {
                for (int frnd : al2) {
                    if (al1.contains(frnd))
                        count++;
                }
                if (count > max) {
                    max = count;
                    mostAppnode = s;
                }
            }
        }
        if (max != 0)
            return mostAppnode + 1;
        else
            return -1;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int N = 4;
        Graph g = new Graph(4);
 
        g.addEdge(1, 2);
        g.addEdge(1, 3);
        g.addEdge(2, 3);
        g.addEdge(3, 4);
        g.addEdge(2, 4);
        int K = 1;
        System.out.println(g.BFS(K - 1));
    }
}

Python3

# python implementation of above approach
 
# Neighbours of given node stored in al1
al1 = []
 
# Function to add an edge into the graph
 
 
def addEdge(v, w, adj):
    adj[v - 1].append(w - 1)
    adj[w - 1].append(v - 1)
 
 
def BFS(s, adj, V):
 
    # Mark all the vertices as not visited
    # (By default set as false)
    visited = [False] * V
 
    # Create a queue for BFS
    queue = []
 
    # Mark the current node
    # as visited and enqueue it
    visited[s] = True
 
    queue.append(s)
    c = 0
 
    # Max common nodes with given node
    max = 0
 
    mostAppnode = 0
 
    # To store common nodes
    count = 0
    while (len(queue) != 0):
 
        # Dequeue a vertex from queue
        s = queue[0]
        queue.pop(0)
 
        # Get all adjacent nodes
        # of the dequeued node
        # If a adjacent has
        # not been visited, then
        # mark it visited and enqueue it
        c += 1
 
        al2 = []
 
        for i in adj[s]:
            n = i
            if (c == 1):
                al1.append(n)
            else:
                al2.append(n)
 
            # If node is not
            # visited and also not
            # present in queue.
            is_contained = False
            if(n in queue):
                is_contained = True
            if ((visited[n] == False) and (is_contained == False)):
                visited[n] = True
                queue.append(n)
 
        if (len(al2) != 0):
            for frnd in al2:
                if (frnd in al1):
                    count += 1
            if (count > max):
                max = count
                mostAppnode = s
 
    if (max != 0):
        return mostAppnode + 1
    else:
        return -1
 
# Driver Code
N = 4
 
# list to store connections
adj = [[]]*N
addEdge(1, 2, adj)
addEdge(1, 3, adj)
addEdge(2, 3, adj)
addEdge(3, 4, adj)
addEdge(2, 4, adj)
K = 1
print(BFS(K - 1, adj, N))
 
# This code is contributed by rj13to.

C++

#include <iostream>
using namespace std;
 
int main() {
 
    cout << "GFG!";
    return 0;
}

C#

using System;
using System.Collections.Generic;
using System.Linq;
 
class Program
{
    // No. of nodes
    static int V;
 
    // Adjacency Lists
    static List<List<int>> adj = new List<List<int>>();
 
    // Neighbours of given node stored in al1
    static List<int> al1 = new List<int>();
 
    static void CreateGraph(int v)
    {
        V = v;
        adj = new List<List<int>>();
        for (int i = 0; i < v; i++)
        {
            adj.Add(new List<int>());
        }
    }
 
    // Function to add an edge into the graph
    static void AddEdge(int v, int w)
    {
        adj[(v - 1)].Add(w - 1);
        adj[(w - 1)].Add(v - 1);
    }
 
    // find element in queue
    static bool Contains(Queue<int> q, int n)
    {
        while (q.Count > 0)
        {
            if (q.Peek() == n) return true;
            q.Dequeue();
        }
        return false;
    }
 
    static int BFS(int s)
    {
        // Mark all the vertices as not visited
        // (By default set as false)
        bool[] visited = new bool[V];
 
        // Create a queue for BFS
        Queue<int> queue = new Queue<int>();
 
        // Mark the current node
        // as visited and enqueue it
        visited[s] = true;
 
        queue.Enqueue(s);
        int c = 0;
 
        // Max common nodes with given node
        int max = 0;
 
        int mostAppnode = 0;
        // To store common nodes
        int count = 0;
        while (queue.Count > 0)
        {
 
            // Dequeue a vertex from queue
            s = queue.Dequeue();
            // Get all adjacent nodes
            // of the dequeued node
            // If a adjacent has
            // not been visited, then
            // mark it visited and enqueue it
            c++;
 
            List<int> al2 = new List<int>();
            int i = 0;
 
            while (i < adj[s].Count)
            {
                int n = adj[s][i];
                if (c == 1)
                    al1.Add(n);
                else
                    al2.Add(n);
 
                // If node is not
                // visited and also not
                // present in queue.
                if (!visited[n] && !Contains(queue, n))
                {
                    visited[n] = true;
                    queue.Enqueue(n);
                }
                i++;
            }
            if (al2.Count > 0)
            {
                for (int frnd : al2)
                {
                    if (al1.Contains(frnd))
                        count++;
                }
                if (count > max)
                {
                    max = count;
                    mostAppnode = s;
                }
            }
        }
        if

Javascript

// JavaScript implementation of the C++ code above
 
// No. of nodes
let V;
 
// Adjacency Lists
let adj = [];
 
// Neighbours of given node stored in al1
let al1 = [];
 
function create_Graph(v) {
  V = v;
  adj = [];
  for (let i = 0; i < v; ++i)
    adj.push([]);
}
 
// Function to add an edge into the graph
function addEdge(v, w) {
  adj[(v - 1)].push(w - 1);
  adj[(w - 1)].push(v - 1);
}
 
// find element in queue
function contains(q, n) {
  while (q.length) {
    if (q.shift() === n)
      return true;
  }
  return false;
}
 
function BFS(s) {
  // Mark all the vertices as not visited
  // (By default set as false)
  let visited = new Array(V).fill(false);
 
  // Create a queue for BFS
  let queue = [];
 
  // Mark the current node
  // as visited and enqueue it
  visited[s] = true;
 
  queue.push(s);
  let c = 0;
 
  // Max common nodes with given node
  let max = 0;
 
  let mostAppnode = 0;
  // To store common nodes
  let count = 0;
  while (queue.length !== 0) {
 
    // Dequeue a vertex from queue
    s = queue.shift();
    // Get all adjacent nodes
    // of the dequeued node
    // If a adjacent has
    // not been visited, then
    // mark it visited and enqueue it
    c++;
 
    let al2 = [];
    let i = 0;
 
    while (i < adj[s].length) {
      let n = adj[s][i];
      if (c === 1)
        al1.push(n);
      else
        al2.push(n);
 
      // If node is not
      // visited and also not
      // present in queue.
      if (!visited[n] && !contains(queue, n)) {
        visited[n] = true;
        queue.push(n);
      }
      i++;
    }
    if (al2.length !== 0) {
      for (let frnd of al2) {
        if (al1.includes(frnd))
          count++;
      }
      if (count > max) {
        max = count;
        mostAppnode = s;
      }
    }
  }
  if (max !== 0)
    return mostAppnode + 1;
  else
    return -1;
}
 
// Driver Code
let N = 4;
create_Graph(4);
 
addEdge(1, 2);
addEdge(1, 3);
addEdge(2, 3);
addEdge(3, 4);
addEdge(2, 4);
let K = 1;
console.log(BFS(K - 1));

Output

Time Complexity: O (V*V), BFS will take O(V+E) time but finding common elements between al1 and al2 will take O(V*V) time.

Auxiliary Space: O(V)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!