1. Сравните известные вам способы хранения информации о графах в памяти компьютера. Какие достоинства и недостатки имеет каждый из них?
Информация о графах может храниться в памяти компьютера с использованием различных способов, включая матрицу смежности, список смежности и список рёбер. Матрица смежности: это квадратная матрица, где строка и столбец соответствуют вершинам графа, а элемент показывает наличие рёбра. Достоинство этого метода в простоте и удобстве для плотных графов. Недостатком является большой расход памяти при разреженных графах, так как множество элементов остаются нулевыми. Список смежности: каждая вершина графа имеет список связанных с ней вершин. Этот метод экономит память в случае разреженных графов. Недостаток — менее удобный доступ к информации о конкретном ребре. Список рёбер: хранит пары вершин, соединённых рёбрами, возможно, с весами. Это эффективно для хранения разреженных графов, но доступ к информации о соседних вершинах сложнее.
2. Сравните понятия «матрица смежности» и «весовая матрица».
Матрица смежности содержит только информацию о наличии рёбер между вершинами. Её элементы обычно равны 0 или 1 (или другим значениям в случае мультиграфов). Весовая матрица дополнительно включает веса рёбер. Элементы этой матрицы могут быть числами, отражающими стоимость, расстояние или время между вершинами.
3. Какие особенности может иметь весовая матрица орграфа?
Весовая матрица орграфа может быть асимметричной, так как вес рёбра от вершины A к вершине B может отличаться от веса рёбра от B к A. Также в матрице могут присутствовать бесконечные значения для обозначения отсутствия рёбер.
4. Что такое «жадный» алгоритм? Всегда ли он позволяет найти лучшее решение?
Жадный алгоритм выбирает на каждом этапе локально оптимальное решение в надежде получить глобально оптимальное решение. Однако он не всегда находит лучшее решение, так как может застревать в локальных экстремумах. Примером может быть алгоритм ближайшего соседа в задаче коммивояжёра, который не всегда находит минимальный путь.
5. Как, на ваш взгляд, можно было бы ускорить работу алгоритма Крускала с помощью предварительной сортировки рёбер?
В алгоритме Крускала сортировка рёбер по весу позволяет быстрее находить минимальное ребро на каждом шаге. Если выполнить предварительную сортировку, то можно сразу проходить рёбра в порядке возрастания их весов, что сокращает время выполнения поиска минимального рёбра с O(E) до O(1) на каждой итерации.