Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
🙋Introduction
2.
📈Graph Terminologies
2.1.
Graph
2.2.
Undirected Graphs
2.3.
Directed Graphs
2.4.
Degree 
3.
K-cores of a Graph
4.
📃Problem Statement
5.
🚶Approach/Algorithm to the solution.
6.
📍Implementation in C++
7.
Input Snapshot📸
8.
Output Snapshot📸
9.
📍Implementation in Java
10.
Time Complexity⏳
11.
Space Complexity
12.
Frequently Asked Questions
12.1.
What data structures do we use to represent graphs?
12.2.
What are the types of degrees in a directed graph?
12.3.
What do you mean by k-core subgraph?
12.4.
Give an example where a graph is used.
13.
Conclusion
Last Updated: Mar 27, 2024
Hard

Find k-cores of an Undirected Graph

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

🙋Introduction

Hello Readers!!! we have come up with yet another article. Most of you must have heard about graphs that is a non-linear data structure. It's one of those data-structures from which you can expect at least one question in online assessments and interviews. This article will familiarise you with graph data structure and then move on to implementing code to find the k-cores of an undirected graph. But before we begin, let us know some terminologies related to graphs.

📈Graph Terminologies

Graph

graph is a non-linear data structure. It has nodes or vertices which are connected through links which are called edges

graph

The above graph has five vertices and five edges. 1,2,3,4,5 are the vertices, and the black lines connecting these vertices are edges.

Read also: Application of graph data structure

Undirected Graphs

An undirected graph is one in which the links that are the edges that connect two vertices do not have a direction.

The above graph shown is undirected. If there's an edge between two vertices in an undirected graph, it means the edge can be traversed in two ways.

Want to know more? Check out Detect cycle in an undirected graph

Directed Graphs

A directed graph has edges with a direction. In directed graphs, an edge can be traversed in only one way.

directed graph

The above diagram shows a directed graph in which the edges have a direction. For example, the edge between vertex one and vertex two can be traversed only from 1 to 2 and not from 2 to 1.

Degree 

The degree of a vertex is the number of adjacent vertices to a vertex; in simple language, it is the number of edges connecting the vertex to other vertices. Now let us move on to understand the k cores of a graph.

Get the tech career you deserve, faster!
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

K-cores of a Graph

By k-cores of a graph, we mean the vertices (connected) present after removing all the vertices from the original graph having a degree less than k.

📃Problem Statement

We are given an undirected graph. We need to find the k-cores of the graph after removing the vertices with a degree less than k.

Say, we are given the following graph:

input graph

In the input, we have  the number of vertices in the graph, the number of edges, all the edges of the graph, and the value of k.

 

The output for the given graph is the vertices that are left after removing the vertices that had a degree less than k.

The output graph for the given example is shown below:

output graph

🚶Approach/Algorithm to the solution.

  1. We start with adding edges to the graph.
     
  2. Maintain an adjacency list for each vertex.
     
  3. While the vertex is being removed or the degree of the vertices are getting changed-

    1. Get the degree for the vertex i,
       
    2. Compare the degree of the vertex i, with k.

      1. If the degree is less than k, reduce the degree of the vertex by 1 and move to the next adjacent node(vertex).  
         
    3. Repeat this process for all the adjacent vertices of the particular vertex.
       
    4. After the degree of all the vertices has been reduced by 1 set the degree for the vertex to 0.
       
  4. Check for all the vertices again if their degree is less than or equal to 0;

    1. if it is the case remove that vertex and proceed to the next one to check the same.
       
  5. Print the k-cores.

📍Implementation in C++

Below is the implementation of code in C++ for finding k-cores of a graph:

