👑26. Динамические структуры данных. Графы. Алгоритмы обхода графа в ширину и глубину. Примеры.

Динамическая структура данных

• Это структуры данных, память под которые выделяется и освобождается по мере необходимости. Примером таких структур можно считать деревья, списки, очередь, стек.

Граф

Это абстрактный тип данных, который предназначен для реализации понятий неориентированного и ориентированного графа из области теории графов в математике.

Структура данных графа состоит из конечного набора вершин вместе с набором неупорядоченных пар этих вершин для неориентированного графа или набором упорядоченных пар для ориентированного графа.

Область применения графов

• Геолокация

• Планирование процессов

• Компьютерные сети

• Структура программы

• Химические соединения

• Связи между людьми

Основные понятия теории графов

Ориентированный граф - G(V, E) - пара из V(конечного множества) и Е(подмножества декартового произведения множества V*V).

Неориентированный граф - ребра есть неупорядоченные пары. Если для любой пары вершин существует путь, граф неориентированный.

Взвешенный граф - граф, в котором каждому ребру приписан вес. С(U, V)

Взвешенный граф

Вершины графа - элементы множества V.

Ребра графа - элементы множества Е.

Петля - ребро из вершины Vi в само себя.

Вершины Vi и Vj смежны, если между ними имеется связь (Vi, Vj).

Путем из V0 в Vn называется последовательность рёбер таких, что Е1 = (V0, V1), E2 = (V1, V2)... En = (Vn-1, Vn)

Простым путем называется путь, в котором все вершины попарно различны.

Длина пути - количество рёбер в пути.

Цикл - путь, в котором V0=Vn.

Связанная компонента вершины V - множество вершин неориентированного графа до которых существует путь из V.

Обход графа. Поиск в ширину(BFS)

Поиск в ширину от исходной вершины - просмотр всех вершин графа в порядке возрастания расстояния от исходной вершины.

Алгоритм работает следующим образом:

1. Начните с размещения любой вершины графа в конце очереди.

2. Возьмите передний элемент очереди и добавьте его в список посещенных.

3. Создайте список смежных узлов этой вершины. Добавьте те, которых нет в списке посещенных, в конец очереди.

4. Продолжайте повторять шаги 2 и 3, пока очередь не опустеет.

Пример BFS

Давайте посмотрим, как алгоритм «поиска в ширину» работает на примере. Мы используем неориентированный граф с 5 вершинами.

Мы начнем с вершины 0, алгоритм BFS начинается с помещения его в список посещенных и размещения всех смежных вершин в стеке.

Затем мы посещаем элемент в начале очереди, то есть 1, и переходим к соседним узлам. Так как 0 уже был посещен, мы посещаем 2.

У вершины 2 есть соседняя не посещенная вершина 4, поэтому мы добавляем ее в конец очереди и посещаем 3, которая находится в начале очереди.

В очереди остается только 4, поскольку единственный соседний узел с 3, то есть 0, уже посещен. Мы посещаем вершину 4.

Поскольку очередь пуста, мы завершили обход в ширину графика.

Особенности алгоритма

1. Каждая вершина обрабатывается не более 1 раза

2. Легко найти кратчайший путь

3. Легко найти обратный путь

Сложность алгоритма: О(|V|+|E|)

Алгоритм реализован на псевдокоде. Для реализации на Си смотрите здесь.

create a queue Q 
mark v as visited and put v into Q 
while Q is non-empty 
    remove the head u of Q 
    mark and enqueue all (unvisited) neighbours of u

Обход в глубину (Depth-First Search, DFS)

Список смежности - это один из способов представления графа:

список смежности для данного графа

Для каждой вершины (первый столбик) мы составляем список смежных ей вершин, то есть список вершин с которыми у данной есть общие ребра(ребро инцидентное данным вершинам).

Алгоритм поиска

Начнем мы с вершины “0”. В первую очередь алгоритм поиска в глубину поместит ее саму в список “Пройденные” (на изображении “Visited”), а ее смежные вершины — в стек.

Выберите элемент (вершину) и поместите его в список “Пройденные”.

Затем мы берем следующий элемент сверху стека, т.е. к вершину “1”, и переходим к ее соседним вершинам. Поскольку вершина “0” уже пройдена, следующая вершина “2”.

Обход элемента на вершине стека.

Вершина “2” смежна непройденной вершине “4”, следовательно мы добавляем ее наверх стека и проходим ее.

Вершина “2” смежна непройденной вершине “4”, следовательно мы помещаем ее в верх стека.

Добавляем вершину “4” в список “Пройденные” после прохождения.

После того, как мы пройдем последний элемент (вершину “3”), в стеке не останется непройденных смежных вершин, и таким образом мы завершили обход графа в глубину.

После проверки всех смежных вершин для вершины “3” стек остался пустым, а значит алгоритм обхода графа в глубину завершил свою работу.

⭐ Код реализован на С++! Реализован только сам алгоритм, полный код здесь.

void Graph::DFS(int vertex) {
  visited[vertex] = true;
  list<int> adjList = adjLists[vertex];
 
  cout << vertex << " ";
 
  list<int>::iterator i;
  for (i = adjList.begin(); i != adjList.end(); ++i)
    if (!visited[*i])
      DFS(*i);
}