Усвояне на похватите за представяне на графи в по, програмна реализация на графи и решаване на задачи над графи



Дата23.10.2018
Размер47.5 Kb.

ЛУ-10

Графи



Цел: Усвояне на похватите за представяне на графи в ПО, програмна реализация на графи и решаване на задачи над графи.

Теоретична част:

Алгоритмите за графи представляват голям интерес, защото голям брой задачи могат да се сведат до задачи над графи.[8]. Графът може да се разглежда като абстрактно представяне на реални обекти и системи. Например пътната мрежа в една област може да се представи чрез тегловен граф, в който възлите , например, са населените места, а ребрата са пътните връзки между тях, а теглата са разстоянията в км между отделните населени места. С графи могат да се представят още: железопътна, енергийна, водопроводна, отоплителна, компютърна или друга сехеми. Дори строежа на една молекула може да се представи чрез граф[8].

Представянето на граф може да бъде външно или вътрешно. Външното е чрез файл, а вътрешното – чрез матрица на съседство, два масива или чрез списък на съседство.

Един граф може да бъде ориентиран(насочен) или неориентиран (ненасочен, двупосочен).

Пример за представяне на насочен граф (фиг.10.1) чрез матрица на съседство, е даден в[9] - фиг.10.2. Представянето на дадения граф с два масива е направено на фиг.10.3.





0

1

0

0

0

2

0

0

1

0

0

3

0

0

0

0

0

4

0

1

1

0

0

5

1

0

0

1

0




1

2

3

4

5

фиг.10.1 Примерен насочен граф фиг.10.2 Матрица на съседство

На фиг.10.3 е дадено предтсавяне на графа с два масива G и N, при което в G за всеки възел, се записват последователно неговите съседни възли. В масива N , за всеки възел се задава индексът на първия му съседен възел от масива G.

Много алгоритми за графи са посветени на задачата за намиране на пътища от определен вид. Такава, например, е задачата за търговския пътник, при която се търси Хамилтонов цикъл при зададена определена


v


1

2

3

4

5

6

N[v]

1

2

3

4

6

8




k

1

2

3

4

5

6

7

8

G[k]

2

3

0

2

3

1

4

-

Фиг.10.3. Представяне на графа с два масива
оптимизационна функция (минимална стойност на маршрута).
Задача 1: Откриване на път между два възела с определена дължина

Задачата се формулира така: Да се определи дали в даден насочен граф съществува път с дължина К между два възела – А и В.

Алгоритмите за решаване на задачи с графи са предимно рекурсивни[8]. Идеята за рекурсивно решение на тази задача е следната: Път с дължина К, между А и В съществува , ако съществува съсседен на А връх С, такъв, че да съществува път от С до В с дължина (К-L ) , където L е дължина на пътя от А до С.

Една функция за реализиране на тази идея е следната:

void F_road(int k, int a, int b){

if(k==1)


if ( By_me(a,b))

fp=1;


else

fp=0;


else {

fp=0;


for (int i=1;i<=N;i++){

if (By_me(a,c))

if (F_road(k-1,c,b))

fp=1;


}

}

, а функцията By_me(int a, int b) връща 1 или 0 (истина или лъжа) ако връх b е съседен на a, или не е (съответно), и има следната дефиниция:



int By_me(int a, int b){

return matrix[a][b];



}

matrix[N][N] е двумерен масив, който представя матрицата на съседство на възлите на насочения граф. Елемeнтът matrix[a][b] =1, ако възли a и b са съседни, matrix[а][b] =0 - в противен случай.


Въпроси по темата и задачи за изпълнение:


1. Да се напише програма на С/С++, която използва горните две дадени функции (или техни модификации, реализирани от вас), при зададен свързан граф, определя дали има път с дължина К между два възела.

2. Напишете вариант на програмата от предходната задача, която да решава задачата за определяне дължината на пътя между два възела от насочен граф, ако такъв път съществува.
Каталог: docs -> Bachelor -> II%20Kurs -> Sem%20IV -> SAA
SAA -> Вероятностни алгоритми Цел: Упражняване в създаването и програмната реализация на вероятностни алгоритми Теоретична част
SAA -> Лекция №2 алгоритмично-програмни конструкции видове алгоритми
SAA -> Дървета Цел
SAA -> Евристически алгоритми
SAA -> Лекция №4 с о р т и р а н е и с м е с в а н е същност на сортирането
SAA -> Цел: Запознаване с метода за създаване на ефективно по – рекурсия. Създаване и използване на рекурсивни функции при решаване на сложни задачи. Теоретична част
SAA -> Лекция №3 Сложност на алгоритмите
Sem%20IV -> Eлектротехника и електроника
SAA -> Задача за "Ход на коня". Задача 1: Ход на коня
SAA -> Сортировка чрез вмъкване


Поделитесь с Вашими друзьями:




База данных защищена авторским правом ©obuch.info 2020
отнасят до администрацията

    Начална страница