Викиконспекты - Вклад участника [ru]

Алгоритмы на деревьях

2013-12-17T15:04:56Z

217.118.78.98:

__TOC__
== Определение ==

'''Диаметр дерева''' - максимальная длина кратчайшего пути между любыми двумя вершинами.
Алгоритм в этой статье находит диаметр в дереве,причём очень простой реализацией и низким временем работы.

== Алгоритм ==
Возьмём любую вершину <tex> v </tex> и найдём расстояния до всех других вершин.

d = min{<tex> v </tex>,<tex> u </tex> <tex> \subset graph, </tex> <tex> v \ne u </tex>} dist(<tex> v, u </tex>)

Возьмём вершину <tex> u </tex> такую,что d[u] >= d[t] для любого t.Снова найдём расстояние от <tex>u</tex> до всех остальных вершин.Самое большое расстояние - диаметр дерева.
Расстояние до остальных вершин удобно искать алгоритмом BFS.

== Реализация ==

int diameterTree(graph g)
{
v = u = w = 0;
bfs(g,v); // заполняет массив d[n] кратчайшими расстояниями до всех вершин.
for(i = 0; i < n; i++)
if (d[i] > d[u])
u = i;
bfs(g,u);
for(i = 0; i < n; i++)
if (d[i] > d[w])
w = i;
return d[w];
}

== Обоснование корректности ==
Будем пользоваться свойством,что в любом дереве >= 2 листов(имеют степень один).

{{Теорема
|statement=
Искомое расстояние - есть расстояние между двумя листами.
|proof=
Пусть нет, пусть искомое расстояние - есть расстояние между вершинами <tex>a,b</tex> где <tex>b</tex> - не является листом. Т.к. b не является листом, то значит её степень <tex>></tex> 1 => из неё существует ребро в непосещенную вершину (дважды посетить вершину <tex>b</tex> мы не можем). Лемма доказана.
}}

Запустив BFS от произвольной вершины. Мы получим дерево BFS.

{{Теорема
|statement=
В дереве BFS не существует ребер между вершинами из разных поддеревьев некоторого из общего предка.
|proof=
Такое же как у дерева dfs.
}}

Мы свели задачу к нахождению вершины <tex>w</tex>, такой, что сумма глубин поддеревьев максимальна.

Докажем, что одно из искомых поддеревьев содержит самый глубокий лист.
Пусть нет, тогда взяв расстояние от <tex>w</tex> до глубочайшего листа мы можем улучшить ответ.

Таким образом мы доказали, что нам нужно взять вершину <tex>u</tex> с наибольшей глубиной после первого bfs, очевидно что ей в пару надо сопоставить вершину <tex>w</tex> , что dist(u, w) - <tex>max</tex> . Очевидно, что проблема решается запуском bfs из <tex>u</tex>.

'''Оценка производительности:'''

Все операции кроме bfs - О(1).
BFS работает линейное время,запускаем мы его 2 раза.Получаем O(V+E).

Обход в ширину

2012-03-22T22:18:45Z

217.118.78.98: /* Ссылки */

'''Обход в ширину''' ('''Поиск в ширину''', '''BFS''', '''Breadth-first search''') — один из простейших алгоритмов обхода графа, являющийся основой для многих важных алгоритмов для работы с графами.

== Алгоритм ==

=== Общая идея ===

Пусть задан невзвешенный граф <tex> G = (V, E) </tex>, в котором выделена исходная вершина <tex>s</tex>. Для алгоритма нам потребуются очередь, которая сначала содержит только <tex> s </tex>, и множество посещенных вершин <tex> X </tex>, которое изначально тоже содержит только <tex> s </tex>. На каждом шаге алгоритм вынимает из начала очереди вершину, рассматривает все исходящие из нее ребра и добавляет все связанные с ней непосещенные вершины в <tex> X </tex> и в конец очереди. Если очередь пуста, то алгоритм завершает работу.

Поиск в ширину также может построить дерево поиска в ширину. Изначально оно состоит из одного корня <tex> s </tex>. Когда мы добавляем непосещенную вершину в очередь, то добавляем ее и ребро, по которому мы до нее дошли, в дерево. Поскольку каждая вершина может быть посещена не более одного раза, она имеет не более одного родителя. После окончания работы алгоритма для каждой достижимой из <tex> s </tex> вершины <tex> t </tex> путь в дереве поиска в ширину соответствует кратчайшему пути от <tex> s </tex> до <tex> t </tex> в <tex> G </tex>.

