5 years ago (2015-11-15)  Algorithm language |   First to comment  29 
post score 0 times, average 0.0
[Slideup] Catalog


Given an arbitrary undirected graph, the graph is divided into several subsets. Any two nodes in the subset set are not connected. The greedy algorithm is used to minimize the number of subsets.

Algorithm steps or processes:


  • Construct a vector A to join by the size of the node.
  • Build vector B is empty, B stores the final result, its elements are subsets
  • Take the first element m of the vector A (that is, the largest degree) and add it to the vector B, and iterate over the elements in B. If m is not connected to the elements in the element (subset) of B, then join the current subset if it is connected. Create a new subset.
  • Remove m in vector A and reorder vector A according to size, repeat 3

The subset with the lowest number of undirected graphs and disjoint elements

C++ code



This article has been printed on copyright and is protected by copyright laws. It must not be reproduced without permission.If you need to reprint, please contact the author or visit the copyright to obtain the authorization. If you feel that this article is useful to you, you can click the "Sponsoring Author" below to call the author!

Reprinted Note Source: Baiyuan's Blog>>https://wangbaiyuan.cn/en/number-at-least-undirected-graph-elements-not-connected-subset-of-2.html

Post comment


No Comment


Forget password?