在Python中打印邻接矩阵的所有边

Question

如何在Python中使用给定的邻接矩阵打印图的所有边缘？例如，如果0与3和8相邻，则应打印： 0 3 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))

- niko

---

你已经看过 networkx 库了吗？ - Paritosh Singh

Answer 1

如果我理解正确，鉴于您的示例矩阵 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)

- Dani Mesejo

---

是的，这是正确的，但是否有任何方法可以使用正常的BFS技术打印相同的输出呢？我的意思是使用队列和已探索数组？顺便说一句，谢谢。 - niko

Answer 2

一个简单的方法是遍历邻接矩阵，并建立一个包含连接位置索引的元组列表：

[(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)])

- yatu

---

谢谢您的回复，但是如果不使用networkx，您如何实现相同的功能？ - niko

Answer 3

你可以将矩阵转换为邻接表，然后输出节点和连接的边：

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)]

- RoadRunner

Answer 4

创建一个与邻接矩阵大小相同的网格：

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]

- Danny Zilberg