python - 有没有办法在矩阵中找到连接？

Question

我正在尝试编写一个函数，它将显示这些示例。

一个。connection (False) 节点 1 连接到节点 2

湾。共享连接（真）节点 1 连接到节点 2，而节点 2 连接到节点 3，因此意味着节点 1 和节点 3 与节点 2 共享连接

C。disconnection(False) 节点1和节点4完全断开

它需要返回一个布尔值，例如

matrix = [[ [0,1,1,1,0],
             [1,0,0,1,0],
             [1,0,0,0,1],
             [1,1,0,0,0],
             [0,0,1,0,0] ]

调用 nodeconn(matrix, 0, 4) 应该返回 true，因为矩阵显示了节点 0 和节点 4 之间共享的连接，两者都连接到节点 2。

也调用 nodeconn(matrix, 1, 4) 应该返回 False 因为 1 和 4 没有共同的节点

我尝试将矩阵转换为边缘列表并使用 for 循环进行循环。它没有用，所以我改变了我的方法

def nodeconn(matrix, node1, node2):
    n1 = matrix[node1]
    n2 = graph_matrix[node2]
    for index in matrix:
        for connections in index:
            if connections in n1 and n2:
                return True
            elif nd1[node2]==1:
                return False
    return False

标签： pythonpython-3.x

Answer 1

如果你想在路径中找到 > 1 个节点的共享连接，你可以使用 bfs：

def check_if_path_exists(matrix, node1, node2):
    queue = [node1]
    visited = set()
    while queue:
        current_node = queue.pop(0)
        visited.add(current_node)

        for index, is_connected in enumerate(matrix[current_node]):
            if not is_connected:
                continue

            if index == node2:
                return True
            elif index not in visited and index not in queue:
                queue.append(index)

    return False

def check_if_connection_is_shared(matrix, node1, node2):
    if matrix[node1][node2]:
        return False  # connected

    return check_if_path_exists(matrix, node1, node2)

如果您想在共享连接中查找只有 1 个节点的节点，则可以简化此代码：

def check_if_connection_is_shared(matrix, node1, node2):
    if matrix[node1][node2]:
        return False  # connected directly

    for a, b in zip(matrix[node1], matrix[node2]):  # if both node1 and node2 are connected to the same node, in connections list element with this node number will be 1 for both node1 and node2.
        if a and b:
            return True

    return False