Представление графа в программе.

Алгоритмы над графами

Обход графа в глубину

Пусть задан граф G = (V, E), где V — множество вершин графа, E — множество ребер графа. Предположим, что в начальный момент времени все вершины графа окрашены в белый цвет. Выполним следующие действия:

1. Из множества всех белых вершин выберем любую вершину, обозначим её v ₁.

2. Выполняем для неё процедуру DFS(v ₁).

3. Перекрашиваем её в чёрный цвет.

4. Повторяем шаги 1-3 до тех пор, пока множество белых вершин не пусто.

Процедура DFS (параметр — вершина )

1. Перекрашиваем вершину u в серый цвет.

2. Для всякой вершины w, смежной с вершиной u, выполняем следующие два шага:

1. Если вершина w окрашена в белый цвет, выполняем процедуру DFS(w).

2. Окрашиваем w в чёрный цвет.

Обход графа в ширину

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

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

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

Алгоритм обхода приведён ниже:

 

создадим пустую очередь открытых вершин;

пометим все вершины как "новые";

 

вершина Start помещается в очередь и помечается как открытая;

 

while(очередь не пуста) {

v=вершина в начале очереди;

для всех вершин, смежных с v {

v1=очередная вершина, смежная с v;

if(вершина v1 "новая"){

поместим её в очередь и пометим как открытую;

запомним ребро (v,v1) в массиве пройденных ребер

} // конец прохода вершин смежных с v

вершина v становится закрытой и удаляется из очереди;

занесем вершину v в массив посещенных вершин;

} // конец цикла "пока очередь не пуста"

 

Если компонента связности единственная в графе, то пройденные ребра образуют остовное дерево.

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

Поиск кратчайших путей.(Алгоритм Дейкстры).(wikipedia)

Алгоритм Де́йкстры — алгоритм на графах изобретенный нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса.

Пусть граф задан вершинами и ребрами. Каждому ребру iàj приписан вес (стоимость), равная C[i][j];

Пример.

Рассмотрим выполнение алгоритма на примере графа, показанного на рисунке. Пусть требуется найти расстояния от 1-й вершины до всех остальных.

На рисунке вершины помечены номерами, ребра – стоимостями. Рядом с каждой вершиной красным обозначена метка — длина кратчайшего пути в эту вершину из вершины 1.

Первый шаг. Рассмотрим шаг алгоритма Дейкстры для нашего примера. Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6.

Первый по очереди сосед вершины 1 — вершина 2, потому что длина пути до неё минимальна. Длина пути в неё через вершину 1 равна кратчайшему расстоянию до вершины 1 + длина ребра, идущего из 1 в 2, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2, поэтому новая метка 2-й вершины равна 7.

Аналогичную операцию проделываем с двумя другими соседями 1-й вершины — 3-й и 6-й.

Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит (то, что это действительно так, впервые доказал Дейкстра). Вычеркнем её из графа, чтобы отметить, что эта вершина посещена.

Второй шаг. Шаг алгоритма повторяется. Снова находим «ближайшую» из непосещенных вершин. Это вершина 2 с меткой 7.

Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю. Соседями вершины 2 являются 1, 3, 4.

Первый (по порядку) сосед вершины 2 — вершина 1. Но она уже посещена, поэтому с 1-й вершиной ничего не делаем.

Следующий сосед вершины 2 — вершина 3. Если идти в неё через 2, то длина такого пути будет = 7 + 10 = 17. Но текущая метка третьей вершины равна 9<17, поэтому метка не меняется.

Ещё один сосед вершины 2 — вершина 4. Если идти в неё через 2-ю, то длина такого пути будет = кратчайшее расстояние до 2 + расстояние между вершинами 2 и 4 = 7 + 15 = 22. Поскольку 22<∞, устанавливаем метку вершины 4 равной 22.

Все соседи вершины 2 просмотрены, замораживаем расстояние до неё и помечаем её как посещенную.

Третий шаг. Повторяем шаг алгоритма, выбрав вершину 3. После её «обработки» получим такие результаты:

Дальнейшие шаги. Повторяем шаг алгоритма для оставшихся вершин (Это будут по порядку 6, 4 и 5).

Завершение выполнения алгоритма. Алгоритм заканчивает работу, когда вычеркнуты все вершины. Результат его работы виден на последнем рисунке: кратчайший путь от вершины 1 до 2-й составляет 7, до 3-й — 9, до 4-й — 20, до 5-й — 20, до 6-й — 11.

 

Ниже приведен текст решения:

Определения структур

#define MAXREBRO 10 // максимальная степень вершины

#define MAXVERSH 20 // максимальное число вершин в графе

struct REBRO{

int w; // номер смежной вершины

float Weight; // вес ребра

};

struct VERSHINA{

int nSm; // число вершин, смежных с данной

REBRO Rebro[MAXREBRO];

bool Visited; // признак того, что вершина посещалась

float s; // минимальная стоимость пути от начальной вершины до данной

int Prev; // вершина предшествующая данной на кратчайшем пути к ней

};

struct GRAPH{

int nv; // число вершин в графе

VERSHINA Versh[MAXVERSH];

};

 

Implementation

//-------------------------------------------------

void Dijkstra(GRAPH *g, int Start){

// Подготовка к решению

// присвоим всем вершинам метки, равные бесконечности

// и пометим их как непосещенные

VERSHINA *v;

for(int i=0; i<g->nv; i++){

v=g->Versh+i;

v->s=FLT_MAX;

v->Visited=false;

}

// кроме стартовой

g->Versh[Start].s=0;

g->Versh[Start].Prev=-1; // у неё нет предыдущей

 

// сортируем смежные для каждой из вершин по весу ребер

// пузырек

bool b;

REBRO r;

REBRO *pv1,*pv2;

for(int i=0; i<g->nv; i++){

do{

b=false;

for(int j=0; j<g->Versh[i].nSm-1; j++){

pv1=g->Versh[i].Rebro+j;

pv2=pv1+1;

if(pv1->Weight>pv2->Weight){

memcpy(&r,pv1,sizeof(REBRO));

memcpy(pv1,pv2,sizeof(REBRO));

memcpy(pv2,&r,sizeof(REBRO));

b=true;

}

}

}while(b);

}

StepDijkstra(g, Start);

}

 

//---------------------------------------------------

void StepDijkstra(GRAPH *g, int Start){

int i,k;

float ToStart=g->Versh[Start].s; // текущая стоимость пути до вершины Start

float ww; // вес ребра Start-очередная смежная вершина

float sw; // текущая стоимость пути до очередной вершины

VERSHINA *v;

 

for(i=0; i < g->Versh[Start].nSm; i++){

k=g->Versh[Start].Rebro[i].w; // номер вершины, смежной со Start

// если k вершина посещалась - мимо

if(g->Versh[k].Visited){

continue;

}

ww=g->Versh[Start].Rebro[i].Weight; // вес ребра

sw=g->Versh[k].s; // уже достигнутый путь до вершины k

 

if(sw > ToStart+ww){

g->Versh[k].s=ToStart+ww; // новая длина пути для k вершины

g->Versh[k].Prev=Start; // запомним предыдущую для k

}

}

g->Versh[Start].Visited=true;

for(i=0; i<g->Versh[Start].nSm; i++){

k=g->Versh[Start].Rebro[i].w; // номер вершины, смежной со Start

// если k вершина посещалась - мимо

if(g->Versh[k].Visited){

continue;

}

StepDijkstra(g, k);

}

}

 

Алгоритм Прима

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

 

Идея алгоритма. Пусть часть остовного дерева уже построена. Это утверждения всегда верно, так как в начале процесса вершина с которой начинается построение уже входит в дерево. Итак если часть основного дерева уже есть, то множество вершин графа можно разделить на два подмножества: подмножество состоящее из вершин уже построенного остовного дерева и оставшихся вершин графа.

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

 

Алгоритм.

 

 Множество остовных вершин – исходная веришны

 Множество оставшихся - все вершины за исключением исходной.

 Пока множество оставшихся не пусто

o Ищем ребро соединяющее множество остовных и множество оставшихся и имеющее наименьший вес.

o Для найденного ребра, вершину принадлежащую множеству оставшихся:

 Вычеркиваем из множества оставшихся.

 Добавляем к множеству остовных.

Определение структур

#define INF 1000000 // бесконечность

struct REBRO{

int v1,v2,Cost;

};

struct GRAPH{

Implementation

// Предполагается, что все начальные установки в графе *gr выполнены

void PrimOstov(GRAPH *gr, int Start){

int i,j,ki,kj,MinCost,nIncluded=1,Cost;

bool b;

int nr=0; // число ребер в остовном дереве

gr->Included[Start]=true; // стартовая вершина включается в остовное дерево

nIncluded=1;

while(nIncluded<gr->nVersh){ // пока все вершины не будут включены

ki=0;

kj=0; // ki,kj - ребро будет ребром минимальной стоимости

MinCost=INF;

// ищем минимальное ребро, одна вершина которого

// уже входит в остовное

// дерево, а вторая ещё нет

for(i=0; i<gr->nVersh; i++){

if(gr->Included[i]){

for(j=0; j<gr->nVersh; j++){

b=!gr->Included[j];

Cost=gr->m[i][j];

if(b && Cost<MinCost){

ki=i;

kj=j;

MinCost=Cost;

} // if

} // for j

} // if(gr->Included[i])

} // for i

// включаем ребро в остовное дерево

gr->OstovRebro[nr].v1=ki;

gr->OstovRebro[nr].v2=kj;

gr->OstovRebro[nr].Cost=MinCost;

gr->Included[kj]=true;

nIncluded++;

nr++;

} // while

gr->nOstovReber=nr;

}

Алгоритм Краскала

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

 

Идея алгоритма. Искомые ребра соединяют вершины. Поэтому возможны две стратегии построения. Можно идти от вершин и для каждой из них искать минимальное ребро (как это сделано в алгоритме Прима) а можно для каждого ребра выяснять можно ли его включить в строящееся дерево. Алгоритм Краскала предлагает делать это следующим образом. Во-первых, ребра графа пронумеровываем в порядке возрастания весов. Затем для каждого ребра начиная с первого проверяем соединяет или нет оно две несвязные вершины, если да, то его можно включить в остовное дерево. Ясно, что если мы имеем V вершин, то работа алгоритма начинается с V несвязных компонент графа (пока из графа все ребра исключаем). Для того, чтобы их связать необходимо найти V-1 ребро.

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

 

Структуры данных. В алгоритме используется термин «компонента связности». Такой конструкции нет ни в одном языке программирования. Это исключительно математический термин, поэтому для конкретной реализации алгоритма необходимо тщательно продумать вопрос о представлении «компоненты связности» существующими языковыми конструкциями.

 

Алгоритм

1. Создаем список ребер по возрастанию.

2. Создаем множество компонент связности каждая из которых содержит ровно одну вершину.

3. Пока компонент связности больше чем одна.

3.1. Взять ребро из начала списка ребер.

3.2. Если ребро соединяет две разных компоненты связности то

3.2.1. Компоненты связности объединить в одну.

 

Определение структур

struct REBRO{

int v1,v2,Cost;

};

struct GRAPH{

Implementation

void KruskalOstov(GRAPH *gr){

// эту функцию НАПИШИТЕ САМИ

int i,j;

Представление графа в программе.

Пусть дан смешанный граф:

Рис. 6. Смешанный граф.

Известно несколько способов представлений графа G=(V, Е) в памяти компьютера.

Матрица смежности.

Матрица смежности - это матрица размером n×n, в которой c_ij =1, если существует ребро из i в j и c_ij =0 в противном случае.

Например для вышеприведенного графа матрица смежности будет иметь следующий вид:

	1	2	3	4	5
1
2
3
4
5

Для неориентированного графа справедливо c_ij = c_ji и матрица смежности симметрична.

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

 

В тех случаях, когда ребра имеют веса (например, роль веса играет расстояние между вершинами или стоимость перемещения из вершины в вершину), элементы матрицы смежности – веса рёбер. Признаком отсутствия ребра в этом случае является не 0, а ∞, что означает бесконечно большое расстояние или стоимость. В качестве значения ∞ в программе можно использовать FLT_MAX для величин типа float и DBL_MAX для double, определённые в float.h.

 

Данные, хранимые в матрице смежности, могут быть представлены также массивом структур, содержащим списки смежности, вида:

struct VERSHINA {

int nr; // число вершин, смежных с данных

int *sm; // массив номеров вершин, смежных с данной

};

Массив можно заменить линейным списком.

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

struct REBRO{

int w; // номер смежной вершины

<свойства ребра>;

};

struct VERSHINA{

<свойства вершины>;

int nr; // число вершин, смежных данной (число ребер)

REBRO *Rebro; // массив рёбер

};

struct GRAPH{

int nv; // число вершин

VERSHINA *v; // массив вершин

};

Массивы могут быть заменены на списки.

 

Матрица инцидентности

Матрица инцидентности — одна из форм представления графа, в которой указываются связи между инцидентными элементами графа (ребро(дуга) и вершина). Столбцы матрицы соответствуют ребрам, строки — вершинам. Ненулевое значение в ячейке матрицы указывает связь между вершиной и ребром (их инцидентность).

В случае ориентированного графа каждому ребру <x,y> ставится в соответствие "-1" на позиции (x,y) и "1" на позиции (y,x); если связи между вершинами нет, то ставится в соответствие "0".

Пример

Граф	Матрица инцидентности

 

В каждом столбце должны стоять две единицы, а все остальные символы - нули.

Массив ребер.

Массив ребер – это массив, в котором ребра хранятся парами вершин, которые они соединяют.

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

struct REBRO{

int v,w; // вершины

float Weight; // вес ребра

};

Для представления конечного автомата структура могла бы иметь вид:

struct REBRO{

int v,w; // состояния автомата

int Symbol; // входной символ

void (*f)(); // функция, выполняемая на переходе

};

 

Для не ориентированного графа можно при наличии описания ребра (v,w) не включать описание (w,v);

Алгоритмы над графами

Обход графа в глубину

Пусть задан граф G = (V, E), где V — множество вершин графа, E — множество ребер графа. Предположим, что в начальный момент времени все вершины графа окрашены в белый цвет. Выполним следующие действия:

1. Из множества всех белых вершин выберем любую вершину, обозначим её v ₁.

2. Выполняем для неё процедуру DFS(v ₁).

3. Перекрашиваем её в чёрный цвет.

4. Повторяем шаги 1-3 до тех пор, пока множество белых вершин не пусто.

Процедура DFS (параметр — вершина )

1. Перекрашиваем вершину u в серый цвет.

2. Для всякой вершины w, смежной с вершиной u, выполняем следующие два шага:

1. Если вершина w окрашена в белый цвет, выполняем процедуру DFS(w).

2. Окрашиваем w в чёрный цвет.

Обход графа в ширину

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

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

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

Алгоритм обхода приведён ниже:

 

создадим пустую очередь открытых вершин;

пометим все вершины как "новые";

 

вершина Start помещается в очередь и помечается как открытая;

 

while(очередь не пуста) {

v=вершина в начале очереди;

для всех вершин, смежных с v {

v1=очередная вершина, смежная с v;

if(вершина v1 "новая"){

поместим её в очередь и пометим как открытую;

запомним ребро (v,v1) в массиве пройденных ребер

} // конец прохода вершин смежных с v

вершина v становится закрытой и удаляется из очереди;

занесем вершину v в массив посещенных вершин;

} // конец цикла "пока очередь не пуста"

 

Если компонента связности единственная в графе, то пройденные ребра образуют остовное дерево.

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

Поиск кратчайших путей.(Алгоритм Дейкстры).(wikipedia)

Алгоритм Де́йкстры — алгоритм на графах изобретенный нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса.

Пусть граф задан вершинами и ребрами. Каждому ребру iàj приписан вес (стоимость), равная C[i][j];

Пример.

Рассмотрим выполнение алгоритма на примере графа, показанного на рисунке. Пусть требуется найти расстояния от 1-й вершины до всех остальных.

На рисунке вершины помечены номерами, ребра – стоимостями. Рядом с каждой вершиной красным обозначена метка — длина кратчайшего пути в эту вершину из вершины 1.

Первый шаг. Рассмотрим шаг алгоритма Дейкстры для нашего примера. Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6.

Первый по очереди сосед вершины 1 — вершина 2, потому что длина пути до неё минимальна. Длина пути в неё через вершину 1 равна кратчайшему расстоянию до вершины 1 + длина ребра, идущего из 1 в 2, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2, поэтому новая метка 2-й вершины равна 7.

Аналогичную операцию проделываем с двумя другими соседями 1-й вершины — 3-й и 6-й.

Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит (то, что это действительно так, впервые доказал Дейкстра). Вычеркнем её из графа, чтобы отметить, что эта вершина посещена.

Второй шаг. Шаг алгоритма повторяется. Снова находим «ближайшую» из непосещенных вершин. Это вершина 2 с меткой 7.

Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю. Соседями вершины 2 являются 1, 3, 4.

Первый (по порядку) сосед вершины 2 — вершина 1. Но она уже посещена, поэтому с 1-й вершиной ничего не делаем.

Следующий сосед вершины 2 — вершина 3. Если идти в неё через 2, то длина такого пути будет = 7 + 10 = 17. Но текущая метка третьей вершины равна 9<17, поэтому метка не меняется.

Ещё один сосед вершины 2 — вершина 4. Если идти в неё через 2-ю, то длина такого пути будет = кратчайшее расстояние до 2 + расстояние между вершинами 2 и 4 = 7 + 15 = 22. Поскольку 22<∞, устанавливаем метку вершины 4 равной 22.

Все соседи вершины 2 просмотрены, замораживаем расстояние до неё и помечаем её как посещенную.

Третий шаг. Повторяем шаг алгоритма, выбрав вершину 3. После её «обработки» получим такие результаты:

Дальнейшие шаги. Повторяем шаг алгоритма для оставшихся вершин (Это будут по порядку 6, 4 и 5).

Завершение выполнения алгоритма. Алгоритм заканчивает работу, когда вычеркнуты все вершины. Результат его работы виден на последнем рисунке: кратчайший путь от вершины 1 до 2-й составляет 7, до 3-й — 9, до 4-й — 20, до 5-й — 20, до 6-й — 11.

 

Ниже приведен текст решения:

Определения структур

#define MAXREBRO 10 // максимальная степень вершины

#define MAXVERSH 20 // максимальное число вершин в графе

struct REBRO{

int w; // номер смежной вершины

float Weight; // вес ребра

};

struct VERSHINA{

int nSm; // число вершин, смежных с данной

REBRO Rebro[MAXREBRO];

bool Visited; // признак того, что вершина посещалась

float s; // минимальная стоимость пути от начальной вершины до данной

int Prev; // вершина предшествующая данной на кратчайшем пути к ней

};

struct GRAPH{

int nv; // число вершин в графе

VERSHINA Versh[MAXVERSH];

};

 

Implementation

//-------------------------------------------------

void Dijkstra(GRAPH *g, int Start){

// Подготовка к решению

// присвоим всем вершинам метки, равные бесконечности

// и пометим их как непосещенные

VERSHINA *v;

for(int i=0; i<g->nv; i++){

v=g->Versh+i;

v->s=FLT_MAX;

v->Visited=false;

}

// кроме стартовой

g->Versh[Start].s=0;

g->Versh[Start].Prev=-1; // у неё нет предыдущей

 

// сортируем смежные для каждой из вершин по весу ребер

// пузырек

bool b;

REBRO r;

REBRO *pv1,*pv2;

for(int i=0; i<g->nv; i++){

do{

b=false;

for(int j=0; j<g->Versh[i].nSm-1; j++){

pv1=g->Versh[i].Rebro+j;

pv2=pv1+1;

if(pv1->Weight>pv2->Weight){

memcpy(&r,pv1,sizeof(REBRO));

memcpy(pv1,pv2,sizeof(REBRO));

memcpy(pv2,&r,sizeof(REBRO));

b=true;

}

}

}while(b);

}

StepDijkstra(g, Start);

}

 

//---------------------------------------------------

void StepDijkstra(GRAPH *g, int Start){

int i,k;

float ToStart=g->Versh[Start].s; // текущая стоимость пути до вершины Start

float ww; // вес ребра Start-очередная смежная вершина

float sw; // текущая стоимость пути до очередной вершины

VERSHINA *v;

 

for(i=0; i < g->Versh[Start].nSm; i++){

k=g->Versh[Start].Rebro[i].w; // номер вершины, смежной со Start

// если k вершина посещалась - мимо

if(g->Versh[k].Visited){

continue;

}

ww=g->Versh[Start].Rebro[i].Weight; // вес ребра

sw=g->Versh[k].s; // уже достигнутый путь до вершины k

 

if(sw > ToStart+ww){

g->Versh[k].s=ToStart+ww; // новая длина пути для k вершины

g->Versh[k].Prev=Start; // запомним предыдущую для k

}

}

g->Versh[Start].Visited=true;

for(i=0; i<g->Versh[Start].nSm; i++){

k=g->Versh[Start].Rebro[i].w; // номер вершины, смежной со Start

// если k вершина посещалась - мимо

if(g->Versh[k].Visited){

continue;

}

StepDijkstra(g, k);

}

}

 

Алгоритм Прима

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

 

Идея алгоритма. Пусть часть остовного дерева уже построена. Это утверждения всегда верно, так как в начале процесса вершина с которой начинается построение уже входит в дерево. Итак если часть основного дерева уже есть, то множество вершин графа можно разделить на два подмножества: подмножество состоящее из вершин уже построенного остовного дерева и оставшихся вершин графа.

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

 

Алгоритм.

 

 Множество остовных вершин – исходная веришны

 Множество оставшихся - все вершины за исключением исходной.

 Пока множество оставшихся не пусто

o Ищем ребро соединяющее множество остовных и множество оставшихся и имеющее наименьший вес.

o Для найденного ребра, вершину принадлежащую множеству оставшихся:

 Вычеркиваем из множества оставшихся.

 Добавляем к множеству остовных.

Определение структур

#define INF 1000000 // бесконечность

struct REBRO{

int v1,v2,Cost;

};

struct GRAPH{