cpp
#include <iostream>
using namespace std;
class AdjListVertex
{
 public:
   int v;
 AdjListVertex * next;
 AdjListVertex(int v)
 {
   this -> v = v;
   this -> next = NULL;
 }
};
class GraphVertex
{
 public:
   int data;
 AdjListVertex * edge;
};
// This class will construct the graph
class Graph
{
 public:
   //number of nodes in a graph
   int size;
 GraphVertex * node;
 Graph(int size)
 {
   if (size < 0)
   {
     cout << "\n Invalid number of vertices " << size << " \n";
   } else
   {
     this -> size = size;
     this -> node = new GraphVertex[this -> size];
     int i = 0;
     while (i < this -> size)
     {
       this -> node[i].data = i;
       this -> node[i].edge = NULL;
       i++;
     }
   }
 }
 //  Function to connect the edges between the vertices x and y
 void connect_Edge(int x, int y)
 {
   if (this -> size <= 0)
   {
     cout << "\n Graph is empty!\n";
     return;
   }
   //   Create Adjacency list
   AdjListVertex * newEdge = new AdjListVertex(y);
   if (newEdge != NULL)
   {
     //   Get the first edge of x vertex
     AdjListVertex * edge = this -> node[x].edge;
     //  if there's no edge between x and any other vertices add the first
     //edge
     if (edge == NULL)
     {
       this -> node[x].edge = newEdge;
     } else
     {
       //  Find the last vertex which has an edge with the current
       //vertex
       while (edge -> next != NULL)
       {
         edge = edge -> next;
       }
       //   Add edge at last position
       edge -> next = newEdge;
     }
   } else
   {
     cout << "\nCannot connect edges.\n";
   }
 }
 //   It adds an edge between x and y
 void add_Edge(int x, int y)
 {
   if (this -> size > 0 && x < this -> size && y < this -> size)
   {
     this -> connect_Edge(x, y);
     if (x == y)
     {
       return;
     }
     this -> connect_Edge(y, x);
   } else
   {
     cout << "Invalid number of vertices " << x << " " << y;
   }
 }
 //  Display Adjacency list of each vertex
 void display_Graph()
 {
   if (this -> size > 0)
   {
     AdjListVertex * temp = NULL;
     int i = 0;
     while (i < this -> size)
     {
       cout << "\n Adjacency list of vertex " << i << "->";
       //   Get first edge of ith node
       temp = this -> node[i].edge;
       while (temp != NULL)
       {
         cout << "  " << this -> node[temp -> v].data;
         temp = temp -> next;
       }
       i++;
     }
   } else
   {
     cout << "Empty Graph Node";
   }
 }
 //  To find the degree of each vertex
 void vertex_degree(int degree[])
 {
   if (this -> size <= 0)
   {
     return;
   }
   AdjListVertex * temp = NULL;
   int i = 0;
   while (i < this -> size)
   {
     degree[i] = 0;
     i++;
   }
   i = 0;
   while (i < this -> size)
   {
     //   Get first edge of ith vertex
     temp = this -> node[i].edge;
     while (temp != NULL)
     {
       degree[temp -> v]++;
       // move to the next node
       temp = temp -> next;
     }
     ++i;
   }
 }
 //   Function to find and remove vertices having degrees less than
 void kCores(int k)
 {
   if (k <= 0 || this -> size <= 0)
   {
     cout << "\nGraph is empty or " << k << " core Not valid\n";
   } else
   {
     int degree[this -> size];
     //   Loop controlling variable
     int i = 0;
     this -> vertex_degree(degree);
     AdjListVertex * edge = NULL, * temp1 = NULL, * temp2 = NULL;
     bool flag = true;
     while (flag == true)
     {
       flag = false;
       i = 0;
       while (i < this -> size)
       {
         if (degree[i] > 0 && degree[i] < k)
         {
           edge = this -> node[i].edge;
           this -> node[i].edge = NULL;
           while (edge != NULL)
           {
             temp1 = edge;
             degree[edge -> v]--;
             edge = edge -> next;
             //  remove edge
             temp1 = NULL;
           }
           degree[i] = 0;
           flag = true;
         }
         ++i;
       }
     }
     // Since removing a vertex will change the degree of all its adjacent
     //vertices check again for all the adjacent vertices
     i = 0;
     while (i < this -> size)
     {
       edge = this -> node[i].edge;
       temp1 = NULL;
       while (edge != NULL)
       {
         if (degree[edge -> v] <= 0)
         {
           if (this -> node[i].edge == edge)
           {
             this -> node[i].edge = edge -> next;
           } else
           {
             temp1 -> next = edge -> next;
           }
           temp2 = edge;
           edge = edge -> next;
           //  remove edge
           temp2 = NULL;
         } else
         {
           temp1 = edge;
           //   visit to next edge
           edge = edge -> next;
         }
       }
       ++i;
     }
     cout << "\n";
   }
 }
};
int main()
{
 	cout << "Enter the number of vertices\n";
 	int n, e, k;
 	cin >> n;
 	int a, b;
 	Graph g1 = Graph(n);
 	cout << "Enter the number of edges\n";
 	cin >> e;
 	//  Connected two node with Edges
 	cout << "Enter the edges to be added by entering the two connected vertices separated by spaces\n";
 	for (int i = 0; i < e; i++)
 	{
   	cin >> a >> b;
   	g1.add_Edge(a, b);
 	}
 	cout << "Enter the value of 'k':\n";
 	cin >> k;
 	g1.kCores(k);
 	cout << "\n The k cores of the graph are: \n";
 	g1.display_Graph();
 	return 0;
 }

 

