Операции с графами

Нахождение K путей минимальной длины

Построение минимального остовного дерева

Кратчайший путь в графе с неотрицательными весами

Кратчайший путь для всех пар вершин

Путь с минимальным количеством вершин

Введение

Здесь рассматриваются алгоритмы работы с графами. Граф - пара G = (V, E), где V - множество вершин (вершинами могут быть объекты произвольной природы) и E - множество ребер, ребра - элементы вида e = (v_i , v_j ), где v_i , v_j  принадлежат множеству вершин, т.е. ребро это элемент из декартова произведения множества V на себя. Достаточно подробно терминология теории графов разобрана на странице А.Чернобаева, поэтому за более полной информацией можно обратиться туда, там же можно найти алгоритмы для работы с графами, как те которые представлены здесь, так и многие другие. Нам же для дальнейшей работы понадобится рассмотреть способы задания и структуры для хранения информации о графе.

Первый способ задания графа (невзвешенного) это задать матрицу связности S размера n*n, где n количество вершин графа, т.е. мощность множества V, при этом элемент s_ij  = 1, если существует ребро из i-ой в j-ую вершины и s_ij  = 0, если такого ребра нет. Нетрудно видеть, что матрица S - симметрична, если граф неориентированный, и может быть не симметричный в противном случае. При этом полагаем, что s_ii  = 0, т.е. в графе нет петель. Такой способ задания графа используется например в волновом алгоритме.

Второй способ используется для задания взвешенного графа, т.е. графа каждому ребру которого соответствует некий параметр - вес. Для определения такого графа используется матрица весов W размер которой n*n, где n количество вершин графа. При этом элемент w_ij  равен весу ребра соединяющего i-ую и j-ую вершины. Если такого ребра нет, то w_ij  полагаем равным бесконечности (на практике это максимальное число возможное на данном языке программирования). Этот способ задания используется например в алгоритмах поиска пути во взвешенном графе.

Если нашли ошибку в алгоритме - сообщите!

Бочканов Сергей, Быстрицкий Владимир
Copyright © 1999-2004
При поддержке проекта MANUAL.RU