## Monday, March 28, 2016

### Find k-cores of an undirected graph - GeeksforGeeks

Find k-cores of an undirected graph - GeeksforGeeks
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

The standard algorithm to find a k-core graph is to remove all the vertices that have degree less than- ‘K’ from the input graph. We must be careful that removing a vertex reduces the degree of all the vertices adjacent to it, hence the degree of adjacent vertices can also drop below-‘K’. And thus, we may have to remove those vertices also. This process may/may not go until there are no vertices left in the graph.
To implement above algorithm, we do a modified DFS on the input graph and delete all the vertices having degree less than ‘K’, then update degrees of all the adjacent vertices, and if their degree falls below ‘K’ we will delete them too.
Time complexity of the above solution is O(V + E) where V is number of vertices and E is number of edges.
Related Concepts :
Degeneracy : Degeneracy of a graph is the largest value k such that the graph has a k-core. For example, the above shown graph has a 3-Cores and doesn’t have 4 or higher cores. Therefore, above graph is 3-degenerate.
Degeneracy of a graph is used to measure how sparse graph is.
`// A recursive function to print DFS starting from v.`
`// It returns true of 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,`
`bool` `Graph::DFSUtil(``int` `v, vector<``bool``> &visited,`
`                    ``vector<``int``> &vDegree, ``int` `k)`
`{`
`    ``// Mark the current node as visited and print it`
`    ``visited[v] = ``true``;`

`    ``// Recur for all the vertices adjacent to this vertex`
`    ``list<``int``>::iterator i;`
`    ``for` `(i = adj[v].begin(); i != adj[v].end(); ++i)`
`    ``{`
`        ``// degree of v is less than k, then degree of adjacent`
`        ``// must be reduced`
`        ``if` `(vDegree[v] < k)`
`            ``vDegree[*i]--;`

`        ``// If adjacent is not processed, process it`
`        ``if` `(!visited[*i])`
`        ``{`
`            ``// If degree of adjacent after processing becomes`
`            ``// less than k, then reduce degree of v also.`
`            ``if` `(DFSUtil(*i, visited, vDegree, k))`
`                ``vDegree[v]--;`
`        ``}`
`    ``}`

`    ``// Return true if degree of v is less than k`
`    ``return` `(vDegree[v] < k);`
`}`

`// Prints k cores of an undirected graph`
`void` `Graph::printKCores(``int` `k)`
`{`
`    ``// INITIALIZATION`
`    ``// Mark all the vertices as not visited and not`
`    ``// processed.`
`    ``vector<``bool``> visited(V, ``false``);`
`    ``vector<``bool``> processed(V, ``false``);`

`    ``// Store degrees of all vertices`
`    ``vector<``int``> vDegree(V);`
`    ``for` `(``int` `i=0; i<V; i++)`
`        ``vDegree[i]  = adj[i].size();`

`    ``// DFS traversal to update degrees of all`
`    ``// vertices.`
`    ``for` `(``int` `i=0; i<V; i++)`
`        ``if` `(visited[i] == ``false``)`
`           ``DFSUtil(i, visited, vDegree, k);`

`    ``// PRINTING K CORES`
`    ``cout << ``"K-Cores : \n"``;`
`    ``for` `(``int` `v=0; v<V; v++)`
`    ``{`
`        ``// Only considering those vertices which have degree`
`        ``// >= K after BFS`
`        ``if` `(vDegree[v] >= k)`
`        ``{`
`            ``cout << ``"\n["` `<< v << ``"]"``;`

`            ``// Traverse adjacency list of v and print only`
`            ``// those adjacent which have vDegree >= k after`
`            ``// BFS.`
`            ``list<``int``>::iterator itr;`
`            ``for` `(itr = adj[v].begin(); itr != adj[v].end(); ++itr)`
`                ``if` `(vDegree[*itr] >= k)`
`                    ``cout << ``" -> "` `<< *itr;`
`        ``}`
`    ``}`
`}`

Read full article from Find k-cores of an undirected graph - GeeksforGeeks

## Labels