Input Snapshot📸

output

Output Snapshot📸

output

 

📍Implementation in Java

Below is the implementation of code in Java for finding k-cores of a graph:

 

java
import java.util.*;
class AdjListVertex
{
   public int v;
   public AdjListVertex next;
   public AdjListVertex(int v)
   {
       this.v = v;
       this.next = null;
   }
}

class GraphVertex
{


   public int data;
   public AdjListVertex edge;
   public GraphVertex(int data)
   {
       this.data = data;
       this.edge = null;
   }
}

public class Graph
{
   public int size;
   public GraphVertex[] node;
   public graph(int size)
   {
       if (size < 0)
       {
           System.out.println("Invalid number of vertices");
       } else
       {
           this.size = size;
           this.node = new GraphVertex[this.size];
           int i = 0;


           for (i = 0; i < this.size; i++)
           {
               this.node[i] = new GraphVertex(i);
           }
       }
   }

   public void connect_Edge(int x, int y)
   {
       if (this.size <= 0)
       {
           System.out.println("Graph is empty");
           return;
       }


       AdjListVertex newEdge = new AdjListVertex(y);
       if (newEdge != null)
       {
           AdjListVertex edge = this.node[x].edge;
           if (edge == null)
           {
               this.node[x].edge = newEdge;
           } else
           {
               while (edge.next != null)
               {
                   edge = edge.next;
               }
               edge.next = newEdge;
           }
       } else
       {
           System.out.println("Cannot connect edges");
       }
   }
   public void add_Edge(int x, int y)
   {
       if (this.size > 0 && x < this.size && y < this.size)
       {
           connect_Edge(x, y);
           if (x == y)
           {
               return;
           }
           connect_Edge(y, x);
       } else
       {
           System.out.print("Invalid Node Vertices " + x + " " + y);
       }
   }
   public void display_Graph()
   {
       if (this.size > 0)
       {
           AdjListVertex temp = null;
           int i = 0;
           for (i = 0; i < this.size; i++)
           {
               System.out.print("\n Adjacency list of vertex " + i + " ->");
               temp = this.node[i].edge;
               while (temp != null)
               {
                   System.out.print("  " + this.node[temp.v].data);
                   temp = temp.next;
               }
           }
       } else
       {
           System.out.print("Empty Graph Node");
       }
   }
   public void findDegree(int[] indegree)
   {
       if (this.size <= 0)
       {
           return;
       }
       AdjListVertex temp = null;
       int i = 0;
       for (i = 0; i < this.size; ++i)
       {
           indegree[i] = 0;
       }
       for (i = 0; i < this.size; ++i)
       {
           temp = this.node[i].edge;
           while (temp != null)
           {
               indegree[temp.v]++;
               temp = temp.next;
           }
       }
   }
   public void kCores(int k)
   {
       if (k <= 0 || this.size <= 0)
       {
           System.out.print("\nGraph is empty or core Not valid\n");
       } else
       {
           int degree[] = new int[this.size];
           int i = 0;
           findDegree(degree);
           AdjListVertex edge = null, temp1 = null, temp2 = null;
           boolean flag = true;
           while (flag == true)
           {
               flag = false;
               for (i = 0; i < this.size; ++i)
               {
                   if (degree[i] > 0 && degree[i] < k)
                   {
                       edge = this.node[i].edge;
                       this.node[i].edge = null;
                       while (edge != null)
                       {
                           temp1 = edge;
                           degree[edge.v]--;
                           edge = edge.next;
                           temp1 = null;
                       }
                       degree[i] = 0;
                       flag = true;
                   }
               }
           }
           for (i = 0; i < this.size; ++i)
           {
               edge = this.node[i].edge;
               temp1 = null;
               while (edge != null)
               {
                   if (degree[edge.v] <= 0)
                   {
                       if (this.node[i].edge == edge)
                       {
                           this.node[i].edge = edge.next;
                       } else
                       {
                           temp1.next = edge.next;
                       }
                       temp2 = edge;
                       edge = edge.next;
                       temp2 = null;
                   } else
                   {
                       temp1 = edge;
                       edge = edge.next;
                   }
               }
           }
           System.out.println();
       }
   }
   public static void main(String[] args)
   {
       System.out.println("Enter the number of vertices\n");
              
       int n, e, k;
              
       Scanner sc = new Scanner(System.in);
              
       n = sc.nextInt();
              
       int x, y;
       Graph g1 = new Graph(n);

              
       System.out.println("Enter the number of edges\n");
              
       e = sc.nextInt();


              
       System.out.println("Enter the edges to be added by entering the two connected vertices separated by spaces\n");
              
       for (int i = 0; i < e; i++)
               {
                      
           x = sc.nextInt();
                      
           y = sc.nextInt();
                      
           g1.add_Edge(x, y);
                  
       }      
       System.out.println("Enter the value of 'k':");
              
       k = sc.nextInt();
       g1.kCores(k);
       System.out.println("The k cores of the graph are: ");
       g1.display_Graph();

   }
}

