Список смежности и матрица смежности в Python

Привет, я понимаю понятия смежности и матрицы, но я не понимаю, как их реализовать в Python:

Алгоритм для достижения следующих двух примеров достигает, но не знает ввода с самого начала, поскольку они жестко кодируют его в своих примерах:

Для списка смежности:

a, b, c, d, e, f, g, h = range(8) N = [ {b:2, c:1, d:3, e:9, f:4}, # a {c:4, e:3}, # b {d:8}, # c {e:7}, # d {f:5}, # e {c:2, g:2, h:2}, # f {f:1, h:6}, # g {f:9, g:8} # h ] 

Для матрицы смежности:

  a, b, c, d, e, f, g, h = range(8) _ = float('inf') # abcdefgh W = [[0,2,1,3,9,4,_,_], # a [_,0,4,_,3,_,_,_], # b [_,_,0,8,_,_,_,_], # c [_,_,_,0,7,_,_,_], # d [_,_,_,_,0,5,_,_], # e [_,_,2,_,_,0,2,2], # f [_,_,_,_,_,1,0,6], # g [_,_,_,_,_,9,8,0]] # h 

Снова любая помощь будет высоко оценена, спасибо!

  • Обеспечение того, что подпроцессы мертвы при выходе из программы Python
  • построение гистограмм, высота баров которых равна 1 в matplotlib
  • Система событий в Python
  • Использование сеанса в флеш-приложении
  • Присоединение таблиц mdb с pyodbc
  • Python Как просто перенаправить вывод печати в файл TXT с новой строкой, созданной для каждого перенаправления
  • Формирование биграмм слов в списке предложений с Python
  • Установка селена на использование настраиваемого профиля, но он продолжает открываться по умолчанию
  • 3 Solutions collect form web for “Список смежности и матрица смежности в Python”

    Предполагая, что:

     edges = [('a', 'b'), ('a', 'b'), ('a', 'c')] 

    Вот какой код для матрицы:

     from collections import defaultdict matrix = defaultdict(int) for edge in edges: matrix[edge] += 1 print matrix['a', 'b'] 
     2 

    И для «списка»:

     from collections import defaultdict adj_list = defaultdict(lambda: defaultdict(lambda: 0)) for start, end in edges: adj_list[start][end] += 1 print adj_list['a'] 
     {'c': 1, 'b': 2} 

    Настройка структур данных может быть довольно простой. Например, пример списка смежности может быть реализован с использованием параметра defaultdict следующим образом:

     from collections import defaultdict N = defaultdict(dict) 

    Затем, когда вы начинаете вводить ввод, просто сделайте N[start][end] = weight для каждого введенного края. Множество узлов будет немного сложнее, если у вас есть некоторые узлы без исходящих ребер (вам нужно объединить ключи внутренних словарей с внешним, чтобы быть уверенным, что у вас есть все). Но многие алгоритмы будут работать корректно даже без полного списка узлов.

    Матрица смежности немного сложнее, так как вам нужно знать количество узлов, чтобы правильно установить его размеры. Если вы это знаете заранее, то это легко:

     number_of_nodes = 8 _ = float("inf") N = [[_]*number_of_nodes for i in number_of_nodes] 

    Если вы этого не сделаете, вы, вероятно, захотите просмотреть по краям, которые вы получаете в качестве входных данных, чтобы найти наивысший нумерованный узел, а затем использовать тот же код, что и для создания матрицы. Например, если ваши ребра представлены в виде списка (start, end, weight) 3-х кортежей, вы можете использовать это:

     number_of_nodes = max(max(start, end) for start, end, weight in edges) 

    Я надеюсь, что приведенный ниже пример поможет вам иметь как Инициализированный график, так и пользовательский

     class Graph: """ Read the Intialized Graph and Create a Adjacency list out of it There could be cases where in the initialized graph <map> link issues are not maintained for example node 2 to 1 link 2->1 there needs to be a link then since undirected Graph 1->2 """ def __init__(self,Graph_init): self.edge={} for keys,values in Graph_init.items(): for value in values: self.addEdge(keys,value); """ Add a vertex to graph map structure is int => int list """ def addVertex(self,v): if v not in self.edge: self.edge[v]=[] """ Add Edge from both vertex to each other Make sure the nodes are present 

    «»»
    def addEdge (self, u, v): если u не в self.edge: self.addVertex (u), если v не в self.edge: self.addVertex (v), если u не в self.edge [v]: self .edge [v] .append (u), если v не в self.edge [u]: self.edge [u] .append (v)

     def isEdge(self,u,v): if u not in self.edge: return False if v not in self.edge: return False return u in self.edge[v] def display(self): for keys,values in self.edge.items(): print(keys,":=>",values) """A initalized Graph (not in form of adjaceny list""" Graph_init = {1:[2,3,5], 2:[1,4], 3:[1,6]}; """Default constrcutor takes care of making the initialzed map to adjaceny list""" g=Graph(Graph_init) g.addVertex(1) g.addVertex(2) g.addVertex(3) g.addEdge(1,2) g.addEdge(3,2) g.display(); 
    Interesting Posts

    Преобразование исходной строки байтов в Юникод, не зная кодовой страницы заранее

    pandas dataframe с заголовком 2 строки и экспорт в csv

    Как получить заголовки http в фляге?

    Частные функции / Применения переменных в python

    Получение списка всех подкаталогов в текущем каталоге

    Как я могу написать модульные тесты против кода, использующего matplotlib?

    ftp.retrbinary () help python

    Как вычислить skipgrams в python?

    Шифрование и расшифровка алгоритмом AES как в python, так и в android

    Почему NumPy и SciPy имеют много одинаковых функций? Что я должен предпочесть?

    Ошибка при развертывании приложения python для конечных точек Google в локальном приложении с SDK приложения Engine

    Как удалить все отдельные слова длиной 16 букв или более с помощью python

    Python находит сумму столбца в таблице в текстовом файле

    Почему django использует запятую как десятичный разделитель

    Автоматическая установка значения элемента перечисления для его имени

    Python - лучший язык программирования в мире.