Print nodes having maximum and minimum degrees

Last Updated : 08 Feb, 2023

Given an undirected graph having N nodes, the task is to print the nodes having minimum and maximum degree.
Examples:

Input:
1-----2
|     |
3-----4
Output:
Nodes with maximum degree : 1 2 3 4 
Nodes with minimum degree : 1 2 3 4 
Every node has a degree of 2.

Input:
    1
   / \
  2   3
 /
4
Output:
Nodes with maximum degree : 1 2 
Nodes with minimum degree : 3 4

Approach: For an undirected graph, the degree of a node is the number of edges incident to it, so the degree of each node can be calculated by counting its frequency in the list of edges. Hence the approach is to use a map to calculate the frequency of every vertex from the edge list and use the map to find the nodes having maximum and minimum degrees.
Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the nodes having
// maximum and minimum degree
void minMax(int edges[][2], int len, int n)
{
 
    // Map to store the degrees of every node
    map<int, int> m;
 
    for (int i = 0; i < len; i++) {
 
        // Storing the degree for each node
        m[edges[i][0]]++;
        m[edges[i][1]]++;
    }
 
    // maxi and mini variables to store
    // the maximum and minimum degree
    int maxi = 0;
    int mini = n;
 
    for (int i = 1; i <= n; i++) {
        maxi = max(maxi, m[i]);
        mini = min(mini, m[i]);
    }
 
    // Printing all the nodes with maximum degree
    cout << "Nodes with maximum degree : ";
    for (int i = 1; i <= n; i++) {
        if (m[i] == maxi)
            cout << i << " ";
    }
    cout << endl;
 
    // Printing all the nodes with minimum degree
    cout << "Nodes with minimum degree : ";
    for (int i = 1; i <= n; i++) {
        if (m[i] == mini)
            cout << i << " ";
    }
}
 
