Вопросы для обсуждения

  1. Нарисуйте граф, соответствующий следующей матрице смежности.
../_images/adjMatEX.png
  1. Нарисуйте граф, соответствующий следующему списку рёбер.
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
  1. Игнорируя веса, выполните поиск в ширину для графа из предыдущего вопроса.
  2. Каково время выполнения функции buildGraph в терминах “большого О”?
  3. Выведите время выполнения в терминах “большого О” для алгоритма топологической сортировки.
  4. Выведите время выполнения в терминах “большого О” для алгоритма поиска сильно связных компонетов.
  5. Покажите каждый шаг выполнения алгоритма Дейкстры для графа, показанного выше.
  6. Используя алгоритм Прима, найдите минимальное взвешенное островное дерево для графа, показанного выше.
  7. Нарисуйте граф зависимостей, иллюстрирующий отправку е-мейла. Выполните топологическую сортировку для вашего графа.
  8. Выведите выражение для базы экспоненты, используемой в выражении времени выполнения задачи о ходе коня.
  9. Объясните, почему общий DFS алгоритм не подходит для решения задачи о ходе коня.
  10. Каково время выполнения алгоритма Прима в терминах нотации “большое О”?
Next Section - Упражнения для программирования