Алгоритм ближайшего соседа

Графы

Стеки и очереди

В технологии программирования особую важность представляют две структуры данных, основанные на динамических последовательностях, т.е. последовательностях, которые изменяются вследствие включения новых и исключения имеющихся элементов.

В обоих случаях операции включения и исключения производятся только на концах последовательности [11].

Стек есть последовательность, у которой все включения и исключения происходят только в одном конце, называемом вершиной стека. Соответственно другой конец последовательности называется основанием.

Правило работы со стеком: «Первым пришел — последним ушел».

Очередь — это последовательность, в которой все включения производятся на одном конце списка (в конце очереди), в то время как все исключения производятся на другом (в начале очереди).

Правило работы с очередью: «Первым пришел — первым ушел».

Стеки и очереди имеют важное значение в автоматизации работы с информационными структурами.

Рис. 9.5. Связь между ячейками в стеке

Рис. 9.6. Связь между ячейками в очереди

Конечный граф G = (V, E) состоит из конечного множества вершин V = {V₁, V₂ … V_m} и конечного множества ребер E = {e₁, e₂ … e_n}. Каждому ребру соответствует пара вершин.

Если ребро определяется e = (v, w), то говорят, что оно инцидентно вершинам v и w. Графы бывают ориентированными, если ребра — дуги и не ориентированными в противном случае.

Ребро называется петлей, если оно начинается и кончается в одной вершине. Два ребра считаются параллельными, если они имеют одну и ту же пару концевых вершин и, если они имеют одну и ту же ориентацию, в случае ориентированного графа.

Граф называется простым, если он не имеет ни петель, ни параллельных ребер.

Представление графа матрицей смежности

Рис. 9.7. Ориентированный граф и его матрица смежности

У неориентированного графа матрица смежности симметричная, и для ее представления достаточно хранить только верхний треугольник, что экономит память.

Матрица весов

Граф, в котором ребру (i, j) сопоставлено число w_ij, называется взвешенным графом, а число w_ij называется весом ребра (i, j). В сетях связи или транспортных сетях эти веса представляют некоторые физические величины, такие как стоимость, расстояние, эффективность, емкость, надежность и т.д. Простой взвешенный граф может быть представлен своей матрицей весов W = [w_ij], где w_ij есть все ребра, соединяющие вершины i и j. Веса несуществующих ребер обычно полагают равными ¥ или 0 в зависимости от приложений.

Список ребер

Иногда более эффективно представлять ребра графа парами вершин. Это представление можно реализовать двумя массивами g = (g₁, g₂, …, g_m) и h = (h₁, h₂, …, h_m).

Каждый элемент в массиве есть метка вершины, а i -е ребро графа выходит из вершины g_i и входит в вершину h_i. Например, ориентированный граф (рис. 9.7) будет представляться следующим образом:

g = (1, 2, 2, 2, 2, 3, 3, 4, 5, 5, 5, 7, 7)

h = (6, 1, 3, 4, 6, 4, 5, 5, 3, 6, 7, 1, 6)

При этом легко представимы петли и параллельные ребра.

Связность и расстояние

Говорят, что вершины x и y в графе смежны, если существует ребро, соединяющее их. Говорят, что два ребра смежны, если они имеют общую вершину. Путь — это последовательность смежных ребер (v₁, v₂), (v₂, v₃) …, в которой все вершины v_1,v₂, …, v_k — различны, исключая возможно, случай v₁ = v_k. Записывается путь из v₁ в v_k как (v₁, v₂, v₃, …, v_k). Число ребер в пути называется длиной пути. Расстояние от вершины a до вершины b определяется как длина кратчайшего пути (т.е. пути наименьшей длины) из a в b.

Цикл — это путь, в котором первая и последняя вершины совпадают.

Подграф графа G = (V, E) есть граф, вершины и ребра которого принадлежат G.

Во взвешенном графе часто бывает нужно определить подграф с минимальным общим весом ребер, т.е. подграф, у которого сумма весов всех его ребер минимальна.

Процедура при этом такова. На каждом шаге выбирается новое ребро с наименьшим весом (наименьшее ребро), не образующее циклов с уже выбранными ребрами; этот процесс продолжается до тех пор, пока не будет выбрано |v|–1 ребер, образующих подграф Т, где v — число узлов дерева. Этот процесс известен как жадный алгоритм.

Другой способ получения минимума общего веса ребер, который не требует ни сортировки ребер, ни проверки на цикличность на каждом шаге, известен как алгоритм ближайшего соседа.

Прохождение графа начинается с некоторой произвольной вершины а в заданном графе. Пусть (a, b) — ребро с наименьшим весом, инцидентное a; ребро (a, b) включается в дерево. Затем среди всех ребер, инцидентных либо а, либо b, выбирается ребро с наименьшим весом, и оно включается в частично построенный подграф. В результате в подграф добавляется новая вершина, например c. Повторяя процесс, ищем наименьшее ребро, соединяющее a, b или c с некоторой другой вершиной графа. Процесс продолжается до тех пор, пока все вершины из G не будут включены в подграф.