有没有一种返回布尔值的方法来确定节点及其组件是否连接？

Question

所以这是为了理解，我试着编码一种方法来识别哪里有联系，有点像一个节点的社会。基本上，如果我输入一个矩阵和一个节点，如果给定的节点有已经相关的组件，它将返回True或False

我曾尝试使用while循环来循环访问的集合，但我仍然迷失在这个过程中。从理解的角度来说，我对for循环感到更舒服。如果有一种方法可以迭代一系列子矩阵，以找到节点之间的关系，这将很容易理解和适应

def society(graph_matrix, node):

    for item in (graph_matrix):
        for j in item:
            if graph_matrix[item][j] and graph_matrix[item][node] and graph_matrix[j][node] == 1:
                return True
    return False


gmatrix =  [ [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] ]

因此，如果我输入(society(gmatrix,0))，答案应该返回True，因为当您查看节点0时，您可以看到它与节点1和节点3的连接，而节点1与节点3的连接可以在gmatrix矩阵中观察到。有点像一个节点的社会。我是

但是，society(gmatrix,2)应该返回False，节点2连接到0，节点4但是0和4没有连接

Answer 1

在代码中，for item in (graph_matrix):，这里item表示一个数字列表。 并且不能使用数字列表作为如下的矩阵索引：graph_matrix[item][node]

据我所知，你的问题是，你想知道三个节点是否相互连接。为此，您可以通过以下方式修改代码：

def society(graph_matrix, node):
    for i in range(len(graph_matrix[node])):
        for j in range(len(graph_matrix[node])):
            if graph_matrix[node][i] and graph_matrix[node][j] and graph_matrix[i][j] == 1:
                return True
    return False


gmatrix =  [ [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] ]

print(society(gmatrix, 0));

这里，len(graph_matrix[node])将返回graph_matrix[node]的长度，range(len(graph_matrix[node]))将从0迭代到length-1

Answer 2

我认为把你的图变成矩阵形式会让你很难去思考。将边缘连接列表转换为连接节点的列表将使事情变得更简单（并且，作为一个额外的好处，在society()将返回False的情况下减少计算负载，随着节点数量的增加，这一点更为重要）：

def to_map(gmatrix):
    return [[k for k,v in enumerate(edges) if v] for edges in gmatrix]

然后你就能做到：

def society(graph_map, node):
    for n in graph_map[node]:
        if n == node:
            continue
        for nn in graph_map[n]:
            if nn != node and nn != n and nn in graph_map[node]:
               return True
    return False

例如：

gmatrix =  [ [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] ]
gmap = to_map(gmatrix)

print(society(gmap,0)) # True
print(society(gmap,2)) # False