Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Graph📝
3.
Adjancency💥
4.
Problem Statement
5.
Example
6.
Approach🎯
7.
Solution
8.
Frequently Asked Questions
8.1.
What is an adjacent node in the graph?
8.2.
What is a weighted graph in graph theory?
8.3.
What is the Weight of a node in a graph?
8.4.
How do you calculate the shortest path in a weighted graph?
8.5.
Why are graphs important data structures?
9.
Conclusion
Last Updated: Mar 27, 2024
Medium

k’th Heaviest Adjacent Node in a Graph where Each Vertex has Weight

Author yuvatimankar
0 upvote

Introduction

In this blog, we will cover what graphs are, adjacent nodes in a graph, Vertex, Weight, and how to find k'th heaviest adjacent node in a graph where each Vertex has Weight.

K'th heaviest adjacent node in a graph

Now, Let's start with the topics!

Graph📝

A Graph is a non-linear Data Structure that contains two non-empty sets of vertices and edges. 

Term Definition
Vertex Vertex is defined as one of the points on which a graph is defined.
Weight The Weight in the graph data structure is defined as the "cost" of an edge.

Applications of a Graph🎯

Graphs are used in Google maps.

✳ Graphs are used in social networking.

✳ Graphs are used in operating systems.

Graph

In the above graph, set of vertices are V={1,2,3,4,5} and set of degree are E={(1,2),(2,3),(3,4),(5,3),(4,5)}.

Read also: Application of graph data structure

Adjancency💥

In a graph, two nodes are said to be adjacent if there is an edge between the two nodes. The Adjacency here of nodes is maintained by the single edge connecting those two nodes.

Adjacent graph

In the above graph, 'a' and 'b' are adjacent nodes, with a common edge 'ab' present between them.

Problem Statement

We have given a positive number k and an undirected graph of N nodes, numbered from 0 to N-1, each having some weight. For every node, if we sort the nodes according to their weights, which are directly connected(in decreasing order), then what will be the position of k’th heaviest Adjacent node in a Graph.

We have to print the kth node number for every node, and if the node number does not exist, print -1.

Example

Input: N=3, k=2, w[ ] = {2, 4, 3}.

edge 1: { a , c }

edge 2: { a , b }

edge 3: { b , c }

Output: c a a

Graph:

Example graph

Explanation:

  • For node a, the sorted decreasing order nodes according to weights are node b(w = 4), node c (w = 3). The node at the second position for node a is node b.
     
  • For node b, the sorted decreasing order nodes according to weights are node c (w = 3), node a (w = 2). The node at the second position for node b is node a.
     
  • For node c, the sorted decreasing order nodes according to weights are node b(w =4), node a (w = 2). The node at the second position for node c is node a.


Therefore, the k’th heaviest Adjacent node in a Graph is c a a. 

Approach🎯

The motive is to sort the Adjacency list of every node based on their weights.

🔥 First, we are required to create Adjacency List for all the nodes in a graph. Now, for every node, the nodes directly connected to it are stored in a list. In the adjacency list, keep the nodes along with their weights.

🔥 Now, for every node, sort the nodes in the decreasing order based on their weights, and then print the node number, which is present at the k'th position.

Solution

💥C++

#include<bits/stdc++.h>
using namespace std;
 
/* Print Kth node number for each node after sorting
 connected node according to their weight. */
void printkthNodePosition(vector< pair<int, int> > adj[],
                        int w[], int n, int k)
{
    /* Sort Adjacency List of all node on the basis
     of its weight. */
    for (int i = 0; i < n; i++)
      sort(adj[i].begin(), adj[i].end());
 
    /* Printing Kth node for each node. */
    for (int i = 0; i < n; i++)
    {
        if (adj[i].size() >= k)
          cout << adj[i][adj[i].size() - k].second;
        else
          cout << "-1";
    }
}
 
/* Driven Program */
int main()
{
    int n = 3, k = 2;
    int w[] = { 2, 4, 3 };
 
    /* Making adjacency list, storing the nodes
     along with their weight. */
    vector< pair<int, int> > adj[n+1];
 
    adj[0].push_back(make_pair(w[2], 2));
    adj[2].push_back(make_pair(w[0], 0));
 
    adj[0].push_back(make_pair(w[1], 1));
    adj[1].push_back(make_pair(w[0], 0));
 
    adj[1].push_back(make_pair(w[2], 2));
    adj[2].push_back(make_pair(w[1], 1));
 
    printkthNodePosition(adj, w, n, k);
    return 0;
}
You can also try this code with Online C++ Compiler
Run Code


