Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.


Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

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

Домашнее заданиеКакое максимальное количество рёбер может быть в ориентированном ациклическом графе с n вершинами?Может ли быть так, что правильным результатом топологической сортировки графа оказывается любой порядок его вершин?Решить задачу о производстве деталей с помощью DFS.Как использовать
Алгоритмы на графахОпределение наличия циклов в графеЮгов Иван ОлеговичМОУ Гимназия №10, г. Тверь Домашнее заданиеКакое максимальное количество рёбер может быть в ориентированном ациклическом графе с Циклы и топологическая сортировкаЕсли в графе есть циклы, то топологическая сортировка невозможна.Если Поиск циклов в графеИспользуем DFS для нахождения графа.Если из текущей вершины есть Поиск циклов в графеРассмотрим цикл и момент, когда покидаем первую вершину в Поиск циклов в графеКак определить сам цикл?Сделаем стек. При заходе в вершину Поиск циклов в графеPascalfor i := 1 to n do color[i] := Поиск циклов в графеКак запомнить все вершины, из которых выходим?Сделаем второй стек. Поиск циклов в графеВ первой строке файла input.txt заданы целые n и Домашнее заданиеВерно ли утверждение, что из всех циклов в графе, проходящих через
Слайды презентации

Слайд 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

Поиск циклов в графеPascalfor i := 1 to n do color[i]

n do
color[i] := WHITE;
rm := False; found :=

False; DFS(1);

DFS(v):
color[v] := GRAY; Push(v);
for 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()
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

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

заданы целые n и m — соответственно число вершин

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

  • Имя файла: algoritmy-na-grafah-opredelenie-nalichiya-tsiklov-v-grafe.pptx
  • Количество просмотров: 158
  • Количество скачиваний: 0