我有一个无向和未加权图的节点的某个子集 . 我试图确定所有这些节点之间是否存在路径，如果存在，那么包含最少节点的最短路径是什么，这些节点不在节点子集中 .
我一直试图想办法修改最小生成树算法来实现这一目标，但到目前为止我还没有提出一个可行的解决方案 .
有没有一种好方法可以做到这一点，或者这是对已知算法的描述？
我正在尝试确定所有这些节点之间是否存在路径
（我从中理解你正在寻找一个访问所有标记节点的单一路径）
好吧，我的朋友，这可能是一个问题 - 你正在描述Traveling Salesman Problem和Hamiltonian Path Problem的变体（如果你正在寻找一条简单的路径，哈密顿路径的reduction是直截了当的：标记所有节点） .但我担心这些问题是NP-Hard .
NP-Hard问题是我们要解决它的问题，而一般的假设是 - 一个不存在1 .
因此，你最好的镜头可能是一些指数解决方案 . 有使用动态编程或强力解决方案的TSP的 O(n^2 * 2^n) 解决方案 O(n!)
O(n^2 * 2^n)
O(n!)
（1）真的不是一个正式的定义，但这是了解问题的足够信息，NP-Hard问题确实存在很多 .
这是一种方法，可以让你在那里的一些方式：
使用Floyd-Warshall或Dijkstra来找到每个i和j的节点i和节点j之间的距离d（i，j），使得节点i和节点j在节点的子集中 .
（如果d（i，j）=无穷大，那么现在停止，没有解决方案）
创建一个包含子集中每个节点的新图 . 对于每个d（i，j），在新图中的节点i，节点j之间添加一个边，权重= d（i，j）
现在在这个新图上使用旅行推销员算法来找到访问所有节点的最短路径 .
此最短路径为您提供路径的长度，但路径可能会多次访问某些节点 . 这意味着我们在所需子集之外的节点数上限 .
Dijkstra的算法或使用广度优先搜索 .
你应该使用Dijkstra's shortest path algorithm . 首先，您必须为图中的所有边分配权重（或距离），连接不在子集中的两个节点的每个边必须赋予权重1.连接子集中的一个或两个节点的每个边必须给予无限重量 . 其次，你应该在结果图上运行Dijkstra的算法 . 该算法将检查图的每个边缘 .
此外，您可以使用A* (A-star) algorithm .
更新：我一开始不明白这个问题 . 正如@amit所说，这是一个NP难问题，是HCP和TSP的结合 . 也许某种随机搜索算法可以在多项式时间内以高概率解决这个问题 .
我创建了一个Graph / Node / Connection类，它不仅可以显示最短路径，还可以告诉您是否所有节点都已连接：
var allNodesAreConnected = StartNode.AllNodes.All(n => n.IsConnectedToStartNode);
或者，如果您想知道哪些节点没有连接，请稍微更改一下：
var anotConnectedNodes = StartNode.AllNodes.Where(n => !n.IsConnectedToStartNode);
这篇文章中的更多示例和完整代码：Create your own navigation system (with a Graph, Node and Connection class)
对于那些没有真正具有图论背景的人，我已经解决了这个问题，发现在一个无向图中，最简单的方法是Depth First Search . 像Dijkstra这样的算法的实现通常采用 weighted 解决方案，并为权重输入任意值 .
我找到工作的解决方案我遍历节点使用 DFS 并记录每次成功的旅程，然后它只是返回最短的成功旅程的情况 .
这是繁重的文件：Depth First Search Algorithm
6 回答
（我从中理解你正在寻找一个访问所有标记节点的单一路径）
好吧，我的朋友，这可能是一个问题 - 你正在描述Traveling Salesman Problem和Hamiltonian Path Problem的变体（如果你正在寻找一条简单的路径，哈密顿路径的reduction是直截了当的：标记所有节点） .
但我担心这些问题是NP-Hard .
NP-Hard问题是我们要解决它的问题，而一般的假设是 - 一个不存在1 .
因此，你最好的镜头可能是一些指数解决方案 . 有使用动态编程或强力解决方案的TSP的
O(n^2 * 2^n)解决方案O(n!)（1）真的不是一个正式的定义，但这是了解问题的足够信息，NP-Hard问题确实存在很多 .
这是一种方法，可以让你在那里的一些方式：
使用Floyd-Warshall或Dijkstra来找到每个i和j的节点i和节点j之间的距离d（i，j），使得节点i和节点j在节点的子集中 .
（如果d（i，j）=无穷大，那么现在停止，没有解决方案）
创建一个包含子集中每个节点的新图 . 对于每个d（i，j），在新图中的节点i，节点j之间添加一个边，权重= d（i，j）
现在在这个新图上使用旅行推销员算法来找到访问所有节点的最短路径 .
此最短路径为您提供路径的长度，但路径可能会多次访问某些节点 . 这意味着我们在所需子集之外的节点数上限 .
Dijkstra的算法或使用广度优先搜索 .
你应该使用Dijkstra's shortest path algorithm . 首先，您必须为图中的所有边分配权重（或距离），连接不在子集中的两个节点的每个边必须赋予权重1.连接子集中的一个或两个节点的每个边必须给予无限重量 . 其次，你应该在结果图上运行Dijkstra的算法 . 该算法将检查图的每个边缘 .
此外，您可以使用A* (A-star) algorithm .
更新：我一开始不明白这个问题 . 正如@amit所说，这是一个NP难问题，是HCP和TSP的结合 . 也许某种随机搜索算法可以在多项式时间内以高概率解决这个问题 .
我创建了一个Graph / Node / Connection类，它不仅可以显示最短路径，还可以告诉您是否所有节点都已连接：
或者，如果您想知道哪些节点没有连接，请稍微更改一下：
这篇文章中的更多示例和完整代码：Create your own navigation system (with a Graph, Node and Connection class)
对于那些没有真正具有图论背景的人，我已经解决了这个问题，发现在一个无向图中，最简单的方法是Depth First Search . 像Dijkstra这样的算法的实现通常采用 weighted 解决方案，并为权重输入任意值 .
我找到工作的解决方案我遍历节点使用 DFS 并记录每次成功的旅程，然后它只是返回最短的成功旅程的情况 .
这是繁重的文件：Depth First Search Algorithm