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)}.
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;
}
You can also try this code with Online C++ Compiler
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
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
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.