За один шаг просмотра можно ответить, существует ли ребро из х в y.
Независимо от количества ребер объем требуемой памяти равен.
Для случая взвешенного графа вместо 1 используется значение весовой функции, и такая матрица называется матрицей весов (веса могут представлять расстояние между городами или продолжительность конкретной работы).
Возможно представление графа списком ребер. Это экономит память при неплотных графах (m<<). Требуемый объем памяти составляет 2m (m - количество ребер графа).
Список смежности - для каждой вершины x содержит список вершин, смежных с ней.
Каждый элемент списка смежности является структурой, содержащей вершину и указатель на следующую структуру в списке. Начало каждого списка хранится в массиве. Для неориентированных графов каждое ребро представлено дважды.
Для взвешенного орграфа каждый узел связного списка содержит поле веса.
Лекция №14
Тема: Алгоритмы обхода графов
Цель: знать алгоритмы обхода графов.
Для прохождения нелинейных структур требуется разработать стратегию доступа к узлам и маркирования узлов после обработки.
Большинство алгоритмов на графах имеют в основе такой систематический перебор вершин графа, что каждая вершина просматривается один раз.
4.3.1. Поиск в глубину
Поиск в глубину напоминает прямой метод обхода деревьев, при котором сначала обрабатывается узел, а потом выполняется продвижение вниз по дереву.
Начальная вершина передается в качестве параметра и становится первой обрабатываемой вершиной. По мере продвижения вниз до тупика смежные вершины запоминаются в стеке. Если еще остались необработанные вершины, то осуществляется возврат к вершинам в стеке и продолжается поиск по другому пути. Обработанные вершины образуют множество всех вершин, достижимых из начальной вершины.
Для хранения обработанных вершин используется список L, а для запоминания смежных вершин – стек S.
Начальная вершина помещается в стек. Итерационный процесс выталкивания вершины из стека и ее обработки:a) вытолкнуть вершину V из стека;
b) проверить по списку L, была ли она обработана;
c) если нет, то произвести обработку этой вершины и получить список смежных с ней вершин;
d) включить V в список L, чтобы избежать повторной обработки;
e) поместить в стек те смежные с V вершины, которых еще нет в списке L.
Когда стек становится пустым, процесс завершается и возвращает список отработанных вершин.Пример:
Дан граф
1. Вершина А является начальной и помещается в стек. |
2. А выталкивается из стека и обрабатывается. А включается в список обработанных вершин, смежные с ней вершины B и G помещаются в стек. |
3. Вершина G выталкивается из стека. Так как этой вершины пока нет в списке L, она включается в него. В стек помещается вершина F, смежная с G. |
4. Вершина F выталкивается из стека и помещается в список L. Смежная с ней вершина A уже есть в списке. |
5. Обработка вершины В. |
6. Обработка вершины С. |
7. Вершина Е имеет две смежные вершины D и F. Вершина F в имеется списке L и поэтому пропускается. Вершины D в списке нет, поэтому она помещается в стек. |
8. Поиск завершается после обработки вершины D. Второй экземпляр D в стеке игнорируется, так как эта вершина уже находится в списке L. |
4.3.2. Поиск в ширину
Поиск в ширину аналогичен поперечному прохождению дерева, который начинается с корня, и обход узлов осуществляется уровень за уровнем сверху вниз.
Поиск в ширину начинает работу с некоторой начальной вершины и затем производит обработку каждой вершины, смежной с ней. Затем сканирование продолжается на следующем уровне смежных вершин, и т. д. до конца пути.
Для хранения обработанных вершин используется список L, а для запоминания смежных вершин – очередь Q.
Начальная вершина помещается в очередь. Итерационный процесс удаления вершины из очереди и ее обработки:a) удалить вершину V из очереди;
b) проверить по списку L, была ли она обработана;
c) если нет, то произвести обработку этой вершины и получить список смежных с ней вершин;
d) включить V в список L, чтобы избежать повторной обработки;
e) поместить в очередь те смежные с V вершины, которых еще нет в списке L.
Когда очередь становится пустой, процесс завершается и возвращает список отработанных вершин.Пример:
Дан граф
1. Вершина А является начальной и помещается в очередь. |
2. А удаляется из очереди и обрабатывается. А включается в список обработанных вершин, смежные с ней вершины B и G помещаются в очередь. |
3. Вершина В удаляется из очереди. Так как этой вершины пока нет в списке L, она включается в него. В очередь помещается вершина С, смежная с В. |
4. Вершина G удаляется из очереди и помещается в список L. Смежная с ней вершина F помещается в очередь. |
5. Обработка вершины C. |
6. Обработка вершины F. |
7. Обработка вершины D. |
8. Обработка вершины Е. |
4.4. Достижимость и алгоритм Уоршолла
Для каждой пары вершин некоторого графа говорят, что достижима из тогда и только тогда, когда существует направленный путь от к. Это определяет отношение достижимости R. Для каждой вершины поиск в глубину находит все вершины, достижимые из. При поиске в ширину получается серия списков достижимости, которые образуют отношение R:
: <список достижимости для > |
Это же отношение можно описать при помощи матрицы достижимости размером, которая содержит 1 в позиции (i, j), представляя тем самым R.
Матрицу достижимости можно использовать для проверки существования пути между двумя вершинами. Если элемент (i, j) равен 1, то существует минимальный путь между и.
Вершины в списке достижимости можно использовать для наращивания ребер графа.
Если существует путь из вершины u в вершину v, мы добавляем ребро E(u, v), соединяющее эти две вершины. Расширенный граф состоит из вершин V графа G и ребер, связывающих вершины, которые соединены направленным путем. Такой расширенный граф называется транзитивным замыканием.
Поиск матрицы достижимости
Предположим, что мы стоим матрицу достижимости R и вершинам a, b, c соответствуют индексы i, j, k. Если R[i][k]=1 и R[k][j]=1, установить R[i][j]=1.
Алгоритм Уоршалла проверяет все возможные тройки с помощью трех вложенных циклов по индексам i, j, k. Для каждой пары (i, j) добавляет ребро, если существует вершина, такая, что ребра и находятся в расширенном графе.
Повторяя этот процесс, мы соединяем дополнительными ребрами любую пару достижимых вершин. В результате получается матрица достижимости:
for (i=0;i<n;i++)
for (j=0;j<n;j++)
for (k=0;k<n;k++)
if (WSM[i][j]==0) WSM[i][j]=WSM[i][k] * WSM[k][j];
Этот алгоритм устанавливает, что существует путь от вершины i до вершины j, проходящий через вершины с номерами, не превышающими k, только в следующих случаях:
Уже существует путь от вершины i до вершины j, который проходит через вершины с номерами, не превышающими k-1. Существует путь от вершины i до вершины k, проходящий через вершины с номерами, не превышающими k-1, и путь от вершины k до вершины j, который также проходит через вершины с номерами, не превышающими k-1.Лекция №15.
Тема: Теория сложности алгоритмов.
Цель: познакомить с методами сравнения алгоритмов и требованиями предъявляемыми к ним.
Для сравнения разных алгоритмов, предназначенных для решения одной задачи, для приблизительной оценки времени выполнения программы применяется математический анализ алгоритмов.
В процессе решения прикладных задач необходимо выбрать подходящий алгоритм решения. При этом алгоритм должен удовлетворять следующим требованиям:
1. Быть простым для понимания, перевода в программный код и отладки.
2. Эффективно использовать компьютерные ресурсы и выполняться по возможности быстро.
На время выполнения программы влияют следующие факторы:
1. Ввод исходной информации в программу.
2. Качество скомпилированного кода исполняемой программы.
3. Машинные инструкции, используемые для выполнения программы.
4. Временная сложность алгоритма соответствующей программы.
Под временной сложностью алгоритма понимается «время» выполнения алгоритма, измеряемое в «шагах», которые необходимо выполнить алгоритму для достижения запланированного результата. В качестве синонима для этого термина часто используется выражение «время выполнения алгоритма».
Время выполнения программы зависит от размера исходных данных. Например, нахождение минимального элемента в массиве - простой алгоритм, основная операция которого включает сравнение элементов данных. Для массива с n элементами алгоритм требует n-1 сравнений, и время его выполнения пропорционально n.
Для описания временной сложности алгоритмов используется О-символика. Например, если время выполнения Т(n) некоторой программы имеет порядок O(n2) (читается «о-большое от n в квадрате», или просто «о от n в квадрате»), это означает, что существуют положительные константы c и n0, такие, что для всех n, больших или равных n0, выполняется неравенство T(n)?cn2.
Следует отдавать предпочтение программам с наименьшей степенью роста времени выполнения. Это объясняется тем, что чем меньше степень роста, тем больше размер задачи, которую можно решить на компьютере.
Теоретическое нахождение времени выполнения программ - сложная математическая задача, для ее решения необходимо знать несколько базовых принципов.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
