19. Алгоритмы на графах. Алгоритмы на графах.

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

Иногда приходится распространять ту или иную информацию среди большой группы людей или по всем компьютерам большой сети. Мы хотели бы, чтобы информация достигла каждого участника группы, но при этом ровно по одному разу. В некоторых группах для этой цели организуется «телефонное дерево», когда каждый из членов группы, получив свежую новость, сообщает ее небольшому числу других участников. Если каждый из членов группы встречается в дереве лишь однажды, а высота дерева не очень велика, то информация очень быстро доходит до всех. Для графов общего вида ситуация оказывается сложнее: в среднем графе гораздо больше связей, чем в дереве. Мы изучим два метода обхода графов: в глубину и по уровням, позволяющих преодолеть эту трудность. Остовное дерево представляет собой связное подмножество графа, не содержащее циклов, включающее в себя все вершины графа и некоторые из его ребер. Минимальное остовное дерево это остовное дерево, имеющее минимально возможную сумму весов ребер.

Одно из применений минимальных остовных деревьев — организация внутренней компьютерной сети. Передающие станции устанавливаются в стратегически важных местах некоторой области. Если мы хотим уменьшить суммарную стоимость объединения станций в сеть, то можно нарисовать граф, в котором станции будут служить вершинами, а ребрам, их соединяющим, можно приписать стоимость соединения. Минимальное остовное дерево этого графа указывает, какие станции следует соединить между собой, чтобы любые две станции оказались соединенными, причем общая стоимость соединения была минимально возможной.

Аналогичные приложения имеет и задача поиска кратчайшего пути в графе: умение решать такую задачу помогает планировать путь на автомобиле или посылать сообщение по компьютерной сети.

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

Структуры данных для представления графов. Информацию о графах или орграфах можно хранить двумя способами: в виде матрицы примыканий или в виде списка примыканий.

Матрица примыканий обеспечивает быстрый доступ к информации о ребрах графа, однако если в графе мало ребер, то эта матрица будет содержать гораздо больше пустых клеток, чем заполненных. Длина списка примыканий пропорциональна числу ребер в графе, однако при пользовании списком время получения информации о ребре увеличивается. Ни один из этих методов не превосходит другой заведомо. В основе выбора подходящего метода должны лежать наши предварительные знания о графах, которые будут обрабатываться алгоритмом. Если в графе много вершин, причем каждая из них связана лишь с небольшим количеством других вершин, список примыкании оказывается выгоднее, поскольку он занимает меньше места, а длина просматриваемых списков ребер невелика. Если же число вершин в графе мало, то лучше воспользоваться матрицей примыканий: она будет небольшой, и даже потери при хранении в матричном виде разреженного графа будут незначительны. Если же в графе много ребер и он почти полный, то матрица примыканий всегда является лучшим способом хранения графа.

Матрица примыканий AdjMat графа G = (V,E) с числом вершин \V\ = N записывается в виде двумерного массива размером N х N.

В каждой ячейке [ i , j ] этого массива записано значение 0 за исключением лишь тех случаев, когда из вершины Uj в вершину Vj ведет ребро, и тогда в ячейке записано значение 1.

Список примыканий AdjList графа G = (V,E) с числом вершин \V\ = N записывается в виде одномерного массива длины N, каждый элемент которого представляет собой ссылку на список. Такой список приписан каждой вершине графа, и он содержит по одному элементу на каждую вершину графа, соседнюю с данной.