Материал: Вопросы к экзамену

Использование вершины происходит с помощью просмотра сразу всех еще непросмотренных соседей этой вершины.

1PROCEDURE WS(v);

{поиск в ширину в графе с началом в вершине v; переменные НОВЫЙ, СПИСОК - глобальные}

2BEGIN

3ОЧЕРЕДЬ := 0; ОЧЕРЕДЬ <= v; НОВЫЙу := false;

4WHILE ОЧЕРЕДЬ :Ф 0 DO begin

5Р<= ОЧЕРЕДЬ; посетить р;

6FOR tСПИСОКр DO

7IF НОВЫЙt THEN BEGIN

8ОЧЕРЕДЬ <= t; НОВЫЙt := false

9END

10END

11END

Вызов процедуры WS(v) приводит к посещению всех вершин компоненты связности графа, содержащей вершину v, причем каждая вершина просматривается ровно один раз. Вычислительная сложность алгоритма также имеет порядок m+n, т.к. каждая вершина помещается в очередь и удаляется из очереди в точности один раз, а число итераций цикла 6, очевидно, будет иметь порядок числа ребер графа.

Поиск в графе в ширину может быть использован для нахождения пути между фиксированными вершинами v и t. Для этого достаточно начать поиск в графе с ве ршины v и вести его до вершины t.

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

помечены как непосещенные. Поиск в глубину начинается с выбора начальной вершины v графа G, и эта вершина помечается как посещенная. Затем для каждой вершины, смежной с вершиной v и которая не посещалась ранее, рекурсивно применяется поиск в глубину. Когда все вершины, которыеможнодостичьизвершиныv,будут«удостоены»посещения,поискзаканчивается.Если некоторые вершины остались не посещенными, то выбирается одна из них и поиск повторяется. Этот процесс продолжается до тех пор, пока обходом не будут охвачены все вершины орграфа

G.

Этот метод обхода вершин орграфа называется поиском в глубину, поскольку поиск непосещенных вершин идет в направлении вперед (вглубь) до тех пор, пока это возможно. Например, пусть x – последняя посещенная вершина. Для продолжения процесса выбирается какая-либо нерассмотренная дуга x → y, выходящая из вершины x. Если вершина y уже посещалась, то ищется другая вершина, смежная с вершиной x. Если вершина y ранее не посещалась, то она помечается какпосещенная и поиск начинаетсязаново от вершины y. Пройдя все пути, которые начинаются в вершине y, возвращаемся в вершину x, т. е. в ту вершину, из которой впервые была достигнута вершина y. Затем продолжается выбор нерассмотренных дуг, исходящих из вершины x, и так до тех пор, пока не будут исчерпаны все эти дуги.

26

Для представления вершин, смежных с вершиной v, можно использовать список смежных, а для определения вершин, которые ранее посещались, – массив flag:

#define n 9

Bool flag[n]={false};

Чтобы применить эту процедуру к графу, состоящему изn вершин, надо сначала присвоить всем элементам массива flag значение false , затем начать поиск в глубину для каждой вершины, помеченной какfalse.

Поиск в глубину для полного обхода графа сn вершинами и m дугами требует общего времени порядка O(max(n, m)). Поскольку обычно m ≥ n, то получается O(m).

#include <stdio.h> #include <conio.h> #define n 9

int A[n][n];

bool flag[n] = {false};

void DFS(int prev, int cur)

{

if(prev>=0)

printf("%d - %d\n",prev+1,cur+1); flag[cur] = true;

for(int i=0;i<n;i++)

if(flag[i]==false && A[cur][i]==1) DFS(cur,i);

}

int _tmain(int argc, _TCHAR* argv[])

{

FILE *f = fopen("graph.txt","r"); for(int i=0;i<n;i++)

for(int j=0;j<n;j++) fscanf(f,"%d",&A[i][j]);

fclose(f); int FST;

printf("Input number of list vertex: "); scanf("%d",&FST); DFS(-1,FST-1);

getch(); return 0;

}

27

Алгоритм 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