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

problem

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

Style

No Comment

登录

Forget password?

您也可以使用第三方帐号快捷登录

切换登录

注册

TW