图的临界点：以最小的点数和权重到达所有节点
这是一个数据结构和算法课程的问题，所以我不是在寻找一个具体的或完整的答案，但我希望得到一些提示来帮助我了解我是否在正确的轨道上（或那些可以指出我在正确轨道上的提示）
给定一个位置的无向图，其中节点为位置，道路为边（以遍历某条道路需要多少时间加权），在最大权重为5的情况下，找到能到达所有节点的点*的最小数目。*点是图上的任何点。它们可以在边或节点上。从现在起我就叫他们临界点。
举个例子，如果我们有这张图：
Node2->Node1（重量7)->Node4(w1)->Node7(w8)
节点3->节点1(1)->节点4(2)->节点5(2)->节点6（2）
节点4->节点2（1）->节点3（2）->节点5（2）
节点7->节点6（5）->节点5（3）->节点2（8）
那么临界点将是：一个在节点1和2之间的边缘，节点1的权重为2，节点2的权重为5（注意它们的和必须仍然等于7，节点1到2的原始权重），第二个在节点7本身。第一个临界点在最大权重为5的情况下可以到达节点1到6。只有节点7在权重5中从该点起不可达，因此第二临界点在节点7本身上。因此，整个图可以从这2个权重为5（或更小）的临界点到达。
我的想法是：为每个鼻子保持一个布尔“完成”，表示从已经找到的临界点之一可以到达或不能到达。从某个节点开始。使用BFS并遍历该图。在未执行的节点上,执行以下操作：
这里的问题是有效性的证明。对于每个临界点（当使用最大的权重边时）有不止2个选项，我只是考虑2个。但另一方面，如果我考虑更多，我们进入复杂度的问题，而且算法已经不是太优化了。此外，我们可能需要在一个节点周围的边缘上放置一个以上的临界点。这个算法只放一个或一个都不放，然后继续前进，因为我假设放多个点可能比需要的多得多。
所以基本上，我不太确定从这里往哪走。任何帮助都是非常非常感谢的。
共有1个答案
下面来自我的头顶，欢迎大家在推理中找漏洞。
看起来你手边有套盖问题。即。给定一个集合覆盖问题的实例，就可以构建一个问题的实例，这样解决后一个问题也就解决了前一个问题。当然，集合覆盖问题是NP-完全的。
这是减幅。给定一个普适集U及其复盖所有U的子集的某些集S，构造一个仍复盖所有U的S的极小子集。
-
我在leetcode中遇到了一个名为“二叉树相机”的问题。 我在想如何处理这个类似的问题：- 你必须把摄像机放在一个图的节点上，这样整个图就被覆盖了。一个节点上的摄像机监视它的所有近邻节点和它自己。找到覆盖所有节点所需的最小摄像机数量。
-
我有一个场景 我想从一个特定的节点（比如ID:7）开始运行BFS 如果有无法从该节点访问的节点，我想重新启动BFS（使用任何剩余节点），直到访问图的所有顶点 到目前为止，我得到的是从节点0开始并用另一个未访问的顶点重新启动的代码（部分）： 如何有效地更改此代码以满足我的要求？
-
我试图解决一个问题，其中有一个带正加权边的无向图，我需要找到一个最短的路径，该路径正好覆盖所有节点，一旦给定了起始节点和结束节点。此外，图是完整的（每个节点都连接到图中的所有其他节点）。我已经试着寻找一个算法可以解决这个问题，但我还没有找到一个解决这个问题。由于起止节点的限制，这并不完全是旅游销售员的问题。我将感谢任何帮助。
-
我有一个以网状方式相互连接的节点的无向网络（即每个节点的度>=2)。我正在尝试找到一种方法来找到连接到网络中其他节点的最小数量的节点。 但通常情况不是这样，因为我需要手动找到其他节点。我想我可以使用最高度节点（例如x）作为源，使用找到到其他节点的最短路径。然后我可以迭代最短路径来找到其他节点。但是这种方法很乏味，我想知道是否有人有任何其他建议，使用networkx中可用的工具来最佳地解决这个问题。
-
问题声明：给定数组：[1,0,1,0,1,1,1,1,1,0,1,1,1,0]输出：到达结束所需的最小步骤 条件： 0上的步骤是退出 我已经完成了不使用DP的情况下的使用，是否存在针对此问题的DP解决方案。 我的代码：
-
因此，在Hackerrank上的一个名为“非循环图”的编程竞赛中出现了这个挑战，它基本上可以归结为计算“有向非循环图”中每个节点可达的节点数。例如，假设你有一个这样的图: 可达性计数（包括源节点）： 我的方法是“深度优先”遍历和记忆。环顾四周，但似乎运行时间无法进一步提高，因为在以下情况下会出现过度计数： 第三个节点将计算第四个节点，即使第二个节点已经计算了第四个节点。更糟糕的是，我只用JavaS