Обратите внимание на другие наши ресурсы:
Youtube | Telegram | VK | Rutube | Dzen | Boosty
Графы являются одним из объединяющих понятий информатики – абстрактное представление, которое описывает организацию транспортных систем, взаимодействие между людьми и телекоммуникационные сети. То, что с помощью одного формального представления можно смоделировать так много различных структур, является источником огромной силы для образованного программиста.
Стивен С. Скиена
¶ Историческая справка.
Задача о Кенигсбергских мостах
(лат. problema Regiomontanum de septem pontibus, англ. the Königsberg bridges problem) - старинная математическая задача, в которой спрашивалось, как можно пройти по всем семи мостам центра старого Кёнигсберга, не проходя ни по одному из них дважды.
Впервые была решена в статье, датированной 1736 годом, математиком Леонардом Эйлером, который доказал, что это невозможно, и по ходу доказательства изобрел эйлеровы циклы.
Решение Эйлером задачи о кёнигсбергских мостах явилось первым в истории применением теории графов, но без использования термина граф и без рисования диаграмм графов.
¶ Структура графов
Граф состоит из вершин, соединенных ребрами. Обычно обозначается буквой V. Количество вершин графа:
Буквой E - количество ребер:
Общий вид записи графа:
Для правильного понимания графов следует учитывать, что граф не является геометрическим объектом. Форма визуализации не влияет на его суть или свойства, потому что граф это топологический объект.
Термин «топология» впервые появился в 1847 году в работе Листинга. Листинг определяет топологию так:
«Под топологией будем понимать учение о модальных отношениях пространственных образов — или о законах связности, взаимного положения и следования точек, линий, поверхностей, тел и их частей или их совокупности в пространстве, независимо от отношений мер и величин».
Две вершины называются соседними или смежными, если они соединены ребром. Степенью вершины называется число соседних с ней вершин:
Максимальная степень вершины в графе:
Минимальная степень вершины графа:
Формула суммы степеней графа :
*Сумма степеней всех вершин графа равна удвоенному количеству ребер
¶ Виды графов
Граф называется связным, если существует путь, по которому можно достичь любой вершины.
Если не все вершины графа связаны, то его называют несвязным
Во взвешенном графе каждому ребру сопоставлен вес.
Веса интерпретируются как длины ребер, а длиной пути считается сумма весов составляющих его ребер.
Взвешенный граф
В ориентированном графе по каждому ребру можно проходить только в одном направлении.
Граф является двудольным тогда и только тогда, когда в нем нет цикла с нечетным количеством вершин.
Деревом называется связный граф без циклов.
¶ Представление графа
¶ Таблица смежности
Таблица смежности графа - это таблица, содержащая информацию о смежных вершинах для каждой вершины графа. Для каждой вершины эту информацию можно представить в виде списка её соседей, к которым она имеет прямое ребро.
В таблице смежности графа вершины графа сортируются по определенному критерию (например, по номеру вершины). Затем для каждой вершины указывается список всех вершин, которые прямо связаны ребром с данной вершиной.
Представление ниже показывает пример словаря, содержащего множества смежности. Заметьте, что вершины в нем обозначены символами.
N = {
'a': set('bcdef'),
'b': set('ce'),
'c': set('d'),
'd': set('e'),
'e': set('f'),
'f': set('cgh'),
'g': set('fh'),
'h': set('fg')
}
¶ Список смежности
Часто для представления графов используется список смежности. Его идея заключается в хранении для каждой вершины расширяемого массива (вектора), содержащего всех её соседей.
Для каждой вершины составляем список соседних вершин:
¶ Реализация на Python
Аннотация:
AdjNode - класс, представляющий узел списка смежности
data - данные, хранящиеся в узле
vertex - вершина графа
next - ссылка на следующий узел в списке смежности
Graph - класс, представляющий граф
vertices - количество вершин в графе
V - количество вершин в графе
graph - список списков смежности, представляющий граф
add_edge - метод добавления ребра в граф
node - узел графа
src - начальная вершина ребра
dest - конечная вершина ребра
----------------------------------------------------------------------------------------
class AdjNode:
def __init__(self, data):
self.vertex = data
self.next = None
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = [None] * self.V
def add_edge(self, src, dest):
node = AdjNode(dest)
node.next = self.graph[src]
self.graph[src] = node
node = AdjNode(src)
node.next = self.graph[dest]
self.graph[dest] = node
def print_graph(self):
for i in range(self.V):
print("Adjacency list of vertex {}\n head".format(i), end="")
temp = self.graph[i]
while temp:
print(" -> {}".format(temp.vertex), end="")
temp = temp.next
print(" \n")
¶ Реализация на С++
Аннотация:
addEdge - функция добавления ребра
vector adj[] - массив векторов, используемый для представления списка смежности графа
u и v - номера вершин в графе
printGraph - функция печати списка смежности графа
V - число вершин в графе
----------------------------------------------------------------------------------------
#include <bits/stdc++.h>
using namespace std;
void addEdge(vector<int> adj[], int u, int v)
{
adj[u].push_back(v);
adj[v].push_back(u);
}
void printGraph(vector<int> adj[], int V)
{
for (int v = 0; v < V; ++v) {
cout << "\n Adjacency list of vertex " << v
<< "\n head ";
for (auto x : adj[v])
cout << "-> " << x;
cout<<endl;
}
}
¶ Список инцидентности
Возьмем для примера следующий граф, где вершины обозначены латинскими буквами, а инцидентные им ребра - цифрами.
Далее составляем список инцидентности для данного графа:
В примере ниже для хранения списка инцидентности был использован стандартный тип данных словарь(dict). Ключи в словаре представляют вершины графа, а значения - списки инцидентных ребер.
Результат выполнения программы :
¶ Реализация на Python
Аннотация:
adj_list - словарь, представляющий список смежности графа
node - узел графа
edges - список ребер, соединяющих узел node с другими узлами графа
----------------------------------------------------------------------------------------
adj_list = {
'A': [1,2],
'B': [2,3,4],
'C': [1,3,5,6],
'D': [4,5,7],
'E': [6,7]
}
for node, edges in adj_list.items():
print(f"{node}{{{','.join(map(str, edges))}}}")
,
A{1,2}
B{2,3,4}
C{1,3,5,6}
D{4,5,7}
E{6,7}
В этом примере для хранения списка инцидентности был использован стандартный тип данных vector<vector<int>>. Внешний вектор хранит списки ребер для каждой вершины, а внутренний вектор - список ребер инцидентных с соответствующей вершиной.
Результатом выполнения программы будет:
¶ Реализация на C++
Аннотация:
vector adj_list - двумерный вектор, представляющий список смежности графа
adj_list.size() - возвращает количество строк в векторе
adj_list[].size() - возвращает количество элементов в строке вектора
----------------------------------------------------------------------------------------
#include <bits/stdc++.h>
using namespace std;
int main()
{
vector<vector<int>> adj_list = {
{1, 2},
{2, 3, 4},
{1, 3, 5, 6},
{4, 5, 7},
{6, 7}
};
for (int i = 0; i < adj_list.size(); i++) {
cout << char(i+'A') << "{";
for (int j = 0; j < adj_list[i].size(); j++) {
cout << adj_list[i][j];
if (j < adj_list[i].size()-1)
cout << ",";
}
cout << "}" << endl;
}
return 0;
}
,
A{1,2}
B{1,2,3}
C{1,2,5,6}
D{3,5,7}
E{6,7}
¶ Матрица инцидентности
Матрица инцидентности графа - это матрица, в которой каждая строка соответствует вершине графа, а каждый столбец - ребру. Значение в ячейке (i,j) равно единице, если вершина i инцидентна ребру j, иначе в ячейке стоит ноль.
a, b, c, d, e, f, g, h = range(8)
# a b c d e f g h
N = [[1,1,0,0,0,0,0,0], # a
[1,0,1,1,1,0,0,0], # b
[0,1,1,0,0,0,0,0], # c
[0,0,0,1,1,0,0,0], # d
[0,0,0,0,0,1,0,0], # e
[0,0,0,0,0,0,1,1], # f
[0,0,0,0,0,1,0,1], # g
[0,0,0,0,0,0,1,0]] # h
Инцидентность - свойство принадлежности ребра к вершине графа. Две вершины или два ребра не могут быть инцидентны.
Матрица инцидентности позволяет удобно хранить информацию о рёбрах графа и их связи с вершинами. Может быть использована для проверки связности графа и для решения задач, связанных с поиском путей и циклов в графе.
По сравнению с матрицей смежности, она занимает больше памяти и используется реже в практических приложениях.
¶ Матрицы смежности
Матрица смежности графа - это квадратная матрица, содержащая информацию о связях между вершинами графа. Каждой вершине сопоставляется строка и столбец в матрице.
Если вершины i и j связаны ребром, то в ячейке (i, j) матрицы ставится единица, в противном случае в ячейке ставится ноль. Для неориентированного графа матрица симметрична относительно главной диагонали, так как если вершина i соединена с вершиной j, то и вершина j соединена с вершиной i.
Матрица смежности позволяет удобно хранить информацию о связях между вершинами графа и обрабатывать её. Она может быть использована для проверки смежности вершин, поиска путей между вершинами, а также для поиска циклов в графе. Кроме того, матрица смежности может быть использована для визуализации графа.
a, b, c, d, e, f, g, h = range(8)
# a b c d e f g h
N = [[0,1,1,1,1,1,0,0], # a
[0,0,1,0,1,0,0,0], # b
[0,0,0,1,0,0,0,0], # c
[0,0,0,0,1,0,0,0], # d
[0,0,0,0,0,1,0,0], # e
[0,0,1,0,0,0,1,1], # f
[0,0,0,0,0,1,0,1], # g
[0,0,0,0,0,1,1,0]] # h
Ввод для матрицы смежности:
¶ Реализация на Python
Аннотация:
adjMat - матрица смежности графа
----------------------------------------------------------------------------------------
if __name__ == '__main__':
n, m = map(int, input().split())
adjMat = [[0 for i in range(n)]for j in range(n)]
for i in range(n):
u, v = map(int, input().split())
adjMat[u][v] = 1
adjMat[v][u] = 1
¶ Реализация на С++
Аннотация:
adjMat - матрица смежности графа
int adjMat[n + 1][n + 1] - создание матрицы смежности размером (n+1) x (n+1)
----------------------------------------------------------------------------------------
#include <iostream>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
int adjMat[n + 1][n + 1];
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adjMat[u][v] = 1;
adjMat[v][u] = 1;
}
return 0;
}
¶ Обход графа в глубину
Обход графа в глубину (DFS) - один из методов обхода графа. Стратегия поиска в глубину состоит том, чтобы идти "вглубь" графа, насколько это возможно.
Обход в глубину начинает с корневой вершины и идёт вглубь до тех пор, пока не будет достигнут конечный узел, или пока не будет достигнут конец некоторой ветви. Когда конец ветви достигнут, алгоритм возвращается на шаг назад и продолжает идти в других направлениях, пока все возможные пути не будут пройдены.
После завершения пути алгоритм делает шаг назад.
Если он может найти еще один уникальный путь из текущего узла, процесс повторяется.
Алгоритм продолжает двигаться по новым ветвям до тех пор, пока все вершины не будут посещены.
¶ Сложность алгоритма
Сложность алгоритма обхода в глубину равна , где n - число вершин, а m - число ребер, поскольку алгоритм обрабатывает каждую вершину и каждое ребро ровно один раз.
¶ Псевдокод
DFS(G, v):
Создать стек S
Поместить v на вершину стека S
Пока S не пустой:
Извлечь вершину u с вершины стека S
Если u не помечен:
Пометить u как посещенную вершину
Для каждой вершины w в списке смежности вершины u:
Если w не помечен:
Поместить w на вершину стека S
¶ Реализация на Python
Аннотация:
addEdge - метод добавления ребра в граф
DFSUtil - рекурсивный вспомогательный метод для обхода графа в глубину
DFS - метод для запуска обхода графа в глубину из заданной вершины
visited - посещенные вершины
neighbour - соседняя вершина текущей вершины
----------------------------------------------------------------------------------------
from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def addEdge(self, u, v):
self.graph[u].append(v)
def DFSUtil(self, v, visited):
visited.add(v)
print(v, end=' ')
for neighbour in self.graph[v]:
if neighbour not in visited:
self.DFSUtil(neighbour, visited)
def DFS(self, v):
visited = set()
self.DFSUtil(v, visited)
if __name__ == "__main__":
g = Graph()
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)
print("Following is DFS from (starting from vertex 2)")
g.DFS(2)
¶ Реализация на C++
Аннотация:
T - тип данных, используемый для вершин графа
visited - посещенные вершины при обходе графа
adj - хранение списка смежности графа
addEdge() - метод добавляющий ребро между вершинами
DFS() - метод обхода графа в глубину
----------------------------------------------------------------------------------------
template<typename T>
class Graph {
map<T, bool> visited;
map<T, list<T>> adj;
void addEdge(T v, T w);
void DFS(T v);
,
Graph<int> g;
,
#include <bits/stdc++.h>
using namespace std;
template<typename T>
class Graph {
public:
map<T, bool> visited;
map<T, list<T> > adj;
void addEdge(T v, T w);
void DFS(T v);
};
template<typename T>
void Graph<T>::addEdge(T v, T w)
{
adj[v].push_back(w);
}
template<typename T>
void Graph<T>::DFS(T v)
{
visited[v] = true;
cout << v << " ";
typename list<T>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFS(*i);
}
int main()
{
Graph<int> g;
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
cout << "Following is Depth First Traversal"
" (starting from vertex 2)
";
g.DFS(2);
return 0;
}
¶ Обход графа в ширину
При поиске в ширину ( breadth-first search, BFS) вершины графа посещаются в порядке возрастания расстояния от начальной вершины.
Поиск в ширину позволяет найти кратчайший путь от начальной вершины до всех остальных.
В процессе поиска в ширину мы посещаем вершины уровень за уровнем. Первыми посещаются вершины, отстоящие от начальной на расстояние 1 , затем - на расстояние 2 и т.д.
Процесс продолжается, пока не останется непосещённых вершин.
¶ Алгоритм обхода графа в ширину.
Обход в ширину начинает с узла и посещает соседние узлы на текущем уровне, затем перемещается на следующий уровень и продолжает поиск. Таким образом, на каждом уровне первыми просматриваются все соседние вершины, а затем их соседи и так далее.
¶ Вычислительная сложность алгоритма
Временная сложность обхода в ширину равна , где n - число вершин, а m - число ребер, поскольку алгоритм обрабатывает каждую вершину и каждое ребро ровно один раз.
¶ Псевдокод
BFS(G, v):
Создать очередь Q
Поместить v в очередь Q
Пометить v как посещенную вершину
Пока Q не пустой:
Извлечь из очереди Q вершину u
Для каждой вершины w в списке смежности вершины u:
Если w не помечен:
Пометить w как посещенную вершину
Поместить w в очередь Q
¶ Реализация на Python
Аннотация:
addEdge - добавление ребра в граф
BFS - обход графа в ширину
visited - посещенные вершины
queue - список очереди для обхода графа в ширину
defaultdict - создания словаря списков, где каждому ключу соответствует список
----------------------------------------------------------------------------------------
from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def addEdge(self, u, v):
self.graph[u].append(v)
def BFS(self, s):
visited = [False] * (max(self.graph) + 1)
queue = []
queue.append(s)
visited[s] = True
while queue:
s = queue.pop(0)
print(s, end=" ")
for i in self.graph[s]:
if visited[i] == False:
queue.append(i)
visited[i] = True
¶ Реализация на C++
Аннотация:
template - создание шаблона
adj - список смежности графа
addEdge - метод добавления вершины
BFS - метод обхода в ширину
visited - вектор уже посещенных вершин
queue - очередь непройденных вершин графа
----------------------------------------------------------------------------------------
#include<bits/stdc++.h>
using namespace std;
template<typename T>
class Graph {
T V;
vector<list<T> > adj;
public:
Graph(T V);
void addEdge(T v, T w);
void BFS(T s);
};
template<typename T>
Graph<T>::Graph(T V)
{
this->V = V;
adj.resize(V);
}
template<typename T>
void Graph<T>::addEdge(T v, T w)
adj[v].push_back(w);
template<typename T>
void Graph<T>::BFS(T s)
{
vector<bool> visited;
visited.resize(V, false);
list<T> queue;
visited[s] = true;
queue.push_back(s);
while (!queue.empty()) {
s = queue.front();
cout << s << " ";
queue.pop_front();
for (auto adjacent : adj[s]) {
if (!visited[adjacent]) {
visited[adjacent] = true;
queue.push_back(adjacent);
}
}
}
}
Ключевое отличие между этими двумя алгоритмами заключается в том, что обход в глубину пытается достичь максимальной глубины поиска в каждый момент времени, в то время как обход в ширину сначала стремится находить ближайшие элементы.
Кроме того, используемые структуры данных для хранения информации о посещенных вершинах различны для обоих алгоритмов. Обход в глубину использует стек для хранения текущего пути, а обход в ширину использует очередь для хранения вершин, ожидающих обработки.
¶ Вывод
Когда использовать графы:
- Когда вам нужно представить и проанализировать отношения между различными объектами или сущностями.
- Когда вам нужно выполнить сетевой анализ.
- Когда вам нужно определить ключевых игроков, влиятельных лиц или узкие места в системе.
- Когда вам нужно сделать прогнозы или рекомендации.
- Моделирование сетей: графы обычно используются для моделирования различных типов сетей, таких как социальные сети, транспортные сети и компьютерные сети. В этих случаях вершины представляют узлы в сети, а ребра представляют связи между ними.
- Поиск путей: графы часто используются в алгоритмах поиска путей между двумя вершинами в графе, таких как алгоритмы поиска кратчайшего пути. Например, графики можно использовать для поиска кратчайшего маршрута между двумя городами на карте или наиболее эффективного способа перемещения между несколькими пунктами назначения.
- Представление отношений данных. Графики можно использовать для представления отношений между объектами данных, например, в базе данных или структуре данных. В этих случаях вершины представляют объекты данных, а ребра представляют отношения между ними.
- Анализ данных. Графики можно использовать для анализа и визуализации сложных данных, например, в алгоритмах кластеризации данных или моделях машинного обучения. В этих случаях вершины представляют точки данных, а ребра представляют сходства или различия между ними.