Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 2 вопрос
- Граф – конечное множество вершин и множеств рёбер. Каждому ребру сопоставлены 2 вершины – концы ребра.
- Представление графов в памяти
- Обычно используются 2 типа матриц: 1) матрица смежности 2) весовая матрица
- Матрица смежности – матрица размером N*N, где каждый эл-т с индексами i,j является логическим значением и показывает есть ли дуга между i и j.
- Весовая матрица – квадратичная матрица, где каждый эл-т с индексами i,j равен весу ребра из вершины i в j.
- DFS
- Поиск в глубину – один из способов обхода графа, заключается в том, чтобы идти вглубь графа насколько это возможно. Алгоритм – рекурсивный. Перебираются все исходящие из рассматриваемой вершины ребра. Если ребро ведет в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать ребра, возврат происходит если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину.
- visited[] // хранит информацию о пройденных и не… вершинах
- function before( G[n]: graph){
- visited = array [n; false];
- }
- function dfs (int i){
- visited[i]=true;
- for v: (u,v) in G
- if not visited[v]
- dfs(v);
- }
- main(){
- for i = 1 to n
- if not visited[i]
- dfs(i);
- }
- Сложность O ( V + E), где V – множество вершин, E мн-во ребёр графа.
- Лемма о белом пути
- Не существует такого момента поиска в глубину, в которой бы существовало ребро из черной вершины в белую.
- Док-во: Пусть в процессе dfs нашлось ребро из черной вершины V в белую вершину U. Рассмотрим момент времени, когда был запущен dfs(V). В этот момент вершина V была перекрашена в серый, и не будет окрашена в черный пока не пройдет по всем вершинам белого цвета.
- Рёбра
- 1. Дуги дерева – рёбра, ведущие к вершинам, которые раньше не посещались.
- 2. Обратные дуги – рёбра, ведущие от потомков к предкам.
- 3. Прямые дуги - рёбра, ведущие от предков к собственным потомкам, не являющиеся дугами дерева
- 4. Поперечные дуги – рёбра, соединяющие вершины, не являющиеся ни предками, ни потомками
- Свойства времен входа и выхода
- Метки времени d[v] и f[v] являются целочисленными от 1 до 2|V|. Для каждой вершины v имеет место неравенство d[v]<f[v]. Вершина v будет белой до момента времени d[v], серой с d[v] до f[v] и чёрной после f[v].
- Проверка графа на ацикличность
- Произведём серию поисков в глубину в графе. Из каждой вершины, в которую мы ещё ни разу не приходили, запустим поиск в глубину, который при входе будет красить вершины в серый, а при выходе в чёрный. И если поиск в глубину из какой-то вершины пытается пойти в серую вершину, то это означает, что цикл обнаружен.
- Подсчет компонент связности
- Производится серия обходов: сначала запустим обход из первой вершины, и все вершины, которые он при этом обошёл – образуют первую компоненту связности. Затем найдём первую из оставшихся вершин, которые ещё не были посещены, и запустим обход из неё, найдя тем самым вторую компоненту связности, пока все вершины не станут помеченными. Асимптотика O(n+m)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement