查找覆盖k条边的图的节点数

问题描述 投票:1回答:1

给出代表无向图的邻接表,我需要找到至少具有k条边的最小节点数。例如:我的邻接列表是调整[1] = 2、3、4adj [2] = 1,5,6adj [3] = 1,7adj [4] = 1,8,9调整[5] = 2、6调整[7] = 3adj [8] = 4,91个/ || \2 3 3/ / \5-6 6 7 8 8-9如果k = 6,则解为2。节点2、4总共有6条边。请注意,节点1、2不是解决方案,因为总边为5,边1-2仅计一次。

给出代表无向图的邻接表,我需要找到至少具有k条边的最小节点数。例如:我的邻接列表是adj [1] = 2,3,4 adj [2] = 1,5,6 adj [3] ...

algorithm
1个回答
0
投票

您可以遍历图形并收集每个节点的边数。创建矢量/地图:

© www.soinside.com 2019 - 2024. All rights reserved.