算法是图中节点A连接到节点B

Question

我正在寻找一个算法来检查任何有效的连接（最短或最长）之间的两个任意节点在一个图上。

我的图被固定为一个具有逻辑(x，y)坐标的网格，具有北/南/东/西连接，但是节点可以随机移除，所以你不能假设取离目标最近的coords的边总是会让你到达那里。

代码是用Python编写的。数据结构是每个节点（对象）都有一个连接节点的列表。列表元素是对象引用，因此我们可以递归地搜索该节点的连接节点列表，如下所示：

for pnode in self.connected_nodes:
    for cnode in pnode.connected_nodes:
        ...etc

尽管许多张贴的答案可能很有效，但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)

Answer 1

要找到这一点，您只需要在其中一个节点上运行简单的DFS或BFS算法，它将在图的一个连续组件中找到所有可到达的节点，所以如果在算法运行期间找到了另一个节点，您只需将其标记下来。