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.

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.

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)}.

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

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.

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:

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

Output:

2 0 0

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

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)

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.