Бағдарламалу технологиясы


Компьютер жадысында графты көретудің тәсілдері



жүктеу 1,63 Mb.
бет64/73
Дата03.02.2022
өлшемі1,63 Mb.
#35497
түріОқулық
1   ...   60   61   62   63   64   65   66   67   ...   73
Ба?дарламалу технологиясы

12.2 Компьютер жадысында графты көретудің тәсілдері

12.2.1 Графты түйістілік матрицасы (матрица инцидентностей) түрінде көрсету. 12.2-суретте көрсетілген қарапайым бағытталмаған граф берілсін.



12.2-сурет – Қарапайым бағытталмаған граф
Графтар теориясы бойынша ЭЕМ жадысында графты көрсетудің классикалық әдісі ретінде түйістілік матрицасы қолданылады. Осындай матрицада жолдардың саны төбелер санына, ал бағаналар саны граф қабырғаларының санына сәйкес болады. Егер төбе мен қабырға түйістілі болса, онда бағана мен жол қиылысында 1 жазылады, әйтпесе 0 жазылады.

12.2-суретте көрсетілген қарапайым бағытталмаған граф үшін 12.1-кестесінде көрсетілген түйістілік матрицасын құруға болады.


12.1-кесте – Түйістілік матрицасы


Егер доға сәйкес төбеден «шықса», онда бағытталған графта түйістілік матрицасындағы доға бағыты 1-ге тең, егер доға сәйкес төбеге «кіретін» болса, онда минус 1-ге тең.

12.3-суретте көрсетілген бағытталған граф үшін түйістілік матрицасын қарастырайық


12.3-сурет – Бағытталған граф


Бағытталған графтың түйістілік матрицасы 12.2-кестеде көрсетілген.
12.2-кесте – Бағытталған графтың түйістілік матрицасы


Айта кететін жәйт, түйістілік матрицалары ЭЕМ жадысында графтарды сақтаудың қолайсыз тәсілдердің бірі болып есептеледі, өйткені оның мәндері анық мәліметті бермейді. Мысалы, матрицаның өзінде 1-ші мен 2-ші төбелерінің байланысқанын анықтау мүмкін емес.

12.2.2 Графты сыбайлас матрица арқылы көрсету. Сыбайлас матрицада жолдар мен бағаналар саны төбелер санына тең.

Қиылыста осы төбелердің байланысын сипаттайтын мән орналасады, мысалы, егер қабырға болса, онда 1-ге, егер қабырға жоқ болса, онда 0-ге тең.

Бағытталған графтар үшін сыбайлас матрицада жолдар мен бағаналар саны төбелер санына тең.

Қиылыста осы төбелердің байланысын сипаттайтын мән орналасады, мысалы, егер сәйкес төбелер арасында байланыс бар болса, онда 1-ге, егер байланыс жоқ болса, онда 0-ге тең.

12.2-суретте көрсетілген граф үшін сыбайлас матрица 12.3-кестеде көрсетілген.


12.3-кесте – Сыбайлас матрица


12.3-суретте көрсетілген бағытталған граф үшін сыбайлас матрица 12.4-кестеге сәйкес келеді.
12.4-кесте – Бағытталған графтың сыбайлас матрицасы

12.2.3 Графты жұптар тізімі түрінде көрсету. Графты төбелердің сыбайлас жұптарының тізімі түрінде көрсету. Мысалы, жоғарыда ұсынылған графтарды төбелердің сыбайлас жұптарының тізімімен көрсетуге болады.

1-граф 2-граф

1) 1 – 2 1 – 2

2) 1 – 4 1 – 3

3) 1 – 5 3 – 2

4) 2 – 3 3 – 4

5) 2 – 4 5 – 4

6) 3 – 5 5 – 6

7) 3 – 6 6 – 5

8) 4 – 5 1– 2

9) 5 – 6 1– 2


Осы тізімдерді ЭЕМ жадында екі өлшемді массив түрінде көрсетуге болады. ЭЕМ жадында графтарды осы жолмен сақтау ең тиімді болып есептеледі, бірақ жұмыс жасауға үнемі қолайлы бола бермейді.

12.2.4 Сыбайлас төбелердің тізімі түрінде графты көрсету. Графтарға арналған кейбір есептерде граф төбелерін сыбайлас төбелердің тізімдік құрылымы түрінде көрсетуді талап етеді. Мысалы, стек, кезек, қарапайым тізім. Осы жағдайда әдетте сыбайлас төбелер тізімдерінің тақырыптары бойынша массив құрылады. Мысалы, 12.2-суретте көрсетілген графты тақырыптар массиві, графтың көршілес төбелерінің тізімі түрінде, төменде көрсетілгендей жазуға болады:

M[1]->1->2->4->5->NULL;
M[2]->2->1->3->4->NULL;
M[3]->3->2->5->6->NULL;
M[4]->4->1->2->5->NULL;
M[5]->5->3->4->6->NULL;
M[6]->6->3->5->NULL;
12.3-суретте көрсетілген графты тақырыптар массиві, графтың көршілес төбелерінің тізімі түрінде, төменде көрсетілгендей жазуға болады:

M[1]->1->2->3->NULL;


M[2]->2->NULL;
M[3]->3->2->4->NULL;
M[4]->4->NULL;
M[5]->5->4->6->NULL;
M[6]->6->5->NULL;

Графты көрсетудің осы формасы түрлі графты жүріп өту алгоритмдерін орындау үшін қолайлы.



жүктеу 1,63 Mb.

Достарыңызбен бөлісу:
1   ...   60   61   62   63   64   65   66   67   ...   73




©g.engime.org 2024
әкімшілігінің қараңыз

    Басты бет
рсетілетін қызмет
халықаралық қаржы
Астана халықаралық
қызмет регламенті
бекіту туралы
туралы ережені
орталығы туралы
субсидиялау мемлекеттік
кеңес туралы
ніндегі кеңес
орталығын басқару
қаржы орталығын
қаржы орталығы
құрамын бекіту
неркәсіптік кешен
міндетті құпия
болуына ерікті
тексерілу мемлекеттік
медициналық тексерілу
құпия медициналық
ерікті анонимді
Бастауыш тәлім
қатысуға жолдамалар
қызметшілері арасындағы
академиялық демалыс
алушыларға академиялық
білім алушыларға
ұйымдарында білім
туралы хабарландыру
конкурс туралы
мемлекеттік қызметшілері
мемлекеттік әкімшілік
органдардың мемлекеттік
мемлекеттік органдардың
барлық мемлекеттік
арналған барлық
орналасуға арналған
лауазымына орналасуға
әкімшілік лауазымына
инфекцияның болуына
жәрдемдесудің белсенді
шараларына қатысуға
саласындағы дайындаушы
ленген қосылған
шегінде бюджетке
салығы шегінде
есептелген қосылған
ұйымдарға есептелген
дайындаушы ұйымдарға
кешен саласындағы
сомасын субсидиялау