печать всех ребер графа в матрице смежности в python - PullRequest
Новая
       32

печать всех ребер графа в матрице смежности в python

0 голосов
/ 30 декабря 2018

Как вы печатаете все ребра графа с заданной матрицей смежности в 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))

Ответы [ 3 ]

0 голосов
/ 30 декабря 2018

Не уверен, почему вы определяете visited, так как с циклом double for вы перебираете все элементы один раз.Более простой подход, все еще похожий на то, что вы делаете, это: 

def edges(A):
    edges = []
    for i in range(len(A)):
        for j in range(len(A[0])):
            if (A[i][j] == 1):
                edges.append((i,j))
    return edges

print(edges(A))
[(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)
print(g.edges)

[(0, 1), (0, 5), (1, 5), (2, 3), (2, 4), (3, 4)]
0 голосов
/ 30 декабря 2018

Вы можете преобразовать матрицу в список смежности, затем распечатать узлы и соединительные ребра: 

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)]
0 голосов
/ 30 декабря 2018

Если я правильно понял, и учитывая, что ваш пример матрицы 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)
...