Output:

2 0 0
You can also try this code with Online C++ Compiler
Run Code

 

Time Complexity: nlogn

Space Complexity: O(n)


💥Java

import java.util.*;
class Ninjas
{
    /* pair class */
    static class pair
    {
        int first, second;
 
        pair(int a, int b)
        {
            first = a;
            second = b;
        }
    }
 
    /* Print Kth node number for each node after sorting
    connected node according to their weight. */
    static void printkthNodePosition(Vector<pair> adj[], int wt[], int n, int k)
    {
        /* Sort Adjacency List of all node on the basis
         of its weight. */
        for (int i = 0; i < n; i++)
            Collections.sort(adj[i], new Comparator<pair>()
            {
                public int compare(pair p1, pair p2)
                {
                    return p1.first - p2.first;
                }
            });
 
        /* Printing Kth node for each node. */
        for (int i = 0; i < n; i++)
        {
            if (adj[i].size() >= k)
                System.out.print(adj[i].get(adj[i].size() -
                                            k).second + " ");
            else
                System.out.print("-1");
        }
    }
 
    /* Driven Program */
    public static void main(String[] args)
    {
        int n = 3, k = 2;
        int w[] = { 2, 4, 3 };
 
  
        Vector<pair>[] adj = new Vector[n + 1];
        for (int i = 0; i < n + 1; i++)
	        /* loop */
            adj[i] = new Vector<pair>();
 
        adj[0].add(new pair(w[2], 2));
        adj[2].add(new pair(w[0], 0));
 
        adj[0].add(new pair(w[1], 1));
        adj[1].add(new pair(w[0], 0));
 
        adj[1].add(new pair(w[2], 2));
        adj[2].add(new pair(w[1], 1));
 
        printkthNodePosition(adj, w, n, k);
    }
}
You can also try this code with Online Java Compiler
Run Code


Output:

2 0 0

 

Time Complexity: nlogn

Space Complexity: O(n)


💥 Python

def printkthNodePosition(adj, w, n, k):
     
    # Sort Adjacency List of all
    # node on the basis of its weight.
    for i in range(n):
        adj[i].sort()
 
    # Printing Kth node for each node.
    for i in range(n):
        if (len(adj[i]) >= k):
            print(adj[i][len(adj[i]) -
                             k][1], end = " ")
        else:
            print("-1", end = " ")
 
# Driver Code
if __name__ == '__main__':
 
    n = 3
    k = 2
    w = [2, 4, 3]
 
    adj = [[] for i in range(n + 1)]
 
    adj[0].append([w[2], 2])
    adj[2].append([w[0], 0])
 
    adj[0].append([w[1], 1])
    adj[1].append([w[0], 0])
 
    adj[1].append([w[2], 2])
    adj[2].append([w[1], 1])
 
    printkthNodePosition(adj, w, n, k)
 
You can also try this code with Online Python Compiler
Run Code


Output:

2 0 0

 

Time Complexity: nlogn

Space Complexity: O(n)

Frequently Asked Questions

What is an adjacent node in the graph?

An adjacent node in a graph is any two nodes connected by one or more edges.

What is a weighted graph in graph theory?

A graph in which every branch has some numerical weight is known as a weighted graph.

What is the Weight of a node in a graph?

The sum of the weights of the edges directly connected to the node is called the Weight of a node.

How do you calculate the shortest path in a weighted graph?

We use Dijkstra's algorithm to calculate the shortest path in a weighted graph.

Why are graphs important data structures?

Because they can easily represent the relations between real-life data.

Conclusion

In this article, we have discussed finding k'th heaviest adjacent node in a graph where each Vertex has Weight. We started with defining terms such as Graph, Adjacency, Vertex, and Weight, and then we saw the problem statement, its approach, and designed the algorithm to find k'th heaviest adjacent node in a graph.  

😍Excited to learn more about Graphs? Check out the following mentioned artciles.


Recommended Problems - 

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive ProgrammingJavaScriptSystem Design, etc. Enroll in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations.

Happy learning, Ninja🥷

Live masterclass