3
我正在尋找一種算法來檢查圖上兩個任意節點之間的任何有效連接（最短或最長）。算法是節點A在圖中連接到節點B
我的圖被固定在一個網格上，它具有北/南/東/西連接的邏輯（x，y）座標，但節點可以隨機移除，因此您不能假定採用最接近目標總是會讓你到那裏。
代碼是在Python中。數據結構是每個節點（對象）都有一個連接節點的列表。列表中的元素是對象裁判，這樣的話我們可以搜索連接節點的節點的列表遞歸，就像這樣：
for pnode in self.connected_nodes:
for cnode in pnode.connected_nodes:
...etc
我已經包括顯示節點如何映射到X，Y COORDS圖以及它們是如何連接在北/東/南/西。有時缺少節點（即J和K之間），有時缺少邊（即G和H之間）。節點和邊的存在是不斷變化的（儘管當我們運行該算法時，它會及時獲取固定的快照），並且只能通過檢查每個節點的連接節點列表來確定。
該算法需要產生一個簡單的真/假以確定兩個節點之間是否存在有效的連接。遞歸遍歷每個連接節點列表會爆炸所需的操作數量 - 如果節點距離較遠，則最多需要4^n次操作。我的理解是類似於Dijistrka的算法通過找到基於邊權重的最短路徑，但如果根本沒有連接，那麼它是否仍然有效？
對於一些背景，我使用它來模擬2D可破壞對象。每個節點代表一塊材料，並且如果一個或多個節點沒有連接到材料的其餘部分，那麼它應該分離。在圖中 - D，H，R - 應該從主體上剝離，因爲它們沒有連接。
UPDATE：
雖然許多貼出答案可能很好地工作的，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)
您是否知道networkx庫？像[this]（http://networkx.github.io/documentation/latest/reference/generated/networkx.algorithms.shortest_paths.generic.has_path.html）會有幫助嗎？ – Ioannis
@loannis看起來不錯。挖掘它們的源代碼，它看起來像使用dijisktra或類似的，如果找不到路徑則拋出異常。我有一些類似16行代碼的工作代碼，所以我會堅持，而不是導入一個全新的模塊。儘管如果我需要做更多的圖/樹算法，它可能值得切換到像networkx這樣的東西。我有一個習慣於重新發明輪子的機會。 – Oliver
確實，指針更多地提高了對NetworkX的認識，這在其他場合可能會有用。 – Ioannis