PPt4Web Хостинг презентаций

Главная / Информатика / Алгоритмы на графах. Определение наличия циклов в графе
X Код для использования на сайте:

Скопируйте этот код и вставьте его на свой сайт

X

Чтобы скачать данную презентацию, порекомендуйте, пожалуйста, её своим друзьям в любой соц. сети.

После чего скачивание начнётся автоматически!

Кнопки:

Презентация на тему: Алгоритмы на графах. Определение наличия циклов в графе


Скачать эту презентацию

Презентация на тему: Алгоритмы на графах. Определение наличия циклов в графе


Скачать эту презентацию



№ слайда 1 Алгоритмы на графах Определение наличия циклов в графе Югов Иван Олегович МОУ Ги
Описание слайда:

Алгоритмы на графах Определение наличия циклов в графе Югов Иван Олегович МОУ Гимназия №10, г. Тверь

№ слайда 2 Домашнее задание Какое максимальное количество рёбер может быть в ориентированно
Описание слайда:

Домашнее задание Какое максимальное количество рёбер может быть в ориентированном ациклическом графе с n вершинами? Может ли быть так, что правильным результатом топологической сортировки графа оказывается любой порядок его вершин? Решить задачу о производстве деталей с помощью DFS. Как использовать топологическую сортировку для определения наличия циклов в графе?

№ слайда 3 Циклы и топологическая сортировка Если граф ациклический, то можно выполнить топ
Описание слайда:

Циклы и топологическая сортировка Если граф ациклический, то можно выполнить топологическую сортировку. Если в графе есть циклы, то топологическая сортировка невозможна. Как с помощью топологической сортировки определить наличие циклов в графе? Pascal Cycles := False; for i := 1 to n do for j := 1 to n do if A[i, j] and (order[j] > order[i]) then Cycles := True; C Cycles = FALSE; for(i = 0; i < n; i++) for(j = 0; j < n; j++) if(A[i, j] && (order[j] > order[i])) Cycles = TRUE;

№ слайда 4 Поиск циклов в графе Используем DFS для нахождения графа. Если из текущей вершин
Описание слайда:

Поиск циклов в графе Используем DFS для нахождения графа. Если из текущей вершины есть путь в серую вершину, то имеем цикл. Если в графе есть цикл, то почему DFS обязательно его найдёт?

№ слайда 5 Поиск циклов в графе Рассмотрим цикл и момент, когда покидаем первую вершину в н
Описание слайда:

Поиск циклов в графе Рассмотрим цикл и момент, когда покидаем первую вершину в нём. Возвращаться будем из вершины X в вершину Y, поочерёдно окрашивая вершины в цикле в чёрный цвет.

№ слайда 6 Поиск циклов в графе Как определить сам цикл? Сделаем стек. При заходе в вершину
Описание слайда:

Поиск циклов в графе Как определить сам цикл? Сделаем стек. При заходе в вершину помещаем её в стек, при выходе — забираем её оттуда. массив stack длины n — стек вершин; sp — указатель вершины стека (число элементов в нём). Pascal sp := 0; Push(v): Inc(sp); stack[sp] := v; Pop: Dec(sp); C sp = 0; Push(v): stack[++sp - 1] = v; Pop: sp--;

№ слайда 7 Поиск циклов в графе Pascal for i := 1 to n do color[i] := WHITE; rm := False; f
Описание слайда:

Поиск циклов в графе Pascal for i := 1 to n do color[i] := WHITE; rm := False; found := False; DFS(1); DFS(v): color[v] := GRAY; Push(v); for <u - сосед v> do if not Found then if color[u] = WHITE then DFS(u) else if color[u] = GRAY then begin Found := True; cc := u; rm := True; end; if Found then <запомнить текущую вершину>; color[v] := BLACK; Pop; C for(i = 0; i < n; i++) color[i] = WHITE; rm = Found = FALSE; DFS(0); DFS(v): color[v] = GRAY; Push(v); for(<u - сосед v>) if(!Found) if(color[u] == WHITE) DFS(u); else if(color[u] == GRAY) { rm = Found = TRUE; cc = u; }; if(Found) <запомнить текущую вершину>; color[v] = BLACK; Pop;

№ слайда 8 Поиск циклов в графе Как запомнить все вершины, из которых выходим? Сделаем втор
Описание слайда:

Поиск циклов в графе Как запомнить все вершины, из которых выходим? Сделаем второй стек. Если цикл найден, то помещаем во второй стек все покидаемые вершины, пока не встретим вершину cc. массив stack2 длины n — стек вершин в прямом порядке; sp2 — указатель вершины второго стека. Pascal sp2 := 0; <запомнить текущую вершину>: if rm then begin rm := rm and (v <> cc); Inc(sp2); stack2[sp2] := v; end; C sp2 = 0; <запомнить текущую вершину>: if(rm) { rm &= v != cc; stack[++sp - 1] = v; };

№ слайда 9 Поиск циклов в графе В первой строке файла input.txt заданы целые n и m — соотве
Описание слайда:

Поиск циклов в графе В первой строке файла input.txt заданы целые n и m — соответственно число вершин и число рёбер ориентированного графа (1&nbsp;≤&nbsp;n&nbsp;≤&nbsp;10&nbsp;000, 0&nbsp;≤&nbsp;m&nbsp;≤&nbsp;50&nbsp;000). В следующих m строках файла заданы пары номеров вершин, соединённых рёбрами. В файл output.txt вывести последовательность номеров вершин, соответствующих любому циклу в графе. Если граф ациклический, то вывести 0. Ограничение по времени — 1 сек. Ограничение по памяти — 16 Мб.

№ слайда 10 Домашнее задание Верно ли утверждение, что из всех циклов в графе, проходящих че
Описание слайда:

Домашнее задание Верно ли утверждение, что из всех циклов в графе, проходящих через начальную вершину, DFS прежде всего находит цикл минимальной длины? Привести доказательство или контрпример. Решить задачу об определении наличия циклов в ориентированном графе проверкой рёбер: в выходной файл вывести 1, если в графе есть циклы, и 0 в противном случае. Выполнить п. 2 для неориентированного графа. Решить задачу об отыскании цикла в ориентированном графе с помощью DFS без использования второго стека.

Скачать эту презентацию


Презентации по предмету
Презентации из категории
Лучшее на fresher.ru