我正在寻找一种算法，用于检查在图形上任意两个节点之间的任何有效连接（最短或最长）。
我的图形被固定在一个网格上，具有逻辑（x，y）坐标和北/南/东/西连接，但节点可以随机删除，因此不能假设取距目标最近的坐标边缘总是能够到达目标。
代码使用 Python 编写。数据结构为每个节点（对象）都有一个连接节点列表。列表元素是对象引用，因此我们可以递归地搜索该节点的连接节点列表，如下所示：
我已经包含了一张图表，展示了节点如何映射到x、y坐标以及它们是如何在北/东/南/西方向上连接的。有时会缺少节点（即J和K之间），有时会缺少边缘（即G和H之间）。节点和边缘的存在是不稳定的（虽然当我们运行算法时，它会在固定的时间点进行快照），只能通过检查每个节点的连接节点列表来确定。
算法需要产生一个简单的true/false，以确定两个节点之间是否存在有效连接。递归遍历每个连接节点列表会导致操作数量爆炸——如果节点相隔n个边缘，则最多需要4^n次操作。我理解的是，Dijistrka算法之类的算法是基于边权重寻找最短路径的，但如果根本没有连接，它仍然能工作吗？
对于一些背景，我正在使用这个模型来建模二维可摧毁物体。每个节点表示一块材料，如果一个或多个节点与其余材料没有连接，则应该分离。在图表中，D、H、R应该从主体中分离出来，因为它们没有连接。
更新：
虽然许多发布的答案都可能有效，但DFS快速、简单且非常合适。我不喜欢在具有高价值权重的节点之间添加额外的边缘以使用Dijkstra，因为节点本身可能会消失，而不仅仅是边缘。SSC方法似乎更适合区分强连接和弱连接的图形部分，在我的图表中，如果G和H之间有单个边缘，则可以工作。
这是我的DFS搜索实验代码，它创建了与图表中所示相同的图形。
我的图形被固定在一个网格上，具有逻辑（x，y）坐标和北/南/东/西连接，但节点可以随机删除，因此不能假设取距目标最近的坐标边缘总是能够到达目标。
代码使用 Python 编写。数据结构为每个节点（对象）都有一个连接节点列表。列表元素是对象引用，因此我们可以递归地搜索该节点的连接节点列表，如下所示：
for pnode in self.connected_nodes:
for cnode in pnode.connected_nodes:
...etc
我已经包含了一张图表，展示了节点如何映射到x、y坐标以及它们是如何在北/东/南/西方向上连接的。有时会缺少节点（即J和K之间），有时会缺少边缘（即G和H之间）。节点和边缘的存在是不稳定的（虽然当我们运行算法时，它会在固定的时间点进行快照），只能通过检查每个节点的连接节点列表来确定。
算法需要产生一个简单的true/false，以确定两个节点之间是否存在有效连接。递归遍历每个连接节点列表会导致操作数量爆炸——如果节点相隔n个边缘，则最多需要4^n次操作。我理解的是，Dijistrka算法之类的算法是基于边权重寻找最短路径的，但如果根本没有连接，它仍然能工作吗？
对于一些背景，我正在使用这个模型来建模二维可摧毁物体。每个节点表示一块材料，如果一个或多个节点与其余材料没有连接，则应该分离。在图表中，D、H、R应该从主体中分离出来，因为它们没有连接。
更新：
虽然许多发布的答案都可能有效，但DFS快速、简单且非常合适。我不喜欢在具有高价值权重的节点之间添加额外的边缘以使用Dijkstra，因为节点本身可能会消失，而不仅仅是边缘。SSC方法似乎更适合区分强连接和弱连接的图形部分，在我的图表中，如果G和H之间有单个边缘，则可以工作。
这是我的DFS搜索实验代码，它创建了与图表中所示相同的图形。
class node(object):
def __init__(self, id):
self.connected_nodes = []
self.id = id
def dfs_is_connected(self, node):
# Initialise our stack and our discovered list
stack = []
discovered = []
# Declare operations count to track how many iterations it took
op_count = 0
# Push this node to the stack, for our starting point
stack.append(self)
# Keeping iterating while the stack isn't empty
while stack:
# Pop top element off the stack
current_node = stack.pop()
# Is this the droid/node you are looking for?
if current_node.id == node.id:
# Stop!
return True, op_count
# Check if current node has not been discovered
if current_node not in discovered:
# Increment op count
op_count += 1
# Is this the droid/node you are looking for?
if current_node.id == node.id:
# Stop!
return True, op_count
# Put this node in the discovered list
discovered.append(current_node)
# Iterate through all connected nodes of the current node
for connected_node in current_node.connected_nodes:
# Push this connected node into the stack
stack.append(connected_node)
# Couldn't find the node, return false. Sorry bud
return False, op_count
if __name__ == "__main__":
# Initialise all nodes
a = node('a')
b = node('b')
c = node('c')
d = node('d')
e = node('e')
f = node('f')
g = node('g')
h = node('h')
j = node('j')
k = node('k')
l = node('l')
m = node('m')
n = node('n')
p = node('p')
q = node('q')
r = node('r')
s = node('s')
# Connect up nodes
a.connected_nodes.extend([b, e])
b.connected_nodes.extend([a, f, c])
c.connected_nodes.extend([b, g])
d.connected_nodes.extend([r])
e.connected_nodes.extend([a, f, j])
f.connected_nodes.extend([e, b, g])
g.connected_nodes.extend([c, f, k])
h.connected_nodes.extend([r])
j.connected_nodes.extend([e, l])
k.connected_nodes.extend([g, n])
l.connected_nodes.extend([j, m, s])
m.connected_nodes.extend([l, p, n])
n.connected_nodes.extend([k, m, q])
p.connected_nodes.extend([s, m, q])
q.connected_nodes.extend([p, n])
r.connected_nodes.extend([h, d])
s.connected_nodes.extend([l, p])
# Check if a is connected to q
print a.dfs_is_connected(q)
print a.dfs_is_connected(d)
print p.dfs_is_connected(h)