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

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

жүктеу 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