Как найти изолированные вершины?

Question

Учитывая матрицу смежности простого графика, как написать функцию, которая перечисляет изолированные вершины? (Если таковые имеются)

Изолированная вершина является вершиной со степенью 0.

матрица смежности выглядит следующим образом

a, b, c, d, e = range(6) 

#  a b c d e f 
N = [[0,1,0,0,0,1], # a 
    [1,0,1,0,0,0], # b 
    [0,1,0,1,0,0], # c 
    [0,0,1,0,0,1], # d 
    [0,0,0,0,0,0], # e 
    [1,0,0,1,0,0], # f 

Answer 1

Чего не хватает из вашего вопроса, то, что вы пробовали. Вернитесь и опубликуйте то, что вы попробовали, чтобы мы могли помочь вам больше, как сказал FrankV. Тем не менее, я дам предложение начать выяснение этого:

Прежде всего, вам нужно перебирать 2D-массив (я предполагаю это из вашего редактирования), поэтому вы знаете, что вам понадобятся вложенный цикл. Затем вам нужно будет проверить четыре разных направления (проверка ошибок за пределами индексов), чтобы увидеть, имеет ли вершина ребро; вы сделаете это для каждой вершины, которую вы перебираете (сложность O (n^2)).

Это базовый подход к алгоритму; Конечно, есть много других способов решить эту проблему. Первый шаг, однако, заключается в том, чтобы довести его до точки, где вы можете понять это, а затем закодировать его. Вернитесь к нему, когда вы его правильно работаете, и оптимизируйте его.

Answer 2

Чтобы найти изолированные вершины, вы можете сформировать график degree matrix, а затем искать 0 по диагонали. Вот два примера график:

import networkx as nx 
import matplotlib.pyplot as plt 
import numpy as np 

# star adjacency matrix 
star_adj = np.array([[0, 1, 1, 1, 1, 1], [1, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0], 
       [1, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0]]) 
# gr = nx.from_numpy_matrix(star_adj) 
# nx.draw(gr) 
# plt.show() 

Мы не ожидаем каких-либо изолированных вершин в этой звезды графике.

iso_adj = np.array([[0, 1, 1, 0, 0], [1, 0, 1, 0, 0], [1, 1, 1, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 0, 0]]) 

вершина этого графа 4 изолирована.

Теперь я нахожу градус_list (этот список эквивалентен главной диагонали матрицы степени, но здесь нет смысла делать всю матрицу, поскольку все, что мы хотим, являются диагональными элементами), суммируя столбцы смежности матрицы (или строк). После этого я печатаю индексы в этом списке, которые являются ==0.

def degree_list(adjacency_matrix): 
    return np.sum(adjacency_matrix, axis=1) 

star_deg = degree_list(star_adj) 
iso_deg = degree_list(iso_adj) 

print star_deg # prints: [5 1 1 1 1 1] 
print iso_deg # prints: [2 2 3 1 0] 

print [i for i, v in enumerate(star_deg) if v==0] # prints: [] 
print [i for i, v in enumerate(iso_deg) if v==0] # prints: [4] 

Наконец, для матрицы смежности ваш пост, здесь изолированная вершина:

c_adj = [[0,1,0,0,0,1], [1,0,1,0,0,0], [0,1,0,1,0,0], [0,0,1,0,0,1], [0,0,0,0,0,0], [1,0,0,1,0,0]] 
print [i for i, v in enumerate(degree_list(c_adj)) if v==0] # prints [4] 

• Линия i, v in enumerate(blah) получает индекс i и значение v из blah, enumerate().

Answer 3

#  a b c d e f 
N = [[0,1,0,0,0,1], # a 
    [1,0,1,0,0,0], # b 
    [0,1,0,1,0,0], # c 
    [0,0,1,0,0,1], # d 
    [0,0,0,0,0,0], # e 
    [1,0,0,1,0,0], # f 
    ] 

d=[ sum(i) for i in N] 

print [i for i,v in enumerate(d) if v==0] 

Таким образом, вы получите [4] на выходе и это ответ.