Построение и использование структуры данных графа в Python
Введение
Граф в терминах программирования — это абстрактный тип данных, который действует как нелинейная коллекция элементов данных, содержащая информацию об элементах и их связях друг с другом. Это может быть представлено G, где G = (V, E)и Vпредставляет набор вершин, а E представляет собой набор ребер, соединяющих эти вершины. Эти ребра могут представлять отношения между вершинами в виде простого [1, 0], независимо от того, есть соединение или нет, или заданного веса, который может представлять такие значения, как расстояние, сила отношения или количество раз, когда они взаимодействуют. . Это может быть полезно, когда мы хотим отобразить отношения между объектами, особенно когда существует несколько отношений, и когда мы хотим найти оптимальные способы выполнения потока задач.
Существует два распространенных способа реализации этого абстрактного типа данных в Python. Первая — это матрица смежности, а вторая — список смежности. Для наших целей мы будем реализовывать форму списка смежности, но стоит понять, почему это так.
Матрица смежности
Матрица смежности в виде двумерного массива — один из самых простых способов реализовать граф как структуру данных. Это будет представлено как:
где каждая из строк и столбцов будет представлять вершину графа. Это значение, хранящееся в ячейке, представляющей пересечение строки v и столбца w, указывает, существует ли ребро из вершины v в вершину w, а размер представляет «вес». Когда две из этих вершин соединены ребром, мы можем сказать, что они смежные.
Преимущество реализации матрицы смежности заключается в том, что она проста и для небольших графов легко визуализируется. Однако, если многие ячейки пусты, у нас «разреженная» матрица, и поэтому мы используем большие объемы памяти для отображения небольшого количества информации. Таким образом, проблема с этой реализацией заключается в объеме используемой памяти.
Список смежности
Более экономичный способ реализации редкосвязного графа — использование списка смежности. В этой реализации мы храним основной список всех вершин в объекте Graph, а затем каждый объект вершины поддерживает список других вершин, к которым он подключен.
Преимущество этой реализации заключается в том, что мы можем компактно представить разреженный граф, чтобы мы отображали только вершины, содержащиеся в графе, а затем их фактические связи, а не также не представляя никаких связей. Использование этого метода также позволяет нам легко найти все связи, которые напрямую связаны с одной вершиной.
Выполнение
Имея это в виду, зная, что мы хотим, чтобы структура данных содержала и как мы можем захотеть взаимодействовать с ней, мы можем думать о том, как мы хотим реализовать это в реальной структуре данных. Ключевые методы, обычно связанные с этим, включают:
addVertex(vert): добавитьvertexк графику с идентификатором, равным ключуaddEdge(fromVert, toVert): добавляет в граф новое направленное ребро, соединяющее две вершины.getVertex(vertKey): найти вершину в графе с именемvertKeygetVertices(): возвращает список всех вершин графа.inвозвращаетTrueдля оператора формыvertex in graph, если вершина находится в графе,Falseв противном случае
Существует два распространенных способа реализации этого абстрактного типа данных в Python. Первая — это матрица смежности, а вторая — список смежности. Для наших целей мы будем реализовывать форму списка смежности, но стоит понять, почему это так.
Класс вершин
Прежде чем мы создадим граф, содержащий весь список вершин, нам нужно создать класс вершин, который будет представлять каждую вершину в графе. В этой реализации каждая вершина использует словарь для отслеживания вершин, к которым она подключена, в форме атрибута connectedTo. Когда мы создаем новую вершину, мы инициализируем вершину ключом id of, который обычно представляет собой строку, представляющую эту вершину, и пустой словарь connectedTo. Мы также должны добавить функциональность этому классу Vertex, чтобы мы могли добавлять соседей в наш словарь,
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 f"{str(self.id)} connected to: {str([x.id for x in
self.connectedTo])}"
def getConnections(self):
retun self.connectedTo.keys()
def getId(self):
return self.id
def getWeight(self, nbr):
return self.connectedTo.get(nbr)
Класс графика
Способ, которым мы реализуем Graph в этом случае, заключается в том, что Graph содержит словарь, который сопоставляет имена вершин с объектами вершин. Это означает, что при построении нам просто нужно создать пустой словарь, который можно использовать для хранения Vertex объектов при их добавлении в график. Мы также можем добавить атрибут numVertices, который будет хранить количество вершин в графике, чтобы его можно было легко извлечь, когда мы захотим позже.
class Graph:
def __init__(self):
self.vertList = {}
self.numVertices = 0
Теперь, когда у нас есть наш граф, первое, что мы хотим добавить, это добавить вершину к нашему графу. В этой простой реализации мы сосредоточимся на простом добавлении вершины с заданным идентификатором. Для этого нам нужно создать новый класс Vertex с идентификатором ключа, использовать ключ в качестве ключа в словаре vertList и добавить созданный Vertex в качестве значения в словарь. Затем мы можем вернуть это, чтобы пользователь мог видеть вершину, которую он создал:
def addVertex(self, key):
"""
Add a vertex to the Graph network with the id of key
Time complexity is O(1) as we are only adding a single
new vertex which does not affect any other vertex
"""
#add 1 to the number of vertices attribute
self.numVertices += 1
#instantiate a new Vertex class
newVertex = Vertex(key)
#add the vertex with the key to the vertList dictionary
self.vertList[key] = newVertex
#return the NewVertex created
return newVertex
Что, если вы хотите посмотреть на саму вершину?
Затем мы можем создать метод, который будет возвращать фактическую вершину, если есть соответствующий ключ. Мы можем сделать это, используя метод get() для словарей, поскольку он вернет None, если ключ отсутствует в словаре, или в противном случае вернет фактическую вершину. Это позволит пользователю посмотреть, что содержит вершина, а также ссылки на другие вершины в графе.
def getVertex(self, key):
"""
If vertex with key is in Graph then return the Vertex
Time complexity is O(1) as we are simply checking whether
the key exists or not in a dictionary and returning it
"""
#use the get method to return the Vertex if it exists
#otherwise it will return None
return self.vertList.get(key)
В дополнение к этому есть метод, который позволяет нам использовать ключевое слово in, чтобы проверить, находится ли вершина внутри самого графа. Для этого мы используем метод __contains__ dunder, который позволит пользователю проверить, находится ли вершина в словаре, используя нотацию vertex in graph. Поскольку каждый ключ представляет собой вершину, мы можем просто вернуть, находится ли key в vertList или нет, что вернет True или False.
def __contains__(self, key):
"""
Check whether vertex with key is in the Graph
Time complexity is O(1) as we are simply checking whether
the key is in in the dictrionary or not
"""
#returns True or False depending if in list
return key in self.vertList
Важным атрибутом графа являются связи или ребра между вершинами, которые содержат информацию о том, как вершины могут быть связаны, будь то их расстояние или другая метрика. Для этого мы можем создать функцию addEdge, которая добавит ребро, соединяющее две вершины, указанные с весом по умолчанию, равным 0.
Способ, которым мы реализуем это ниже, представляет собой ориентированный граф, поскольку соединение осуществляется только от вершины f к вершине t, однако его можно легко расширить, включив соединение в обоих направлениях. Нам нужно убедиться, что обе вершины f и t действительно находятся в графе, поэтому, если они еще не существуют, мы можем вызвать уже созданный метод addVertex() для создания этих вершин, если это необходимо. Затем мы можем использовать метод addNeighbor() для каждой вершины, чтобы добавить соседа от f до t.
def addEdge(self, f, t, weight = 0):
"""
Add an edge to connect two vertices of t and f with weight
assuming directed graph
Time complexity of O(1) as adding vertices if they don't
exist and then add neighbor
"""
#add vertices if they do not exist
if f not in self.vertList:
nv = self.addVertex(f)
if t not in self.vertList:
nv = self.addVertex(t)
#then add Neighbor from f to t with weight
self.vertList[f].addNeighbor(self.vertList[t], weight)
Теперь у нас есть основная функциональность графа вместо возможности добавлять вершины, проверять их существование и добавлять соединения между вершинами. Таким образом, мы можем начать добавлять дополнительные функции, которые помогают в использовании структуры данных.
Во-первых, это возможность вернуть весь список вершин в графе. Это просто распечатает все имена вершин, но может быть полезно, когда нам нужен краткий обзор графа в его текущей структуре.
def getVertices(self):
"""
Return all the vertices in the graph
Time complexity is O(1) as we simply return all the keys
in the vertList dictionary
"""
return self.vertList.keys()
Второй — возможность вернуть количество вершин в графе. Это довольно просто, поскольку мы создали атрибут numVertices в методе конструктора, к которому мы затем добавляем 1 всякий раз, когда вызываем метод addVertex. Таким образом, мы просто возвращаем этот атрибут, чтобы показать, сколько вершин находится в графе.
def getCount(self):
"""
Return a count of all vertices in the Graph
Time complexity O(1) because we just return the count
attribute
"""
return self.numVertices
Затем мы можем собрать все это вместе, чтобы получить конечный продукт в виде:
Конечно, есть и другие методы, которые могут расширить эту реализацию, в том числе:
- Возможность перебирать каждую вершину
- Возможность удалять вершины из сети
- Возможность удалять или изменять ребра в сети
Но эта простая реализация может заложить основу для этих дополнений.
Заключение
Граф — это очень универсальная структура данных, которую можно использовать различными способами для представления различных задач. Это может включать дорожную сеть, сеть друзей или ходы, которые шахматная фигура может сделать на шахматной доске. Его можно использовать в алгоритмах поиска, таких как поиск в ширину или поиск в глубину, или для извлечения атрибутов, общих для разных графов, таких как кратчайший путь, диаметр сети или центральность определенных узлов. Приведенную выше реализацию можно использовать в этих примерах с некоторыми изменениями, так что теперь у вас есть основа для более подробного изучения!
Это восьмая статья из серии, посвященной структурам данных, их использованию и реализации в Python. Если вы пропустили предыдущие три статьи об очередях, связанных списках и стеках в Python, вы можете найти их по следующим ссылкам:
Следующие статьи этой серии будут посвящены связанным спискам, очередям и графикам. Чтобы ничего не пропустить, подпишитесь на уведомления по электронной почте, когда они будут опубликованы:
И если вам понравилось то, что вы читаете, но вы еще не являетесь участником Medium, рассмотрите возможность поддержать меня и других замечательных авторов на этой платформе, зарегистрировавшись, используя мой реферальный код ниже:
Спасибо за чтение!
