Алгоритмы и структуры данных. Семестр 2. Лекция 1. Графы

Что такое граф?
Граф — это структура, представляющая собой набор объектов, в котором некоторые пары объектов в некотором смысле «связаны».
Объекты, называемые вершинами (также называемыми узлами или точками).
Каждая из связанных пар вершин называется ребром.

Что такое граф?
Например:
Вершины (желтые кружки) is V = {1,2,3,4,5}
Ребра (черные линии) это пары вершин, которые связаны. В этом случае ребра :
E = {(1, 2), (1, 3), (2, 4), (2, 5), (3, 4), (4, 5)}
Мы также определяем граф как пару V и E. Если коротко, то G = (V, E).
Мы будем использовать это обозначение.

Что такое граф?
Параллельные вершины :
Два или более ребра, соединяющие одну и ту же пару вершин.
В примере вершины 1 и 2 соединены с 2 ребрами.
Петля
Ребро, которое начинается и заканчивается в одной вершине.

Что такое граф?
Типы графов
Если ребра в графе ориентированы, т. е. указывают только в одном направлении, граф называется ориентированным графом или орграфом.
Если ребра в графе не имеют направления, граф называется неориентированным графом.

Граф, в котором каждое ребро имеет числовой «вес», называется взвешенным графом.
Что такое граф?
Типы графов

Что такое граф?
Терминология
Вершины u и v называются смежными, если u и v соединены некоторым ребром.
Количество ребер, инцидентных вершине, называется степенью вершины или deg(v). Вершина инцидентна ребру, если эта вершина является одной из двух вершин, которые соединяет ребро. Например, град(3) = 3
Листовая вершина — это вершина с deg(v) = 1, например, 5 — листовая вершина.
Изолированная вершина — это вершина с deg(v) = 0 , например, 6 — изолированная вершина.

Что такое граф?
Лемма о рукопожатии

Что такое граф?
Терминология

Графическое представление

Что такое граф?
Представление
Нужно представить график в компьютере.
3 обычных вида представления։
Список ребер
Матрица смежности
Список смежности

Что такое граф?
Представление. Список ребер
Простое перечисление ребер :
Для этого примера список узлов
{1, 2}, {2, 1}
{1, 3}, {3, 1}
{2, 3}, {3, 2}
{2, 5}, {5, 2}
{3, 4}, {4, 3}
Можно использовать 2 массива от и до.
Может использоваться массив пар.

Что такое граф?
Представление: Список смежности

Что такое граф?
Представление։ Матрица смежности
Если между вершинами i и j есть ребро, то (i, j)-я матрица устанавливается в true, а в противном случае - в false:
Для этого примера матрица смежности
Можно использовать массив массивов.

Что такое граф?
Представление. Ориентированный граф
В случае ориентированного графа представление остается прежним, но ребра добавляются только в одном направлении.
Например, матрица соединений для ориентированного графа будет :
Обратите внимание, что для неориентированного графа (i, j) всегда равно (j, i). В случае направленного такого правила нет.

Breadth First Search (BFS)
Поиск в ширину

Breadth First Search (BFS)
BFS также является методом обхода графа.
Алгоритм:
BFS(v)
{
добавить v в очередь q
пока q не пусто
взять первую вершину u из q
удалить первую вершину из q
пометить u как посетившую
для всех непосещенных смежных вершин w из u
добавить w в q
}

Breadth First Search (BFS)
Посещенные вершины : {}
Очередь: {}
Текущая вершина : -
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти
1
2
4
6
7
8
5
3

Breadth First Search (BFS)
Посещенные вершины : {}
Очередь : {1}
Текущая вершина : -
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1}
Очередь : {}
Текущая вершина : 1
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1}
Очередь : {}
Текущая вершина : 1
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1}
Очередь : {2, 4}
Текущая вершина: 1
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1}
Очередь : {2, 4}
Текущая вершина: 1
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1}
Очередь : {2, 4}
Текущая вершина: -
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2}
Очередь : {4}
Текущая вершина : 2
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2}
Очередь : {4}
Текущая вершина : 2
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2}
Очередь : {4, 6, 7}
Текущая вершина : 2
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2}
Очередь : {4, 6, 7}
Текущая вершина : 2
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2}
Очередь : {4, 6, 7}
Текущая вершина : -
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4}
Очередь : {6, 7}
Текущая вершина : 4
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4}
Очередь : {6, 7}
Текущая вершина: 4
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4}
Очередь : {6, 7, 5}
Текущая вершина: 4
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4}
Очередь : {6, 7, 5}
Текущая вершина : 4
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4}
Очередь : {6, 7, 5}
Текущая вершина : -
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6}
Очередь : {7, 5}
Текущая вершина : 6
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6}
Очередь : {7, 5}
Текущая вершина : 6
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6}
Очередь : {7, 5}
Текущая вершина : 6
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6}
Очередь : {7, 5}
Текущая вершина : -
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6, 7}
Очередь : {5}
Текущая вершина : 7
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6, 7}
Очередь : {5}
Текущая вершина : 7
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6, 7}
Очередь : {5, 3}
Текущая вершина : 7
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6, 7}
Очередь : {5, 3}
Текущая вершина : 7
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6, 7}
Очередь : {5, 3}
Текущая вершина : -
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6, 7, 5}
Очередь : {3}
Текущая вершина : 5
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6, 7, 5}
Очередь : {3}
Текущая вершина : 5
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6, 7, 5}
Очередь : {3, 8}
Текущая вершина : 5
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6, 7, 5}
Очередь : {3, 8}
Текущая вершина : 5
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6, 7, 5}
Очередь : {3, 8}
Текущая вершина : -
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6, 7, 5, 3}
Очередь : {8}
Текущая вершина : 3
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6, 7, 5, 3}
Очередь : {8}
Текущая вершина : 3
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6, 7, 5, 3}
Очередь : {8}
Текущая вершина : 3
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6, 7, 5, 3}
Очередь : {8}
Текущая вершина : -
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6, 7, 5, 3, 8}
Очередь : {}
Текущая вершина : 8
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6, 7, 5, 3, 8}
Очередь : {}
Текущая вершина : 8
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6, 7, 5, 3, 8}
Очередь : {}
Текущая вершина : 8
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6, 7, 5, 3, 8}
Очередь : {}
Текущая вершина : -
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6, 7, 5, 3, 8}
Очередь : {}
Текущая вершина : -
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)

