Содержание
- 2. Поиск в глубину Суть алгоритма: идем из каждой вершины графа «вглубь» насколько это возможно Реализация: void
- 3. Топологическая сортировка Перенумеровывание вершин таким образом, чтобы все ребра вели из вершины с меньшим номером в
- 4. Реализация топологической сортировки Сложность: O(M) void topSort() { g.resize(n + 1); for (int i = 0;
- 5. Обход в ширину Суть алгоритма: идем «вширь» от каждой вершины насколько это возможно, то есть идем
- 6. Кратчайший путь в невзвешенном графе Модифицируем поиск в ширину void bfs(int s) { queue q; q.push(s);
- 7. Кратчайший путь во взвешенном графе. Алгоритм Дейкстры. Все вершины делятся на помеченные и непомеченные Для помеченных
- 8. Реализация алгоритма Дейкстры void dijkstra(int s) { vector mark(n, false); vector d(n, INF); d[s] = 0;
- 9. Алгоритм Флойда-Уоршелла Находит кратчайшие пути между всеми парами вершин for (int k = 0; k for
- 10. Остовное дерево. Алгоритм Прима Остов строится последовательным добавлением вершин в одно большое дерево. На каждом шаге
- 11. Остовное дерево. Алгоритм Прима void prima() { vector mark(n, false); vector d(n, INF); d[0] = 0;
- 12. Остовное дерево. Алгоритм Крускала Остов строится из нескольких деревьев, которые постепенно объединяются в одно Изначально каждая
- 13. Остовное дерево. Алгоритм Крускала void kruskal() { for (int i = 0; i color[i] = i;
- 15. Скачать презентацию