8.6. Графы
До сих пор мы рассматривали структуры данных, в которых связи между элементами имеют регулярный характер (определенный линейно или рекурсивно). Граф можно определить как произвольную систему связей (ветвей), установленную на множестве вершин. Ветви в графе называются ребрами. Ребра могут быть однонаправленными (ориентированный граф) и двунаправленными (неориентированный граф), а также могут иметь дополнительные (например, числовые) характеристики (нагруженные ребра). Ориентация ребер и их нагрузка имеют отношение к задачам, которые решаются при помощи алгоритмов, работающих на графах (например, нагруженные ребра могут обозначать пропускную способность, расстояния и т.п.). Нас же, прежде всего, интересуют способы представления графов и общие принципы программирования для них. Конкретные алгоритмы будут приводиться здесь как иллюстрация общего подхода.
![рис. 86-1. Нагруженный неориентированный граф]./assets/086-01.png)
Способы представления графов
Для представления графов можно использовать различные табличные и списковые структуры. Самой простой и «близкой к математике» является матрица смежности. Это квадратная матрица, индексами в которой являются номера вершин. При наличии между вершинами с номерами i,j ребра с весом m значение элемента Aij=m, при отсутствии ребра значение элемента нулевое. В неориентированном графе матрица симметрична относительно главной диагонали, которая также является нулевой. Для приведенного на рисунке графа матрица смежности определяется в массиве таким образом:
int A[7][7]={
{ 0, 5, 8, 0, 0, 0, 0},
{ 5, 0, 0,12, 0, 9, 0},
{ 8, 0, 0, 0, 8, 4, 2},
{ 0,12, 0, 0, 3, 6, 0},
{ 0, 0, 8, 3, 0, 0, 7},
{ 0, 9, 4, 6, 0, 0, 0},
{ 0, 0, 2, 0, 7, 0, 0}};Для задания переменной размерности используется массив указателей на строки матрицы. Другой более компактный способ – это таблица ребер. Однако он повышает трудоемкость алгоритмов за счет перебора всей таблицы при поиске ребер для заданной вершины.
struct link2 { int v1,v2,lnt; }
A[]={{0,1,5},{0,2,8},{1,3,12},{1,5,9},{3,5,6},
{2,5,4},{3,4,3},{2,4,8},{2,6,2},{4,6,7} ,{-1,-1,0}};Обеспечить прямой доступ к множеству ребер любой вершины и при этом эффективно использовать память можно на основе структур данных, использующих указатели. Это может быть, например, массив указателей на массивы или на списки описателей ребер.
struct link4{ int v2; lnt;};
link4 a0[]={{1,5},{2,8},{-1,-1}};
link4 a1[]={{0,5},{3,12},{5,9},{-1,-1}};
link4 a2[]={{0,8},{4,8},{5,4},{6,2},{-1,-1}};
link4 a3[]={{1,12},{4,3},{5,6},{-1,-1}};
link4 a4[]={{2,8},{3,3},{6,7},{-1,-1}};
link4 a5[]={{1,9},{2,4},{3,6},{-1,-1}};
link4 a5[]={{2,2},{4,7},{-1,-1}};
link *pp[]={a0,a1,a2,a3,a4,a5,a6};
struct link3{
int v2,lnt;
link3 *next; };
//--------------------------------------------------------------------------86-01.cpp
// Создание массива указателей на списки из матрицы смежности
link3 **create(int *pp[],int N){
int i,j;
link3 **M=new link3*[N];
for (i=0;i<N;i++) M[i]=NULL;
for (i=0;i<N;i++)
for (j=0;j<N;j++)
if (pp[i][j]!=0){
int vv2,l2;
link3 *q=new link3(j,pp[i][j]);
q->next=M[i]; M[i]=q;
}
return M;}Поисковые задачи на графах
С помощью графов решаются различные поисковые и оптимизационные задачи. Образная модель (см. 3.4) их решения включает в себя различные варианты «движения» по ребрам графа. Здесь можно выделить две основных идеи:
если алгоритм решает задачу путем присоединения на каждом шаге еще одной вершины к множеству просмотренных, то он является «жадным» и имеет трудоемкость вида T=O(N2), поскольку состоит из N шагов по присоединению вершин, на каждом из которых выбирается одна из еще не просмотренных. Такие алгоритмы являются эффективными, но требуют обоснования «жадности»;
если алгоритм рассматривает все возможные последовательности присоединения вершин, то он имеет экспоненциальную трудоемкость, поскольку содержит в своей основе полный комбинаторный перебор. Так, если вершина имеет в среднем m ветвей, то она может быть оценена как T=O((m-1)N).
Полный рекурсивный обход графа. Задачи, в которых рассматриваются все возможные последовательности вершин графа (пути), могут быть реализованы с помощью рекурсивного алгоритма полного обхода графа. Инвариантом рекурсии здесь является текущая вершина и последовательность пройденных вершин (путь). Как минимум, нужно просто отмечать пройденные вершины. Это исключает их повторное посещение и «зацикливание» рекурсии. По возвращении из рекурсивного вызова отметка снимается, что позволяет выполнять обход всех путей независимо друг от друга.
//--------------------------------------------------------------------------86-01.cpp
//--- Полный рекурсивный обход графа, матрица смежности
void scan_1(int i,int **M, int n, int D[]){
D[i]=1;
for (int j=0;j<n;j++)
if (M[i][j]!=0 && D[j]==0) scan_1(j,M,n,D);
D[i]=0;}
//--- Полный рекурсивный обход графа, таблица пар
void scan_2(int i,link2 M[], int D[]){
D[i]=1;
for (int j=0; M[j].v1!=-1;j++){
if (M[j].v1==i && D[M[j].v2]==0) scan_2(M[j].v2,M,D);
if (M[j].v2==i && D[M[j].v1]==0) scan_2(M[j].v1,M,D);
}
D[i]=0;}
//--- Полный рекурсивный обход графа, таблица списков смежных вершин
void scan_3(int i,link3 *M[], int n, int D[]){
D[i]=1;
link3 *q;
for (q=M[i];q!=NULL;q=q->next)
if (D[q->v2]==0) scan_3(q->v2,M,n,D);
D[i]=0;}
//--- Полный рекурсивный обход графа, массив указателей на массивы ребер
void scan_4(int i,link4 *M[], int n, int D[]){
D[i]=1;
for (int j=0;M[i][j].v2!=-1;j++)
if (D[M[i][j].v2]==0) scan_4(M[i][j].v2,M,n,D);
D[i]=0;}При представлении графа различными структурами данных сущность алгоритма обхода не меняется. Рекурсивная функция получает индекс текущей вершины и отмечает ее в глобальном массиве D, через который различные шаги рекурсии взаимодействуют между собой. Затем просматривается множество соседей, и для неотмеченных вершин функция вызывается рекурсивно. По окончании текущего вызова отметка текущей вершины снимается.
Такой алгоритм уже использовался нами для решения «задачи коммивояжера» (см. 7.4). Там он был дополнен необходимыми деталями: прямым накоплением пройденного пути (с передачей через формальный параметр) и сохранением последовательности пройденных вершин (городов) в глобальном массиве.
Что касается эффективных «жадных» алгоритмов, то все они имеют соответствующее «образное» представление. Оно используется не только для проектирования алгоритма, но и является частью обоснования его «жадности», т.е. однозначности выбора. В качестве примеров рассмотрим наиболее простые и образно очевидные алгоритмы.
Поиск кратчайших путей. Алгоритм Дейкстры. Алгоритм поиска кратчайших путей вычисляет минимальные расстояния вершин графа от его начальной вершины - Di. «Жадность» его состоит в том, что на каждом шаге он включает в множество вершин с вычисленными путями (в терминах алгоритма – «облако») еще одну вершину:
первоначально в каждой вершине устанавливается «бесконечная» длина пути (больше большего) – Di=∞, начальная вершина получает нулевое расстояние D0=0, «облако» не содержит вершин;
на каждом шаге в «облако» включается одна вершина k с минимальным Sk, вычисленным ранее;
после включения вершины корректируются расстояния всех ее соседей, если они находятся вне «облака», и новые вычисленные длины путей Di=Dk+Mk,i , просчитанные от включенной вершины, уменьшают ранее вычисленное значение Di.
//-------------------------------------------------------------------86-02.cpp
// Поиск кратчайшего пути - алгоритм Дейкстры
void min_way(int N, int **M){
int i,k,j;
int *P=new int[N],*D=new int[N];
for (i=0;i<N;i++) P[i]=0,D[i]=100000; // Облако пустое
D[0]=0; // Расстояния – бескончность, начальная - 0
while(1){
for (k=-1,i=0;i<N;i++){
if (P[i]==1) continue; // В облаке
if (k==-1 || D[i] < D[k])
k=i; } // Ближайшая вне облака
if (k==-1) break; // Нет вершин – все в облаке
P[k]=1; // Включить в облако
for (i=0;i<N;i++){
if (M[k][i]==0) continue; // Коррекция путей к соседям
if (D[k] + M[k][i] < D[i]) // - если расстояние уменьшается
D[i] = D[k] + M[k][i];
}}А теперь несколько слов к обоснованию «жадности». Алгоритм имеет ярко выраженный индуктивный характер и содержит следующий инвариант:
«облако» состоит из подмножества вершин с минимальными расстояниями , на каждом шаге Di для вершин в «облаке» будет меньше, чем у вершин вне его;
смежные вершины, не включенные в «облако», также содержат Di, соответствующие минимальным расстояниям при достижении их из текущего «облака»;
инвариантное свойство «облака» сохраняется путем выбора смежной вершины вне «облака» с минимальным Di;
инвариантное свойство смежных вершин сохраняется путем коррекции расстояний до них.
Построение минимального остового дерева. Алгоритм Прима-Ярвика. Удалив из графа некоторые ребра, можно превратить его в дерево. Если оно включает в себя все вершины исходного графа, то оно называется остовым. Кстати, в качестве его корня можно принять любую вершину, и в любом графе существует множество различных остовых деревьев. Задача состоит в построении дерева с минимальной суммой весов (значений нагруженных ребер). Идея «жадного» алгоритма состоит в присоединении на каждом шаге к минимальному дереву очередной вершины (само собой, находящейся вне дерева) с использованием ребра минимального веса. Обоснование алгоритма элементарно проводится методом математической индукции: при присоединении очередной вершины алгоритм сохраняется свойства «древовидности» (соединяя пару вершин в дереве и вне его) и «минимальности» - используя возможное ребро с минимальным весом. По аналогии с предыдущим алгоритмом множество вершин строящегося дерева называется «облаком».
//------------------------------------------------------86-03.cpp
// Построение остового дерева - алгоритм Прима-Ярвика
// Выбор минимального ребра "в облаке"-"вне облака"
#include "86-00.cpp"
void main(){
int N,**M,*P,i,k,j;
int sum=0,sum0=0;
if ((M=load_1("86-011.txt",N))==NULL) return;
P=new int[N]; // Массив отметок – в облаке
for (i=0;i<N;i++) P[i]=0;
P[0]=1; // Первая – в облаке
while(1){
int i1=-1,j1=-1; // Поиск кратчайшего ребра
for (i=0;i<N;i++) // Пропуск отмеченных, пустых
for (j=i+1;j<N;j++){ // и связывающих однотипные вершины
if (M[i][j]<=0 || P[i]==P[j]) continue;
if (j1==-1 || M[i][j]<M[i1][j1])
{ i1=i; j1=j; }
} // Запомнить индексы ребра
if (j1==-1) break; // Не найдено – дерево построено
sum+=M[i1][j1]; // Новая сумма весов дерева
M[i1][j1]=-M[i1][j1]; // Отметить ребро – инвертировать вес
M[j1][i1]=-M[j1][i1]; // Внести вершину «в облако»
if (P[i1]==1) P[j1]=1; else P[i1]=1;
}}Построение минимального остового дерева. Алгоритм Крускала. Другая индуктивно доказываемая идея – при объединении двух минимальных остовых поддеревьев через минимальное ребро получается минимальное остовое дерево на том же множестве вершин. Каждое поддерево называется кластером и первоначально все вершины исходного графа «сами себе поддеревья - кластеры». Затем в цикле ищется ребро с минимальным весом, соединяющее вершины разных кластеров, после чего два кластера сливаются в один, а ребро включается в остовое дерево, связанное с этим кластером. В результате получается единственный кластер – минимальное остовое дерево.
//--------------------------------------------------------86-04.cpp
// Построение остового дерева - алгоритм Крускала
// Слияние кластеров через минимальное ребро
void main(){
int N,**M,*D;
int i,k,j;
int sum=0;
if ((M=load_1("86-011.txt",N))==NULL) return;
D=new int[N];
for (i=0;i<N;i++) D[i]=i; // Каждый сам себе кластер
while(1){
int i1=-1,j1=-1; // Поиск минимального ребра в разных кластерах
for (i=0;i<N;i++) // Пропуск отмеченных, пустых
for (j=i+1;j<N;j++){ // и связывающих вершины в кластере
if (M[i][j]<=0 || D[i]==D[j]) continue;
if (j1==-1 || M[i][j]<M[i1][j1])
{ i1=i; j1=j; }
} // Запомнить индексы ребра
if (j1==-1) break; // Не найдено – дерево построено
sum+=M[i1][j1]; // Новая сумма весов дерева
M[i1][j1]=-M[i1][j1]; // Отметить ребро
M[j1][i1]=-M[j1][i1];
int P=D[j1]; // Слить кластеры
for (j=0;j<N;j++) if (D[j]==P) D[j]=D[i1];
}}Между двумя крайностями – полным рекурсивным перебором последовательностей вершин и «жадным» их присоединением – находятся алгоритмы, использующие промежуточные решения. К ним относится рассмотренный в 7.5 «волновой» алгоритм построения кратчайших путей. На основе явной очереди вершин алгоритм моделирует «волну», которая распространяется из исходной вершины. Когда она достигает некоторой вершины, то для вершины устанавливается значение пройденного «волной» пути и делаются попытки скорректировать этот же параметр у соседей. Если он корректируется в сторону уменьшения, то соседняя вершина также становится источником вторичной «волны» (т.е. помещается в очередь). Такой алгоритм не является «жадным», поскольку допускает повторную коррекцию расстояний у вершин, но он также далек от полного перебора. Оценку трудоемкости здесь проводить не будем.
