Как реализовать граф на python

Заполнение графа соответствующими вершинами

За 2 прохода по исходному словарю.
Первый проход — создание обратного словаря (значение: список_ключей).
Второй проход — объединение двух словарей.

from collections import defaultdict G = P = defaultdict(list) for k,l in G.items(): for v in l: P[v].append(k) for k,v in G.items(): P[k].extend(v) print(P)

defaultdict(list, )

Отслеживать
ответ дан 25 янв 2022 в 17:36
13.4k 1 1 золотой знак 8 8 серебряных знаков 23 23 бронзовых знака

Если граф неориентированный + все рёбра описаны лишь единожды, то можно сделать так:

Пройти по всем ключам исходного словаря, перед этим создав новый словарь H , состоящий из ключей исходного графа. Изначальные значения для каждого ключа — пустые списки;
Пройти по всем значениям списка для текущего ключа и сделать следующее: пусть ключ равен key и текущее значение равно value , тогда мы добавим в список для ключа key значение value и добавим в список для ключа value значение key . Поскольку, как было написано выше, граф неориентированный, то пару (ключ-значение) можно перевернуть, т.е. представить значение в виде ключа, а ключ — в виде значения.

G = H = dict() for i in range(1, 6 + 1): # вместо 6 можно поставить кол-во вершин графа H[i] = [] for i in G: for elem in G[i]: if i

Отслеживать
ответ дан 25 янв 2022 в 17:21
3,933 4 4 золотых знака 9 9 серебряных знаков 22 22 бронзовых знака

Что-то в роде такого ? : ` for i in G:` ` if G[i] not in g:` ` g.setdefault(i,[])` Был бы благодарен за небольшой код

25 янв 2022 в 17:30

@Zvukoed можно проще: for i in G: H[i] = [] — так можно быстро создать словарь для каждой вершины исходного графа

работа с графами в Python

Будет использоваться ненаправленный связный граф V=6 E=6. Существует две популярные методики представления графов: матрица смежности (эффективна с плотными графами) и список связей (эффективно с разряженными графами). Будем использовать второй способ.

graph = 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E']>

2 Depth-First Search — Поиск вглубину

Алгоритм поиска вглубину: исследуем сначала все возможные вершины (из выбранного корня) доступные из текущей, прежде чем возвращаться назад. Данный алгоритм можно реализовать как рекурсивно, так и итеративно. Последовательность действий:

Помечаем текущую вершину как посещённую
Исследуем каждую соседнюю вершину не включённую в список уже посещённых
Вариант с DFS and BFS in Python (модифицированный, т.к. set не поддерживает упорядоченность элементов)

graph = 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E']> def dfs(graph, start): visited, stack = [], [start] while stack: vertex = stack.pop() if vertex not in visited: visited.append(vertex) stack.extend(set(graph[vertex]) - set(visited)) return visited print(dfs(graph, 'A'))

['A', 'C', 'F', 'E', 'B', 'D']

Вариант с DFS and BFS graph traversal (Python recipe) (модифицированный, т.к. для реализации стека нам необходимо добавлять элементы в конец списка, а не в начало)

graph = 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E']> def iteractive_dfs(graph, start, path=None): """iterative depth first search from start""" if path is None: path = [] q = [start] while q: v = q.pop() if v not in path: path = path + [v] q += graph[v] return path print(iteractive_dfs(graph, 'A'))

['A', 'C', 'F', 'E', 'B', 'D']

3 DFS Paths — поиск пути между двумя вершинами

graph = 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E']> def dfs_paths(graph, start, goal): stack = [(start, [start])] # (vertex, path) while stack: (vertex, path) = stack.pop() for next in set(graph[vertex]) - set(path): if next == goal: yield path + [next] else: stack.append((next, path + [next])) print(list(dfs_paths(graph, 'A', 'F')))

[['A', 'C', 'F'], ['A', 'B', 'E', 'F']]

4 Bread-Firsth Search — Поиск вширину

Позволяет найти кратчайший путь между двумя вершинами. Довольно сложно реализовать рекурсивно, гораздо проще реализовать его с использованием очереди.

graph = 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E']> from queue import deque def bfs(graph, start): visited, queue = [], deque([start]) while queue: vertex = queue.pop() if vertex not in visited: visited.append(vertex) queue.extendleft(set(graph[vertex]) - set(visited)) return visited print(bfs(graph, 'A'))

['A', 'B', 'C', 'D', 'E', 'F']

5 BFS Paths

from queue import deque graph = 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E']> def bfs_paths(graph, start, goal): queue = deque([(start, [start])]) while queue: (vertex, path) = queue.pop() for next in set(graph[vertex]) - set(path): if next == goal: yield path + [next] else: queue.appendleft((next, path+[next])) print(list(bfs_paths(graph, 'A', 'F'))) def shortest_path(graph, start, goal): try: return next(bfs_paths(graph, start, goal)) except StopIteration: return None print(shortest_path(graph, 'A', 'F')) print(shortest_path(graph, 'E', 'D')) print(shortest_path(graph, 'A', 'D')) print(shortest_path(graph, 'F', 'D'))

