Представление графов |
121 |
К концу главы вы будете хорошо понимать, что такое графы и как с ними работать. Графовые алгоритмы позволят вам отображать взаимосвязанные структуры данных, извлекать информацию из элементов, связанных прямы ми или косвенными отношениями, а также решать ряд сложных реальных задач.
ПРЕДСТАВЛЕНИЕ ГРАФОВ
Граф — это структура, которая отображает данные в виде вершин и ребер. Граф может быть представлен в виде аGraph = ( , ), где — набор вершин‚ а — на бор ребер. Обратите внимание, что aGraph имеет | | вершин и | | ребер.
Вершина, , представляет собой объект реального мира, например человека, |
||||||||||
компьютер, |
или деятельность. |
|
|
|
|
|
|
|||
Ребро, |
|
|
, соединяет две вершины в |
сеть: |
|
|
|
|
||
|
|
|
& |
i |
|
. |
||||
|
|
|
|
e( 1, 2) | e |
|
|
|
|
||
Предыдущее уравнение указывает, что в графе все ребра принадлежат множе ству и все вершины принадлежат множеству .
Ребро соединяет две вершины и таким образом отображает связь между ними. Вот несколько примеров взаимосвязей, которые можно представить в виде графа:
zz Дружба между людьми.
zz Человек, связанный с другом в LinkedIn.
zz Физическое соединение двух узлов в кластере. zzЧеловек, присутствующий на научной конференции.
В этой главе для представления графов мы будем использовать библиотеку Python networkx. Давайте попробуем создать простой граф на Python, используя networtx. Для начала создадим пустой граф, aGraph, без вершин или узлов:
import networkx as nx G = nx.Graph()
Теперь добавим одну вершину:
G.add_node("Mike")
122 |
Глава 5. Графовые алгоритмы |
Мы можем добавить группу вершин, используя список:
G.add_nodes_from(["Amine", "Wassim", "Nick"])
Также можно добавить одно ребро между существующими вершинами:
G.add_edge("Mike", "Amine")
Давайте теперь выведем на экран ребра и вершины (рис. 5.1).
Рис. 5.1
Обратите внимание, что если мы добавляем ребро, это также приводит и к до бавлению связанных вершин (если их еще нет), как показано в данном случае:
G.add_edge("Amine","Imran")
Если мы выведем список узлов, то получим следующий результат (рис. 5.2).
Рис. 5.2
Следует заметить, что запрос на добавление уже существующей вершины игно рируется без каких-либо сообщений. Запрос игнорируется или принимается в зависимости от типа созданного нами графа.
Типы графов
Графы можно разделить на четыре типа:
zz Неориентированные графы (undirected graphs). zz Ориентированные графы (directed graphs).
Представление графов |
123 |
zz Неориентированные мультиграфы (undirected multigraphs). zzОриентированные мультиграфы (directed multigraphs).
Давайте подробно рассмотрим каждый из них.
Неориентированные графы
В большинстве случаев отношения, представленные вершинами графа, можно рассматривать как неориентированные. В таких отношениях отсутствует иерар хия. При этом ребра называются неориентированными ребрами (undirected edges), а полученный граф — неориентированным графом (undirected graph) (рис. 5.3).
Рис. 5.3
Ниже приведены примеры неориентированных отношений:
zz Майк и Амина (Майк и Амина знают друг друга).
zz Вершина A и вершина B соединены (одноранговая связь).
Ориентированные графы
Граф, в котором связь между вершинами имеет некоторое направление, назы вается ориентированным графом (directed graph) (рис. 5.4).
Ниже приведены примеры ориентированных отношений:
zz Майк и его дом (Майк живет в доме, но дом не живет в Майке). zz Джон руководит Полом (Джон — менеджер Пола).
124 |
Глава 5. Графовые алгоритмы |
Рис. 5.4
Неориентированные мультиграфы
Иногда вершины имеют между собой более одного типа отношений. В таком случае может существовать более одного ребра, соединяющего одни и те же две вершины. Графы, в которых допускаются несколько параллельных ребер между двумя вершинами, называются мультиграфами. Мы должны четко указывать, является ли конкретный граф мультиграфом. Параллельные ребра представля ют различные типы связей между вершинами.
Мультиграф представлен на рис. 5.5.
Рис. 5.5
Пример мультиграфа: Майк и Джон являются не только одноклассниками, но и коллегами.