给定V个顶点(城镇)和E条边(城镇之间的路线)。某公司决定建造仓库，以确保在X镇有一个仓库，或者在X镇附近有一个仓库。
如何找到公司必须建立的最小仓库数量。
示例:设V=10, E = 7，边对为:
1 2
2 4
2 5
3 6
8 6
9 7
10 7
这里的答案是3，因为它足以在2、6、9号镇建造仓库。
我的方法:
我首先计算每个城市的度，然后在度最大的城市放置一个仓库。然后我将所有邻近的城市标记为访问过的，然后移动到下一个未访问的最大节点，并在其上放置一个仓库。我一直这么做，直到没有人没来过。我的方法对吗?
你所需要做的就是形成一个图表，其中:
- 顶点是城镇
- 如果在对应的城镇之间有直接的路线，则在两个顶点之间存在一条边。
然后找到这个图的最小支配集。你应该在每个城镇建立一个仓库，对应于最小支配集中的顶点。
不幸的是，支配集问题是np完全的，所以很难找到确切的最小值，但是你的贪婪算法应该会给出一个很好的近似。