[['A', 'C', 'F'], ['A', 'B', 'E', 'F']] ['A', 'C', 'F'] ['E', 'B', 'D'] ['A', 'B', 'D'] ['F', 'E', 'B', 'D']

Author: Pavel Vavilin

Created: 2017-11-09 Thu 19:40

Как на Python написать код для построения графа по матрице смежности чтобы только односторонние стрелки отображались?

введите сюда описание изображения

Если построить по этому коду то стрелки которые указывают на двух вершин тоже отображаются. А хотелось бы чтобы их не было на графе.

Отслеживать

задан 2 июн 2022 в 14:59

1 2 2 бронзовых знака

Что-что нужно? В вершине 4 только одна входящая дуга, и стрелка в неё только одна.

3 июн 2022 в 3:33

Значит отредактируйте матрицу смежности, выберите какие связи/стрелки оставить.

14 ноя 2022 в 17:29

1 ответ 1

Сортировка: Сброс на вариант по умолчанию

Параметр «arrows» изменить на False

 nx.draw(G, with_labels=True, node_size=300, arrows=False)

Отслеживать

ответ дан 14 ноя 2022 в 17:25

1 1 1 бронзовый знак

добро пожаловать на Stack Overflow на русском! пожалуйста, постарайтесь оставлять чуть более развёрнутые ответы. дополнить ответ можно, нажав править

Реализация¶

Реализовать список смежности на Python с помощью словарей очень легко. Для АТД графа мы создадим два класса (см. листинг 1 и листинг 2): Graph , содержащий основной список вершин, и Vertex — представление каждой из них в графе.

Объекты Vertex будут использовать словарь для отслеживания смежных вершин и весов рёбер. Называться он будет connectedTo . Листинг ниже показывает код для класса Vertex . Конструктор просто инициализирует id (обычную строку) и словарь connectedTo . Метод addNeighbor используется для добавления связи данной вершины с другой. Метод getConnections возвращает все вершины из списка смежности, которые представлены в connectedTo . Метод getWeight возвращает вес ребра из этой вершины к передаваемой ему в качестве параметра.

Листинг 1

class Vertex: def __init__(self,key): self.id = key self.connectedTo = <> def addNeighbor(self,nbr,weight=0): self.connectedTo[nbr] = weight def __str__(self): return str(self.id) + ' connectedTo: ' + str([x.id for x in self.connectedTo]) def getConnections(self): return self.connectedTo.keys() def getId(self): return self.id def getWeight(self,nbr): return self.connectedTo[nbr]

Класс Graph , показанный в следующем листинге, содержит словарь, отображающий имена вершин на их объекты. На рисунке 4 последний показан затенённым серым прямоугольником. Также Graph предоставляет методы для добавления вершин в граф и связывания их друг с другом. Дополнительно мы имеем реализацию метода __iter__ , облегчающего итерации по объектам Vertex в конкретном графе. Вместе два метода позволяют делать итерации по именам вершин или непосредственно по объектам.

Листинг 2

class Graph: def __init__(self): self.vertList = <> self.numVertices = 0 def addVertex(self,key): self.numVertices = self.numVertices + 1 newVertex = Vertex(key) self.vertList[key] = newVertex return newVertex def getVertex(self,n): if n in self.vertList: return self.vertList[n] else: return None def __contains__(self,n): return n in self.vertList def addEdge(self,f,t,cost=0): if f not in self.vertList: nv = self.addVertex(f) if t not in self.vertList: nv = self.addVertex(t) self.vertList[f].addNeighbor(self.vertList[t], cost) def getVertices(self): return self.vertList.keys() def __iter__(self): return iter(self.vertList.values())

Следующая сессия Python создаёт граф с рисунка 2, используя свежеопределённые классы Graph и Vertex . Сначала мы создаём шесть вершин, пронумерованных от 0 до 5. Затем печатаем словарь, их содержащий. Обратите внимание, что для каждого ключа от 0 до 5 создаётся сущность класса Vertex . Далее добавляем рёбра, связывающие вершины вместе. Наконец, вложенный цикл удостоверяется, что каждое ребро в графе сохранено правильно. Вы можете сравнить вывод списка рёбер в конце сессии с рисунком 2.

>>> g = Graph() >>> for i in range(6): . g.addVertex(i) >>> g.vertList , 1: , 2: , 3: , 4: , 5: > >>> g.addEdge(0,1,5) >>> g.addEdge(0,5,2) >>> g.addEdge(1,2,4) >>> g.addEdge(2,3,9) >>> g.addEdge(3,4,7) >>> g.addEdge(3,5,3) >>> g.addEdge(4,0,1) >>> g.addEdge(5,4,8) >>> g.addEdge(5,2,1) >>> for v in g: . for w in v.getConnections(): . print("( %s , %s )" % (v.getId(), w.getId())) . ( 0 , 5 ) ( 0 , 1 ) ( 1 , 2 ) ( 2 , 3 ) ( 3 , 4 ) ( 3 , 5 ) ( 4 , 0 ) ( 5 , 4 ) ( 5 , 2 )

readers online now | | Back to top