Depth First Search (DFS)
Поиск в глубину

Depth First Search (DFS)
Посещенные вершины : {}
Стек: {}
Текущая вершина : -
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти
1
2
4
6
7
8
5
3

Depth First Search (DFS)
Посещенные вершины : {}
Стек : {1}
Текущая вершина : -
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Depth First Search (DFS)
Посещенные вершины : {1}
Стек : {}
Текущая вершина : 1
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Depth First Search (DFS)
Посещенные вершины : {1}
Стек : {}
Текущая вершина : 1
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Depth First Search (DFS)
Посещенные вершины : {1}
Стек : {2, 4}
Текущая вершина: 1
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Depth First Search (DFS)
Посещенные вершины : {1}
Cтек : {2, 4}
Текущая вершина: 1
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Depth First Search (DFS)
Посещенные вершины : {1}
Стек : {2, 4}
Текущая вершина: -
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Depth First Search (DFS)
Посещенные вершины : {1, 2}
Стек : {4}
Текущая вершина : 2
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Depth First Search (DFS)
Посещенные вершины : {1, 2}
Стек : {6, 7, 4}
Текущая вершина : 2
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Depth First Search (DFS)
Посещенные вершины : {1, 2}
Стек : {6, 7, 4}
Текущая вершина : 2
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Depth First Search (DFS)
Посещенные вершины : {1, 2}
Стек : {6, 7, 4}
Текущая вершина : 2
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Depth First Search (DFS)
Посещенные вершины : {1, 2}
Стек : {6, 7, 4}
Текущая вершина : -
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Depth First Search (DFS)
Посещенные вершины : {1, 2, 6}
Стек : {7, 4}
Текущая вершина : 6
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Depth First Search (DFS)
Посещенные вершины : {1, 2, 6, 7}
Стек : {3, 4}
Текущая вершина : 7
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Depth First Search (DFS)
Посещенные вершины : {1, 2, 6, 7, 3}
Стек : {4}
Текущая вершина : 3
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Depth First Search (DFS)
Посещенные вершины : {1, 2, 6, 7, 3, 4}
Стек : {5}
Текущая вершина: 4
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Depth First Search (DFS)
Посещенные вершины : {1, 2, 6, 7, 3, 4, 5}
Стек : {8}
Текущая вершина : 5
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Depth First Search (DFS)
Посещенные вершины : {1, 2, 6, 7, 3, 4, 5}
Стек : {}
Текущая вершина : 8
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Depth First Search (DFS)
Посещенные вершины : {1, 2, 6, 7, 3, 4, 5, 8}
Очередь : {}
Текущая вершина : -
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Depth First Search (DFS)

Алгоритм Дейкстры

Э́дсгер Ви́бе Де́йкстра (11.05.1930— 6.08.2002) — нидерландский учёный, труды которого оказали влияние на развитие информатики и информационных технологий, является одним из разработчиков концепции структурного программирования и других идей, лауреат премии Тьюринга 1972г.
Известность Дейкстре принесли его работы в области применения математической логики при разработке компьютерных программ, идея применения «семафоров» для синхронизации процессов в многозадачных системах, а так же разработка алгоритма нахождения кратчайшего пути на взвешенном графе без ребер отрицательного веса.
Алгоритм Дейкстры

Выбрать начальную вершину, присвоить стоимость пути до нее – 0, остальным вершинам ∞;
Все вершины являются не выделенными;
Объявить первую вершину текущей;
Стоимости путей до всех невыделенных вершин находятся след. образом: стоимость пути до невыделенной вершины есть минимальное число из стоимости старого пути до данной вершины, равное сумме стоимости пути до текущей вершины и веса ребра соединяющего текущую и невыделенную вершины.
Среди невыделенных вершин выбирается вершина с минимальной стоимостью пути до нее. Если такой вершины нет (стоимость путей до всех вершин равна ∞), то путь не существует и алгоритм завершается, иначе текущей вершиной становится найденная, и она же выделяется.
Если все вершины являются выделенными (до всех них найден кратчайший путь), то алгоритм завершается, иначе переход на шаг 4.
Последовательность шагов

