Вопросы для обсуждения
- Нарисуйте граф, соответствующий следующей матрице смежности.
- Нарисуйте граф, соответствующий следующему списку рёбер.
| from |
to |
cost |
|---|
| 1 |
2 |
10 |
| 1 |
3 |
15 |
| 1 |
6 |
5 |
| 2 |
3 |
7 |
| 3 |
4 |
7 |
| 3 |
6 |
10 |
| 4 |
5 |
7 |
| 6 |
4 |
5 |
| 5 |
6 |
13 |
- Игнорируя веса, выполните поиск в ширину для графа из предыдущего вопроса.
- Каково время выполнения функции buildGraph в терминах “большого О”?
- Выведите время выполнения в терминах “большого О” для алгоритма топологической сортировки.
- Выведите время выполнения в терминах “большого О” для алгоритма поиска сильно связных компонетов.
- Покажите каждый шаг выполнения алгоритма Дейкстры для графа, показанного выше.
- Используя алгоритм Прима, найдите минимальное взвешенное островное дерево для графа, показанного выше.
- Нарисуйте граф зависимостей, иллюстрирующий отправку е-мейла. Выполните топологическую сортировку для вашего графа.
- Выведите выражение для базы экспоненты, используемой в выражении времени выполнения задачи о ходе коня.
- Объясните, почему общий DFS алгоритм не подходит для решения задачи о ходе коня.
- Каково время выполнения алгоритма Прима в терминах нотации “большое О”?
Next Section - Упражнения для программирования