Time Complexity⏳

Time complexity for an algorithm is the amount of time it takes to process an input of some length. The time complexity for the given code is O(V+E), where 'V' represents the number of vertices present in the graph and 'E' is the number of edges present in the graph.

Since we are traversing the graph the time complexity here is O(V+E)

Space Complexity

Consecutively, for this code the space complexity will be O(V), where 'V' represents the number of vertices present in the graph  
Check out this problem - No of Spanning Trees in a Graph

Frequently Asked Questions

What data structures do we use to represent graphs?

We represent graphs by edges and vertices, so we can use either a list Adjacency List or a matrix Adjacency Matrix to store the input for a graph. 

What are the types of degrees in a directed graph?

There are two types of degrees in a directed graph: Indegree, the number of edges coming to a vertex, and Outdegree, the number of edges leaving a vertex.

What do you mean by k-core subgraph?

A k-core subgraph is a graph in which all the vertices have at least k degrees.

Give an example where a graph is used.

To allocate a resource operating system uses Resource Allocation Graph. 

Conclusion

This article made us aware about what are the k cores of an undirected graph and also implemented the code to find the same. Check out other graph problems such as finding all the mother vertices of the graphbreadth-first search, DFS Algorithm, and more. Also, look at major graph algorithms like Dijkstra's AlgorithmBellman Ford Algorithm, and Floyd Warshall Algorithm. Wait, we have got more than just graphs. Wanna learn more about web technologies? Why not have a look at web technologies on Coding Ninjas Studio? Practice data structures and algorithmsinterview questionsDBMScomputer networks, and operating systems to crack the interviews of big tech giants. Explore other fields like machine learningdeep learningcomputer vision, and big data. Also, check out Interview Experiences for different companies.

Happy Learning!

Live masterclass