python中打印具有给定邻接矩阵的图形的所有边缘? 例如,如果 0 与 3 和 8 相邻,则应打印:4 ·0 8无重复我一直在使用 Bfs,但我不知道如何更新队列和当前元素。
这是我到目前为止的代码
A = [[0, 1, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 1],
[0, 0, 0, 1, 1, 0],
[0, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0]]
def edges(A):
visited = [False] * len(A)
queue = []
s = [0][0]
queue.append(s)
visited[s] = True
while len(queue) > 0:
s = queue.pop(0)
print(s)
for i in range(len(A)):
print(i)
for j in range(len(A[0])):
if A[i][j] == 1 and visited[s]== False:
queue.append([i][j])
visited[s] = True
print(edges(A))
如果我理解正确,并且考虑到您的示例矩阵A
是不对称的,您可以执行以下操作:
A = [[0, 1, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 1],
[0, 0, 0, 1, 1, 0],
[0, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0]]
def edges(adj):
for i, neighbors in enumerate(adj):
for j, v in enumerate(neighbors):
if v:
yield (i, j)
for edge in edges(A):
print(edge)
输出
(0, 1)
(0, 5)
(1, 0)
(1, 5)
(2, 3)
(2, 4)
(3, 4)
(5, 0)
一个简单的方法是遍历邻接矩阵,并使用存在连接的索引构建元组列表:
[(i,j) for i,l in enumerate(A) for j,v in enumerate(l) if v]
# [(0, 1), (0, 5), (1, 0), (1, 5), (2, 3), (2, 4), (3, 4), (5, 0)]
但是,您可以使用 networkx
.您可以使用 from_numpy_matrix
从邻接矩阵创建图形,并使用 edges
打印带有边缘的列表:
A = np.array([[0, 1, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 1],
[0, 0, 0, 1, 1, 0],
[0, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0]])
import networkx as nx
g = nx.from_numpy_matrix(A, create_using=nx.DiGraph)
g.edges()
# OutEdgeView([(0, 1), (0, 5), (1, 0), (1, 5), (2, 3), (2, 4), (3, 4), (5, 0)])
您可以将矩阵转换为邻接列表,然后打印出节点和连接边:
A = [
[0, 1, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 1],
[0, 0, 0, 1, 1, 0],
[0, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0],
]
def matrix_to_list(matrix):
"""Convert adjacency matrix to adjacency list"""
graph = {}
for i, node in enumerate(matrix):
adj = []
for j, connected in enumerate(node):
if connected:
adj.append(j)
graph[i] = adj
return graph
adjacency_list = matrix_to_list(A)
print(adjacency_list)
# {0: [1, 5], 1: [0, 5], 2: [3, 4], 3: [4], 4: [], 5: [0]}
connected_edges = [
(node, edge) for node, edges in adjacency_list.items() for edge in edges
]
print(connected_edges)
# [(0, 1), (0, 5), (1, 0), (1, 5), (2, 3), (2, 4), (3, 4), (5, 0)]
<</div>
div class="one_answers"> 创建邻接矩阵大小的网格网格:
nodes = np.arange(len(A))
c_grid, r_grid = np.meshgrid(nodes, nodes)
np.stack([r_grid, c_grid, A])
现在你有一个维度的立方体 [3, len(nodes), len(nodes)],你可以根据 A 对其进行切片:
almost_edges = coords_adj_mat[:, adj_mat]
edges = almost_edges[:2]