Нахождение кратчайшего пути в неориентированном графе
Дан неориентированный граф без ребер отрицательного веса. Необходимо найти в нем кратчайшие пути из вершины A до всех остальных вершин.

Нахождение кратчайшего пути в неориентированном графе
Шаги 1-3. Выберем вершину А в качестве первой, выделим ее и присвоим ей стоимость пути до нее равную 0, остальным же вершинам присвоим стоимость равную ∞.

Нахождение кратчайшего пути в неориентированном графе
Шаг 4. Для каждой невыделенной вершины выполним вычисление: суммируем стоимость пути до текущей вершины и вес ребра соединяющего ее с невыделенной вершиной. Если эта сумма меньше стоимости пути до невыделенной вершины, то присваиваем найденную стоимость невыделенной вершине, иначе, продолжаем считать прежнюю стоимость пути до невыделенной вершины минимальной.
0+5=5 < ∞ ? Да

Нахождение кратчайшего пути в неориентированном графе
Шаг 4. Для каждой невыделенной вершины выполним вычисление: суммируем стоимость пути до текущей вершины и вес ребра соединяющего ее с невыделенной вершиной. Если эта сумма меньше стоимости пути до невыделенной вершины, то присваиваем найденную стоимость невыделенной вершине, иначе, продолжаем считать прежнюю стоимость пути до невыделенной вершины минимальной.
0+5=5 < ∞ ? Да
0+2=2 < ∞ ? Да

Нахождение кратчайшего пути в неориентированном графе
Шаг 5. Среди невыделенных вершин выбирается вершина с минимальной стоимостью пути до нее. Если такой вершины нет (стоимость путей до всех вершин равна ∞), то путь не существует и алгоритм завершается, иначе текущей вершиной становится найденная, и она же выделяется

Нахождение кратчайшего пути в неориентированном графе
2+2=4 < 5 ? Да
Шаг 4. Для каждой невыделенной вершины выполним вычисление: суммируем стоимость пути до текущей вершины и вес ребра соединяющего ее с невыделенной вершиной. Если эта сумма меньше стоимости пути до невыделенной вершины, то присваиваем найденную стоимость невыделенной вершине, иначе, продолжаем считать прежнюю стоимость пути до невыделенной вершины минимальной.

Нахождение кратчайшего пути в неориентированном графе
2+2=4 < 5 ? Да
Повторяем шаг 4 для новой вершины
2+10=12 < ∞ ? Да

Нахождение кратчайшего пути в неориентированном графе
2+2=4 < 5 ? Да
Повторяем шаг 4 для новой вершины
2+10=12 < ∞ ? Да
2+7=9 < ∞ ? Да

Нахождение кратчайшего пути в неориентированном графе
Повторяем шаг 5 для выделения новой вершины с минимальной стоимостью пути

Нахождение кратчайшего пути в неориентированном графе
Повторяем шаг 4 для новой вершины
4+3=7 < 12 ? Да

Нахождение кратчайшего пути в неориентированном графе
Повторяем шаг 4 для новой вершины
4+3=7 < 12 ? Да
4+2=6 < 9 ? Да

Нахождение кратчайшего пути в неориентированном графе
Повторяем шаг 5 для выделения новой вершины с минимальной стоимостью пути

Нахождение кратчайшего пути в неориентированном графе
Повторяем шаг 4 для новой вершины
6+6=12 < ∞ ? Да

Нахождение кратчайшего пути в неориентированном графе
Повторяем шаг 4 для новой вершины
6+6=12 < ∞ ? Да
6+4=10 < ∞ ? Да

Нахождение кратчайшего пути в неориентированном графе
Повторяем шаг 5 для выделения новой вершины с минимальной стоимостью пути

Нахождение кратчайшего пути в неориентированном графе
Повторяем шаг 4 для новой вершины
7+5=12 < 10 ? Нет

Нахождение кратчайшего пути в неориентированном графе
Повторяем шаг 4 для новой вершины
7+5=12 < 10 ? Нет
7+5=12 < 12 ? Нет

Нахождение кратчайшего пути в неориентированном графе
Повторяем шаг 5 для выделения новой вершины с минимальной стоимостью пути

Нахождение кратчайшего пути в неориентированном графе
Повторяем шаг 4 для новой вершины
10+2=12 < ∞ ? Да

Нахождение кратчайшего пути в неориентированном графе
Повторяем шаг 5 для выделения новой вершины с минимальной стоимостью пути

Нахождение кратчайшего пути в неориентированном графе
Повторяем шаг 4 для новой вершины
12+3=15 < 12 ? Нет

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

Результаты работы алгоритма
Были найдены следующие кратчайшие пути:
A → A = 0;
A → B = 4;
A → C = 2;
A → D = 7;
A → E = 6;
A → F = 12;
A → G = 10;
A → H = 12;