Разбор КР1 по ВычМеху

[Ссылка на видео]


Теги для навигации:
#ВычМех@diarystudents
#РазборКР1@diarystudents

Объявление
Вместо множество пустых каналов я решил вести только этот.

Тут будет побольше информации

Задачник по теории веротности. Агапов Г.И.

Решения некоторых номеров в комментариях под этим постом

#ТерВер@diarystudents

Обход графа в глубину

Также поиск в глубину, англ. Depth-First Search, DFS.

Работу DFS можно описать следующим образом:
1. Начинать с исходной вершины, маркировать её как посещённую.

2. Рекурсивно исследовать соседей этой вершины, углубляясь в граф.

3. После того как все соседи исследованы, возвращаться к предыдущей вершине и продолжать искать пути.

#ГрафыИТензоры@diarystudents

Алгоритмы Беллмана-Форда и нахождения кратчайшего пути в сети без контуров

Алгоритм Беллмана-Форда более универсален в применении, единственное ограничение для него – отсутствие отрицательного цикла в графе, но за эту универсальность асимптотическая сложность O(|V|*|E|), где V – множество вершин, E – множество ребер, что медленнее чем второй алгоритм.

Алгоритм нахождения кратчайшего пути в сети без контуров требует топологической сортировки, также отсутствия циклов в графе, но за эти ограничения асимптотическая сложность O(|V|+|E|), где V – множество вершин, E – множество ребер.

Отчет по лабораторной работе №2
Полученный балл: 54/54

#ГрафыИТензоры@diarystudents
#Отчет@diarystudents

Обход графа в ширину

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

Области применения:
- Поиск кратчайшего пути в невзвешенном графе (определение минимального числа рёбер).
- Поиск компонент связности.

#ГрафыИТензоры@diarystudents

Отчет по семинару по графам

Программная реализация обхода графа в ширину.

Полученный балл: 54/54

#ГрафыИТензоры@diarystudents
#Отчет@diarystudents