Графы в Python

Графы – одна из наиболее важных структур данных. Они используются, чтобы представлять телефонные сети, карты, подключения к социальным сетям и т.д. В этой статье мы обсудим, что такое Графы и как его их реализовать в Python.

Что такое Графы?

В математике Графы – это набор вершин и ребер, где вершины являются конкретными объектами, а ребра представляют связи между вершинами. Вершины и ребра представлены с помощью наборов.

Математически Граф G можно представить как G = (V, E), где V – множество вершин, а E – множество ребер.

Если ребро Ei соединяет вершины v1 и v2, мы можем представить ребро как Ei= (v1, v2).

Как сделать Граф?

За основу возьмём следующий Граф:

Чтобы представить граф, нам нужно будет найти множество вершин и ребер в графе.

Сначала найдём множество вершин. Для этого можно создать набор, используя вершины, указанные на рисунке выше. На рисунке есть вершины A, B, C, D, E и F. Таким образом, набор вершин может быть создан как V={A, B, C, D, E, F}.

Чтобы найти набор рёбер, сначала мы найдем все рёбра на Графе. Видно, что на графике 6 рёбер от E1 до E6. Ребро Ei может быть создано в виде кортежа (v1, v2), где v1 и v2 – вершины, соединённые Ei. Для приведенного выше графика мы можем представить рёбра следующим образом.

• E₁=(A, D) 
• E₂ = (A,B)
• E₃= (A,E)
• E₄=(A, F)
• E₅=(B,F)
• E₆= (B,C)

Множество ребер E может быть представлено как E= {E1, E2, E3, E4, E5, E6}.

Наконец, граф G можно представить в виде G = (V, E), где V и E – множества вершин и рёбер.

Мы обсудили, как представить графы математически. Как же сделать его в Python? Давайте разберёмся.

Как представить графы в Python?

Мы можем представить графы, используя список смежности. Список смежности можно рассматривать как список, в котором каждая вершина хранит список всех вершин, связанных с ней.

Мы реализуем список смежности графа с помощью словаря и списков.

Сначала создадим словарь со всеми именами вершин в качестве ключей и пустым списком (списком смежности) в качестве связанных с ними значений, используя данный набор вершин.

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

Таким образом, каждый ключ (вершина) в словаре будет иметь связанное значение (список вершин), и словарь будет представлять весь граф в Python.

Учитывая набор вершин и рёбер, можно реализовать граф следующим образом.

vertices = {"A", "B", "C", "D", "E", "F"}
edges = {("A", "D"), ("A", "B"), ("A", "E"), ("A", "F"), ("B", "F"), ("B", "C")}
graph = dict()
for vertex in vertices:
    graph[vertex] = []
for edge in edges:
    v1 = edge[0]
    v2 = edge[1]
    graph[v1].append(v2)
    graph[v2].append(v1)
print("The given set of vertices is:", vertices)
print("The given set of edges is:", edges)
print("Graph representation in python is:")
print(graph)

Вывод:

The given set of vertices is: {'F', 'D', 'B', 'E', 'A', 'C'}
The given set of edges is: {('A', 'F'), ('A', 'B'), ('B', 'C'), ('A', 'D'), ('A', 'E'), ('B', 'F')}
Graph representation in python is:
{'F': ['A', 'B'], 'D': ['A'], 'B': ['A', 'C', 'F'], 'E': ['A'], 'A': ['F', 'B', 'D', 'E'], 'C': ['B']}

В выводе вы увидите, что каждый ключ графа имеет список вершин, которые связаны с ним в качестве его значения.

Заключение

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