Также можно для каждой вершины <tex> t \in V </tex> считать длину этого пути, равную <tex> d[t] </tex>. Можно считать, что для непосещенных вершин эта длина бесконечно велика. Тогда на каждом шаге длина пути до <tex> t </tex> равна <tex> \rho(s, t) </tex>, если <tex> t </tex> посещена и <tex> \infty </tex> в противном случае. Отсюда следует, что если на каждом шаге обновлять длины путей, то информация о множестве <tex> X </tex> является избыточной, и его можно не хранить.

=== Анализ времени работы ===

Оценим время работы для входного графа <tex>G = (V, E)</tex>. В очередь добавляются только непосещенные вершины, поэтому каждая вершина посещается не более одного раза. Операции внесения в очередь и удаления из нее требуют <tex> O(1) </tex> времени, так что общее время работы с очередью составляет <tex> O(|V|) </tex> операций. Для каждой вершины <tex> v </tex> рассматривается не более <tex> deg\ v </tex> ребер, инцидентных ей. Так как <tex> \sum\limits_{v \in V} deg\ v = 2|E| </tex>, то время, используемое на работу с ребрами, составляет <tex> O(|E|) </tex>. Поэтому общее время работы алгоритма поиска в ширину — <tex> O(|V| + |E|) </tex>.

=== Корректность ===

{{Утверждение
|statement=
В алгоритме поиска в ширину очередь всегда содержит сначала некоторое количество вершин с расстоянием k, а потом некоторое количество вершин с расстоянием k + 1(возможно, нулевое).
|proof=
Докажем это утверждение индукцией по числу выполненных алгоритмом шагов.

База: изначально очередь содержит только одну вершину <tex> s </tex> с расстоянием 0, утверждение верно.

Переход: пусть после <tex> l </tex>-ого шага алгоритма очередь содержит <tex> p </tex> вершин с расстоянием <tex> k </tex> и <tex> q </tex> вершин с расстоянием <tex> k + 1 </tex>. Тогда на <tex> l+1 </tex>-ом шаге мы извлечем из очереди одну вершину и добавим в нее все непосещенные(<tex> r </tex> вершин), связанные с ней; расстояние до них, очевидно, будет равно <tex> k + 1 </tex>. У нас останется <tex> p - 1 </tex> (возможно, 0) вершин с расстоянием <tex> k </tex> и <tex> q + r </tex> вершин с расстоянием k + 1, что соответствует нашему инварианту.
}}

{{Теорема
|statement=
Алгоритм поиска в ширину в невзвешенном графе находит длины кратчайших путей до всех достижимых вершин.
|proof=
Допустим, что это не так. Выберем из вершин, для которых кратчайшие пути от <tex> s </tex> найдены некорректно, ту, настоящее расстояние до которой минимально. Пусть это вершина <tex> u </tex>, и она имеет своим предком в дереве обхода в ширину <tex> v </tex>, а предок в кратчайшем пути до <tex> u </tex> — вершина <tex> w </tex>.

Так как <tex> w </tex> — предок <tex> u </tex> в кратчайшем пути, то <tex> \rho(s, u) = \rho(s, w) + 1 > \rho(s, w) </tex>, и расстояние до w найдено верно, <tex> \rho(s, w) = d[w] </tex>. Значит, <tex> \rho(s, u) = d[w] + 1 </tex>.

Так как <tex> v </tex> — предок <tex> u </tex> в дереве обхода в ширину, то <tex> d[u] = d[v] + 1 </tex>.

Расстояние до <tex> u </tex> найдено некорректно, поэтому <tex> \rho(s, u) < d[u] </tex>. Подставляя сюда два последних равенства, получаем <tex> d[w] + 1 < d[v] + 1 </tex>, то есть, <tex> d[w] < d[v] </tex>. Из ранее доказанной леммы следует, что в этом случае вершина <tex> w </tex> попала в очередь и была обработана раньше, чем <tex> v </tex>. Но она соединена с <tex> u </tex>, значит, <tex> v </tex> не может быть предком <tex> u </tex> в дереве обхода в ширину, мы пришли к противоречию, следовательно, найденные расстояния до всех вершин являются кратчайшими.
}}

=== Реализация ===

В приведенном ниже псевдокоде <tex> G = (V, E) </tex> - входной граф, <tex> s </tex> - выделенная вершина, Q - очередь. Множество <tex> X </tex> не хранится, вместо него использются расстояния в дереве обхода в ширину; расстояние от <tex>s</tex> до вершины <tex>u</tex>, вычисляемое алгоритмом, хранится в поле <tex>d[u]</tex>.