// Driver code
int main()
{
 
    // Count of nodes and edges
    int n = 4, m = 6;
 
    // The edge list
    int edges[][2] = { { 1, 2 },
                       { 1, 3 },
                       { 1, 4 },
                       { 2, 3 },
                       { 2, 4 },
                       { 3, 4 } };
 
    minMax(edges, m, 4);
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class GFG 
{
 
// Function to print the nodes having
// maximum and minimum degree
static void minMax(int edges[][], int len, int n)
{
 
    // Map to store the degrees of every node
    HashMap<Integer,
            Integer> m = new HashMap<Integer,
                                     Integer>();
 
    for (int i = 0; i < len; i++) 
    {
 
        // Storing the degree for each node
        if(m.containsKey(edges[i][0]))
        {
            m.put(edges[i][0], m.get(edges[i][0]) + 1);
        }
        else
        {
            m.put(edges[i][0], 1);
        }
        if(m.containsKey(edges[i][1]))
        {
            m.put(edges[i][1], m.get(edges[i][1]) + 1);
        }
        else
        {
            m.put(edges[i][1], 1);
        }
    }
 
    // maxi and mini variables to store
    // the maximum and minimum degree
    int maxi = 0;
    int mini = n;
 
    for (int i = 1; i <= n; i++) 
    {
        maxi = Math.max(maxi, m.get(i));
        mini = Math.min(mini, m.get(i));
    }
 
    // Printing all the nodes with maximum degree
    System.out.print("Nodes with maximum degree : ");
    for (int i = 1; i <= n; i++) 
    {
        if (m.get(i) == maxi)
            System.out.print(i + " ");
    }
    System.out.println();
 
    // Printing all the nodes with minimum degree
    System.out.print("Nodes with minimum degree : ");
    for (int i = 1; i <= n; i++)
    {
        if (m.get(i) == mini)
            System.out.print(i + " ");
    }
}
 
// Driver code
public static void main(String[] args)
{
    // Count of nodes and edges
    int n = 4, m = 6;
 
    // The edge list
    int edges[][] = {{ 1, 2 }, { 1, 3 },
                     { 1, 4 }, { 2, 3 },
                     { 2, 4 }, { 3, 4 }};
 
    minMax(edges, m, 4);
}
}
 
// This code is contributed by PrinciRaj1992

Python3

# Python3 implementation of the approach
 
# Function to print the nodes having 
# maximum and minimum degree 
def minMax(edges, leng, n) : 
 
    # Map to store the degrees of every node 
    m = {};
     
    for i in range(leng) :
        m[edges[i][0]] = 0;
        m[edges[i][1]] = 0;
         
    for i in range(leng) :
         
        # Storing the degree for each node
        m[edges[i][0]] += 1;
        m[edges[i][1]] += 1; 
 
    # maxi and mini variables to store 
    # the maximum and minimum degree 
    maxi = 0; 
    mini = n; 
 
    for i in range(1, n + 1) :
        maxi = max(maxi, m[i]); 
        mini = min(mini, m[i]); 
 
    # Printing all the nodes 
    # with maximum degree 
    print("Nodes with maximum degree : ", 
                                end = "")
     
    for i in range(1, n + 1) :
        if (m[i] == maxi) :
            print(i, end = " "); 
 
    print()
 
    # Printing all the nodes 
    # with minimum degree 
    print("Nodes with minimum degree : ", 
                                end = "")
     
    for i in range(1, n + 1) :
        if (m[i] == mini) :
            print(i, end = " "); 
 
# Driver code 
if __name__ == "__main__" : 
 
    # Count of nodes and edges 
    n = 4; m = 6; 
 
    # The edge list 
    edges = [[ 1, 2 ], [ 1, 3 ], 
             [ 1, 4 ], [ 2, 3 ], 
             [ 2, 4 ], [ 3, 4 ]]; 
 
    minMax(edges, m, 4); 
 
# This code is contributed by AnkitRai01

C#

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG 
{
 
// Function to print the nodes having
// maximum and minimum degree
static void minMax(int [,]edges, int len, int n)
{
 
    // Map to store the degrees of every node
    Dictionary<int, int> m = new Dictionary<int, int>();
 
    for (int i = 0; i < len; i++) 
    {
 
        // Storing the degree for each node
        if(m.ContainsKey(edges[i, 0]))
        {
            m[edges[i, 0]] = m[edges[i, 0]] + 1;
        }
        else
        {
            m.Add(edges[i, 0], 1);
        }
        if(m.ContainsKey(edges[i, 1]))
        {
            m[edges[i, 1]] = m[edges[i, 1]] + 1;
        }
        else
        {
            m.Add(edges[i, 1], 1);
        }
    }
 
    // maxi and mini variables to store
    // the maximum and minimum degree
    int maxi = 0;
    int mini = n;
 
    for (int i = 1; i <= n; i++) 
    {
        maxi = Math.Max(maxi, m[i]);
        mini = Math.Min(mini, m[i]);
    }
 
    // Printing all the nodes with maximum degree
    Console.Write("Nodes with maximum degree : ");
    for (int i = 1; i <= n; i++) 
    {
        if (m[i] == maxi)
            Console.Write(i + " ");
    }
    Console.WriteLine();
 
    // Printing all the nodes with minimum degree
    Console.Write("Nodes with minimum degree : ");
    for (int i = 1; i <= n; i++)
    {
        if (m[i] == mini)
            Console.Write(i + " ");
    }
}
 
// Driver code
public static void Main(String[] args)
{
    // Count of nodes and edges
    int m = 6;
 
    // The edge list
    int [,]edges = {{ 1, 2 }, { 1, 3 },
                    { 1, 4 }, { 2, 3 },
                    { 2, 4 }, { 3, 4 }};
 
    minMax(edges, m, 4);
}
}
 
// This code is contributed by 29AjayKumar

Javascript

// JavaScript implementation of the approach
 
// Function to print the nodes having
// maximum and minimum degree
function minMax(edges, len, n) {
    // Map to store the degrees of every node
    let m = new Map();
 
    for (let i = 0; i < len; i++) {
        // Storing the degree for each node
        if (m.has(edges[i][0])) {
            m.set(edges[i][0], m.get(edges[i][0]) + 1);
        } else {
            m.set(edges[i][0], 1);
        }
        if (m.has(edges[i][1])) {
            m.set(edges[i][1], m.get(edges[i][1]) + 1);
        } else {
            m.set(edges[i][1], 1);
        }
    }
 
    // maxi and mini variables to store
    // the maximum and minimum degree
    let maxi = 0;
    let mini = n;
 
    for (let i = 1; i <= n; i++) {
        maxi = Math.max(maxi, m.get(i));
        mini = Math.min(mini, m.get(i));
    }
 
    // Printing all the nodes with maximum degree
    console.log("Nodes with maximum degree : ", end = " ");
    for (let i = 1; i <= n; i++) {
        if (m.get(i) === maxi) {
            console.log(i + " ");
        }
    }
    console.log();
 
    // Printing all the nodes with minimum degree
    console.log("Nodes with minimum degree : ", end = " ");
    for (let i = 1; i <= n; i++) {
        if (m.get(i) === mini) {
            console.log(i + " ");
        }
    }
}
 
// Driver code
let n = 4, m = 6;
 
// The edge list
let edges = [
    [1, 2],
    [1, 3],
    [1, 4],
    [2, 3],
    [2, 4],
    [3, 4]
];
 
minMax(edges, m, 4);

Output:

Nodes with maximum degree : 1 2 3 4 
Nodes with minimum degree : 1 2 3 4

Time Complexity: O(M*logN + N).
Auxiliary Space: O(N).

Maximum and Minimum Values of an Algebraic Expression

DiptayanBiswas

Improve

Print nodes having maximum and minimum degrees

C++

Java

Python3

C#

Javascript

Similar Reads

What kind of Experience do you want to share?