GeeksforGeeks (1109) LeetCode (1095) Review (846) Algorithm (795) to-do (633) LeetCode - Review (574) Classic Algorithm (324) Dynamic Programming (294) Classic Interview (288) Google Interview (242) Tree (145) POJ (139) Difficult Algorithm (132) LeetCode - Phone (127) EPI (125) Bit Algorithms (120) Different Solutions (120) Lintcode (113) Smart Algorithm (109) Math (108) HackerRank (89) Binary Search (83) Binary Tree (82) Graph Algorithm (76) Greedy Algorithm (73) DFS (71) Stack (65) Interview Corner (61) List (58) BFS (54) Codility (54) ComProGuide (52) Trie (49) USACO (46) Interval (45) LeetCode Hard (42) ACM-ICPC (41) Data Structure (40) Knapsack (40) Jobdu (39) Matrix (39) String Algorithm (38) Union-Find (37) Backtracking (36) Codeforces (36) Must Known (36) Sort (35) Array (33) Segment Tree (33) Sliding Window (33) prismoskills (33) HDU (31) Priority Queue (31) Google Code Jam (30) Permutation (30) Puzzles (30) Array O(N) (29) Company-Airbnb (29) Company-Zenefits (28) Palindrome (28) to-do-must (28) Graph (27) Random (27) GeeksQuiz (25) Logic Thinking (25) Pre-Sort (25) Time Complexity (25) hihocoder (25) Queue (24) Company-Facebook (23) High Frequency (23) TopCoder (23) Algorithm Game (22) Bisection Method (22) Hash (22) DFS + Review (21) Two Pointers (21) Brain Teaser (20) CareerCup (20) LeetCode - DP (20) Merge Sort (20) O(N) (20) Follow Up (19) UVA (19) Ordered Stack (18) Probabilities (18) Company-Uber (17) Game Theory (17) Topological Sort (17) Codercareer (16) Heap (16) Shortest Path (16) String Search (16) Tree Traversal (16) itint5 (16) Difficult (15) Iterator (15) BST (14) KMP (14) LeetCode - DFS (14) Number (14) Number Theory (14) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Euclidean GCD (13) Majority (13) Reverse Thinking (13) mitbbs (13) Combination (12) Modify Tree (12) Reconstruct Tree (12) 尺取法 (12) AOJ (11) DFS+Backtracking (11) Graph DFS (11) LCA (11) Miscs (11) Princeton (11) Proof (11) Rolling Hash (11) Tree DP (11) X Sum (11) 挑战程序设计竞赛 (11) Bisection (10) Bucket Sort (10) Coin Change (10) DFS+Cache (10) HackerRank Easy (10) O(1) Space (10) SPOJ (10) Theory (10) TreeMap (10) Tutorialhorizon (10) Mathblog (9) Max-Min Flow (9) Prefix Sum (9) Quick Sort (9) Simulation (9) Stock (9) Use XOR (9) Book Notes (8) Bottom-Up (8) DFS+BFS (8) Linked List (8) Prime (8) Suffix Tree (8) Tech-Queries (8) 穷竭搜索 (8) Expression (7) Game Nim (7) Graph BFS (7) Hackerearth (7) Inversion (7) Quick Select (7) Radix Sort (7) TreeSet (7) n00tc0d3r (7) 蓝桥杯 (7) DFS+DP (6) DP - Tree (6) Dijkstra (6) Dutch Flag (6) How To (6) Manacher (6) One Pass (6) Pruning (6) Rabin-Karp (6) Sampling (6) Schedule (6) Stream (6) Suffix Array (6) Threaded (6) Xpost (6) reddit (6) AI (5) Big Data (5) Brute Force (5) Code Kata (5) Coding (5) Convex Hull (5) Crazyforcode (5) Cycle (5) Find Rule (5) Graph Cycle (5) Immutability (5) Java (5) Maze (5) Pre-Sum (5) Quadtrees (5) Quora (5) Subarray Sum (5) Sudoku (5) Sweep Line (5) Word Search (5) jiuzhang (5) 单调栈 (5) 树形DP (5) 1point3acres (4) Abbreviation (4) Anagram (4) Anagrams (4) Chess Game (4) Distributed (4) Flood fill (4) Histogram (4) MST (4) MinMax (4) N Queens (4) Probability (4) Programcreek (4) Subset Sum (4) Subsets (4) Symbol Table (4) Triangle (4) Water Jug (4) algnotes (4) fgdsb (4) to-do-2 (4) 最大化最小值 (4) A Star (3) B Tree (3) Coins (3) Dedup (3) Dequeue (3) Dropbox (3) Easy (3) Github (3) GoLang (3) Joseph (3) Jump Game (3) K (3) LogN (3) Minesweeper (3) NP Hard (3) O(N) Hard (3) Parser (3) Rectangle (3) Scala (3) SegmentFault (3) Shuffle (3) Skyline (3) Subtree (3) Trie + DFS (3) Word Ladder (3) bookkeeping (3) codebytes (3) Array Merge (2) BOJ (2) Bellman Ford (2) Bit Counting (2) Bit Mask (2) Bloom Filter (2) Clock (2) Codesays (2) DP - DFS (2) DP-3D Table (2) DP-Classical (2) DP-i-k-j (2) DP-树形 (2) Factor (2) GoHired (2) Graham Scan (2) Huffman Tree (2) Invariant (2) Islands (2) Lucene-Solr (2) Matrix Power (2) Median (2) Parentheses (2) Peak (2) Programming (2) Robot (2) Rosettacode (2) Search (2) SimHash (2) Summary (2) TV (2) Tile (2) Tree Sum (2) Word Break (2) Word Graph (2) Word Trie (2) 剑指Offer (2) 数位DP (2) 1-X (1) 51Nod (1) Akka (1) BACK (1) BK-Tree (1) BZOJ (1) Basic (1) Bayes (1) Big Integer (1) Big Number (1) Binary (1) Bipartite (1) BitMap (1) BitMap index (1) BitSet (1) BuildIt (1) C/C++ (1) CC Interview (1) Cache (1) Chinese (1) Clean Code (1) Cloest (1) Clone (1) Code Quality (1) Company-Epic (1) Company-Yelp (1) Concise (1) Concurrency (1) Custom Sort (1) DFS-Matrix (1) DP-Difficult (1) DP-Graph (1) DP-MaxMin (1) Database (1) Diagonal (1) Domino (1) Dr Dobb's (1) Duplicate (1) FST (1) Fraction (1) Funny (1) Game (1) Generation (1) GeoHash (1) Google APAC (1) Gray Code (1) HOJ (1) Hanoi (1) How Hash (1) How to Test (1) Improve It (1) In Place (1) Interview (1) Isomorphic (1) JDK8 (1) Knight (1) Kruskal (1) Kth Element (1) Linkedin (1) Local MinMax (1) Matrix BFS (1) Matrix Graph (1) Matrix+DP (1) MinHash (1) MinMax Heap (1) Monto Carlo (1) Multiple DFS (1) Next Element (1) PAT (1) Parenthesis (1) Partition (1) Path Finding (1) Persistent (1) Power Set (1) PreProcess (1) Python (1) RSA (1) Ranking (1) Rddles (1) ReHash (1) Realtime (1) Region (1) Resources (1) Robin (1) Selection (1) Similarity (1) Square (1) String DP (1) SubMatrix (1) Subsequence (1) TSP (1) Test (1) Test Cases (1) Thread (1) TimSort (1) Top-Down (1) Tournament (1) Tree Rotate (1) Trie vs Hash (1) Triplet (1) Two Stacks (1) Two-End-BFS (1) UyHiP (1) Valid Tree (1) Vector (1) Wiggle Sort (1) Wikipedia (1) ZOJ (1) ZigZag (1) codevs (1) cos126 (1) javabeat (1) jum (1) sqrt(N) (1) 两次dijkstra (1) 九度 (1) 二进制枚举 (1) 夹逼法 (1) 归一化 (1) 折半枚举 (1) 枚举 (1) 状态压缩DP (1) 男人八题 (1) 英雄会 (1) 逆向思维 (1)