ronith
9/8/2018 - 9:53 AM

## Find k-cores of an undirected graph

Given a graph G and an integer K, K-cores of the graph are connected components that are left after all vertices of degree less than k have been removed.

``````#include <bits/stdc++.h>
using namespace std;

class graph {
int v;
public:
graph (int v) {
this->v = v;
}
void addEdge (int u, int w) {
}
void print();
void kCores (int k);
bool DFSUtil(int , vector <bool> &, vector <int> &, int );
};
void graph::print() {
for (int i=0;i<v; i++) {
cout<< i ;
list<int>::iterator j;
cout<< " - " << *j;
cout<< "\n";
}
}
bool graph::DFSUtil(int s, vector<bool> &visited, vector<int> &d, int k) {
visited[s] = 1;
list<int>::iterator i;
if (d[s]<k)
d[*i]--;
if (!visited[*i]) {
if (DFSUtil(*i, visited, d, k))
d[s]--;
}
}
return (d[s]<k);
}
void graph::kCores(int k) {
vector <bool> visited(v, false);
vector <int> d(v);
int mdeg = INT_MAX, s;
for (int i=0; i<v; i++) {
if (d[i]< mdeg) {
mdeg = d[i];
s = i;
}
}
DFSUtil(s, visited, d, k);

for (int i=0; i<v; i++)
if (!visited[i])
DFSUtil(i, visited, d, k);

for (int i=0; i<v;i++) {
if (d[i]>= k) {
cout<< i;
list<int>::iterator j;
if (d[*j]>= k)
cout<< " - "<< *j;
cout<< "\n";
}
}
}

int main() {
int k=3, v= 9;
graph g(v);