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

Егер доға сәйкес төбеден «шықса», онда бағытталған графта түйістілік 
матрицасындағы доға бағыты 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; 
Графты көрсетудің осы формасы түрлі графты жүріп өту алгоритмдерін 
орындау үшін қолайлы. 

жүктеу/скачать 332.21 Kb.

Достарыңызбен бөлісу: