Find k | C # program to find K - Cores of a graph ; This class represents a undirected graph using adjacency list representation ; No . of vertices ; Pointer to an array containing adjacency lists ; Function to add an edge to graph ; A recursive function to print DFS starting from v . It returns true if degree of v after processing is less than k else false It also updates degree of adjacent if degree of v is less than k . And if degree of a processed adjacent becomes less than k , then it reduces of degree of v also , ; Mark the current node as visited and print it ; Recur for all the vertices adjacent to this vertex ; Degree of v is less than k , then degree of adjacent must be reduced ; If adjacent is not processed , process it ; If degree of adjacent after processing becomes less than k , then reduce degree of v also . ; Return true if degree of v is less than k ; Prints k cores of an undirected graph ; INITIALIZATION Mark all the vertices as not visited and not processed . ; Store degrees of all vertices ; DFS traversal to update degrees of all vertices . ; PRINTING K CORES ; Only considering those vertices which have degree >= K after BFS ; Traverse adjacency list of v and print only those adjacent which have vDegree >= k after BFS . ; Driver Code ; Create a graph given in the above diagram
using System ; using System . Collections . Generic ; class GFG { public class Graph { int V ; List < int > [ ] adj ; public Graph ( int V ) { this . V = V ; this . adj = new List < int > [ V ] ; for ( int i = 0 ; i < V ; i ++ ) adj [ i ] = new List < int > ( ) ; } public void addEdge ( int u , int v ) { this . adj [ u ] . Add ( v ) ; this . adj [ v ] . Add ( u ) ; } bool DFSUtil ( int v , bool [ ] visited , int [ ] vDegree , int k ) { visited [ v ] = true ; foreach ( int i in adj [ v ] ) { if ( vDegree [ v ] < k ) vDegree [ i ] -- ; if ( ! visited [ i ] ) { DFSUtil ( i , visited , vDegree , k ) ; } } return ( vDegree [ v ] < k ) ; } public void printKCores ( int k ) { bool [ ] visited = new bool [ V ] ; bool [ ] processed = new bool [ V ] ; int mindeg = int . MaxValue ; int startvertex = 0 ; int [ ] vDegree = new int [ V ] ; for ( int i = 0 ; i < V ; i ++ ) { vDegree [ i ] = adj [ i ] . Count ; if ( vDegree [ i ] < mindeg ) { mindeg = vDegree [ i ] ; startvertex = i ; } } DFSUtil ( startvertex , visited , vDegree , k ) ; for ( int i = 0 ; i < V ; i ++ ) if ( ! visited [ i ] ) DFSUtil ( i , visited , vDegree , k ) ; Console . WriteLine ( " K - Cores ▁ : ▁ " ) ; for ( int v = 0 ; v < V ; v ++ ) { if ( vDegree [ v ] >= k ) { Console . Write ( " STRNEWLINE ▁ " + v ) ; foreach ( int i in adj [ v ] ) if ( vDegree [ i ] >= k ) Console . Write ( " ▁ - > ▁ " + i ) ; } } } } public static void Main ( String [ ] args ) { int k = 3 ; Graph g1 = new Graph ( 9 ) ; g1 . addEdge ( 0 , 1 ) ; g1 . addEdge ( 0 , 2 ) ; g1 . addEdge ( 1 , 2 ) ; g1 . addEdge ( 1 , 5 ) ; g1 . addEdge ( 2 , 3 ) ; g1 . addEdge ( 2 , 4 ) ; g1 . addEdge ( 2 , 5 ) ; g1 . addEdge ( 2 , 6 ) ; g1 . addEdge ( 3 , 4 ) ; g1 . addEdge ( 3 , 6 ) ; g1 . addEdge ( 3 , 7 ) ; g1 . addEdge ( 4 , 6 ) ; g1 . addEdge ( 4 , 7 ) ; g1 . addEdge ( 5 , 6 ) ; g1 . addEdge ( 5 , 8 ) ; g1 . addEdge ( 6 , 7 ) ; g1 . addEdge ( 6 , 8 ) ; g1 . printKCores ( k ) ; Console . WriteLine ( ) ; Graph g2 = new Graph ( 13 ) ; g2 . addEdge ( 0 , 1 ) ; g2 . addEdge ( 0 , 2 ) ; g2 . addEdge ( 0 , 3 ) ; g2 . addEdge ( 1 , 4 ) ; g2 . addEdge ( 1 , 5 ) ; g2 . addEdge ( 1 , 6 ) ; g2 . addEdge ( 2 , 7 ) ; g2 . addEdge ( 2 , 8 ) ; g2 . addEdge ( 2 , 9 ) ; g2 . addEdge ( 3 , 10 ) ; g2 . addEdge ( 3 , 11 ) ; g2 . addEdge ( 3 , 12 ) ; g2 . printKCores ( k ) ; } }