'''BFS'''(<tex>G</tex>, <tex>s</tex>)
1 d[s] <tex> \leftarrow </tex> 0
2 Q <tex> \leftarrow \emptyset </tex>
3 Q.push(s)
4 '''while''' Q <tex> \ne \emptyset </tex>
5 '''do''' u <tex> \leftarrow </tex> Q.pop
6 '''for''' v: uv <tex> \in </tex> E
7 '''do''' '''if''' d[v] = <tex> \infty </tex>
8 '''then''' d[v] <tex> \leftarrow </tex> d[u] + 1
9 Q.push(v)

== Ссылки ==

* [http://e-maxx.ru/algo/bfs Поиск в ширину на e-maxx.ru]
* [http://ru.wikipedia.org/wiki/Поиск_в_ширину Поиск в ширину в Википедии]
* [http://rain.ifmo.ru/cat/view.php/vis/graph-general/bfs-2002 Визуализатор алгоритма]

== Литература ==

*Томас Х. Кормен и др. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Кратчайшие пути в графах]]

Использование обхода в глубину для проверки связности

2012-03-22T21:58:41Z

217.118.78.98:

== Алгоритм проверки наличия пути из s в t ==
* '''Задача'''
Дан граф <tex>G</tex> и две вершины <tex>s</tex> и <tex>t</tex>. Необходимо проверить, существует ли путь из вершины <tex>s</tex> в вершину <tex>t</tex> по рёбрам графа <tex>G</tex>.

* '''Алгоритм'''
Небольшая модификация алгоритма [[Обход в глубину, цвета вершин|обхода в глубину]]. Смысл алгоритма заключается в том, чтобы запустить обход в глубину из вершины <tex>s</tex> и проверять при каждом посещении вершины, не является ли она искомой вершиной <tex>t</tex>.
Так как в первый момент времени все пути в графе "белые", то если вершина <tex>t</tex> и была достижима из <tex>s</tex>, то по [[Лемма о белых путях|лемме о белых путях]] в какой-то момент времени мы зайдём в вершину <tex>t</tex>, чтобы её покрасить. Время работы алгоритма <tex>O(M + N)</tex>.

* '''Реализация'''
vector<bool> visited; //вектор для хранения информации о ''пройденных'' и ''не пройденных'' вершинах

bool dfs(int u)
{
if(u == t)
return true;
visited[u] = true; //помечаем вершину как пройденную
for (v таких, что (u, v) — ребро в G) //проходим по смежным с u вершинам
if (!visited[v]) //проверяем, не находились ли мы ранее в выбранной вершине
if(dfs(v))
return true;
return false;
}

int main()
{
... //задание графа G с количеством вершин n и вершин S и T.
visited.assign(n, false); //в начале все вершины в графе ''не пройденные''
if(dfs(s))
std::out << "Путь из S в T существует";
else
std::out << "Пути из S в T нет";
return 0;
}

== Алгоритм проверки связности графа G ==
* '''Задача'''
Дан [[Основные определения теории графов|неориентированный граф]] <tex>G</tex>. Необходимо проверить, является ли он связным.
* '''Алгоритм'''
Заведём счётчик количества вершин которые мы ещё не посетили. В стандартной процедуре dfs() будем уменьшать счётчик на единицу при входе в процедуру. Запустимся от какой-то вершины нашего графа. Если в конце работы процедуры dfs() счётчик равен нулю, то мы побывали во всех вершинах графа, а следовательно он связен. Если счётчик отличен от нуля, то мы не побывали в какой-то вершине графа. Работает алгоритм за <tex>O(M + N)</tex>.

* '''Реализация'''
vector<bool> visited; //вектор для хранения информации о ''пройденных'' и ''не пройденных'' вершинах
int k = 0;

void dfs(int u)
{
k--;
visited[u] = true; //помечаем вершину как пройденную
for (v таких, что (u, v) — ребро в G) //проходим по смежным с u вершинам
if (!visited[v]) //проверяем, не находились ли мы ранее в выбранной вершине
dfs(v);
}

int main()
{
... //задание графа G с количеством вершин n и вершин S и T.
visited.assign(n, false); //в начале все вершины в графе ''не пройденные''
k = n;
for(int i = 0; i < n; i++)
dfs(i);
if(k == 0)
std::out << "Граф связен"; //вывести, что граф связен
else
std::out << "Граф несвязен"; //вывести, что граф несвязен
return 0;
}

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обход в глубину]]