Алгоритм DFS(G)

1.For each vV do Mark[v]<-0

2.For vV do

3.If Mark[v]=0 then dfs(v)

Dfs(v)

1.Mark[v]<-1

2.Обработка вершины v

3.For each wV, смежные с v do

4.If Mark[w]=0 then dfs(w)

5.End for.

33. Графы. Поиск кратчайшего пути. Алгоритм Дейкстры.

См. 32 вопрос +

Зада́ча о кратча́йшем пути́— задача поиска самого короткого пути (цепи) между двумя точками (вершинами) на графе, в которой минимизируется сумма весов рёбер, составляющих путь.

Алгори́тм Де́йкстры (Dijkstra’s algorithm) — алгоритм на графах, находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса.

функция D(i) – массив значений весов ребер

функция P(s, i) – функция возвращающая вес ребер между начальным (s) и другими вершинами, если такого ребра нет, возвращает бесконечность.

W – множество обработанных вершин

КЦ

Алгоритм Dijkstra (G,A,S)

1)for each v V do d[v];

2)d[s]0; //путь до вершины S

28

3)S; //множество вершин с известным расстоянием

4)tv; //множество вершин с не известным расстоянем

5)while T0 do;

6)d[w]=min {d[p], p T};

7)SSV{w}; TT-{w};

8)for each v T do;

9)if d[v] > d[w]+a[w,v] then;

10)d[v] d[w] + a[w,v];

11)end for;

12)end while;

13)return d.

d[S]=0; d[A]=; d[B]=; d[C]=; d[D]=; d[E]=; S; T={S, A, B, C, D, E};

d[A]=min{d[A], d[S] + a[S,A]=4}; d[B]=min{d[B], d[S] + a[S,B]=9};

d[C]=3; – Минимальное значение переносим во множество S; d[D]=;

d[E]=;

S={S,C} T={A,B,D,E};

Пересчитываем

d[A]=min{d[A], d[C] + a[C,A]}=min{4, 3 + } = 4; d[B]=min{d[B], d[C] + a[C,B]}=min{9, 3 + }=9; d[D]=min{d[D], d[C] + a[C,D]}=min{, 3 + 3}=6; d[E] =;

S={S,C,A} T={B,D,E};

Пересчитываем

d[B]=min{d[B], d[А] + a[А,B]}=min{9, 3 + 4}=7; d[D]=min{d[D], d[А] + a[А,D]}=min{6, 4 + 2}=6; d[E] =;

S={S,C,A,D} T={B,E};

Пересчитываем

d[B]=min{d[B], d[D] + a[D,B]}=min{7, 6 + }=7;

d[E] = min{d[E], d[D] + a[D,E]}=8; S={S,C,A,D,B} T={E};

Пересчитываем

d[E] = min{d[E], d[B] + a[B,E]}=min{9,8}=8; S={S,C,A,D,B,E} T=;

34.Графы. Построение минимального остовного дерева. Алгоритм Прима.

См. 32 вопрос +

29

Минимальное остовное дерево (или минимальное покрывающее дерево) в связанном взвешенном неориентированном графе — это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер.

Существует несколько алгоритмов для нахождения минимального остовного дерева. наиболее известные из них это Алгоритм Прима и Алгоритм Краскала.

Алгоритм Прима — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа.

На вход алгоритма подаётся связный неориентированный граф. Для каждого ребра задаётся его стоимость.

Сначала берётся произвольная вершина и находится ребро, инцидентное данной вершине и обладающее наименьшей стоимостью. Найденное ребро и соединяемые им две вершины образуют дерево. Затем, рассматриваются рёбра графа, один конец которых — уже принадлежащая дереву вершина, а другой — нет; из этих рёбер выбирается ребро наименьшей стоимости. Выбираемое на каждом шаге ребро присоединяется кдереву. Ростдерева происходит до тех пор, пока не будут исчерпаны все вершины исходного графа.

Результатом работы алгоритма является остовное дерево минимальной стоимости.

Алгоритм:

Отсортировать список рёбер.Взять первую вершину из списка рёбер. Записать вершину в массив обработанных вершин.

ЦИКЛ ПОКА (Все вершины не занесены в массив обработанных) ЦИКЛ ПОКА (Не конец списка рёбер и вершина не обработана)

Выделить первое ребро из списка, соединяющего обработанную вершину с необработанной.

Записать необработанную вершину в массив обработанных. Записать данное ребро в массив с результатами.

Удалить данное ребро из списка рёбер.

КЦ

КЦ

35. Графы. Построение минимального остовного дерева. Алгоритм Крускала.

См. 32 вопрос + 33 вопрос + Алгоритм Краскала/Крускала/Крушкала/Жозефа/Йосефа/Йюсуфа/…/

Алгоритм Краскала — эффективный алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа, общая идея алгоритма состоит в следующем:

1.Упорядочить все ребра по возрастанию (неубыванию) весов,

2.Присвоить вершинам графа различные цвета (номера).

3.ЦИКЛ ПОКА не кончились ребра

Рассмотреть очередное ребро ЕСЛИ концы ребра окрашены в разные цвета, ТО

30

добавить ребро в стягивающее дерево и перекрасить все вершины (в старом графе),номеркоторыхсовпадаетсбольшимномеромиз концов этогоребра

КОНЕЦ ЕСЛИ КОНЕЦ ЦИКЛА

31