27-сур. Екінші ретті ағаштың ыдырауы
Ағаштың ыдырау
процесін мысал түрінде қарастырайық (27-сур.).
Бастапқы екінші ретті ағаш болсын (27 а-сур.), одан тізбектеп келесі
кілттерді жоюға болады: 25, 45, 24; 38, 32; 8, 27, 46, 13, 42; 5, 22; 18,26, 7, 35,
15; (; - секірістер, яғни беттерді босату)
Өздік жұмыс: мыналар үшін процедуралар құру:
1) Б-ағашта іздеу;
2) Б-ағашқа қосу;
3) Б-ағаштан жою.
Ұсынылатын әдебиет
1. Костин А.В., Шаньгин В.Ф. Организация и обработка структур
данных в вычислительных системах. – М. Высш. шк., 1987.
2. Вирт Н. Алгоритмы и структуры данных.- М.: Мир, 1988.
3. Вирт Н. Алгоритмы+ структуры данных= программы.-М.: Мир, 1985.
4. Ленгстайм Й., Огенстайм М., Тененбаум А. Структуры данных
для персональных ЭВМ.- М.: Мир,1989.
5. Флорес И. Структуры и управление данными.- М.: Финансы и
статистика, 1982.
6. Стоун Г. С., Сиворек Д. П. Введение в организацию ЭВМ и
структуры данных. – М.: Машиностроение, 1980.
7. Бауэр Ф. Л., Гооз Г. Информатика. Вводный курс. В двух частях.-
М.: Мир, 1990.
8. Яворский В. В., Богушевская А. А. Структуры данных и
алгоритмы их обработки.- Қарағанды: ҚарМТУ, 2004.- 150б.
СӨЖ үшін бақылау тапсырмалары
1. Деректердің ағаш түріндегі құрылымдары. Негізгі түсініктер.
2. Ағаштарды ЭЕМ-да көрсету.
3. Ағаштың құрылу процедуралары.
4. Бинарлы ағашты айналып өту.
5. Бинарлы ағашта іздеу.
6. Ағашқа жаңа түйінді қосу.
7. Ағаштан түйінді жою.
8. Аса бұтақталған ағаштар.
9. Б-ағаштар.
10. Б-ағаштардың қасиеттері.
11. Б-ағаштарда іздеу,
12. Б-ағашқа қосу.
13. Б-ағаштан жою.
8 БӨЛІМ
ГРАФТАРДАҒЫ АЛГОРИТМДЕР
Дәріс жоспары
1. Графтардың машиналық көрінісі
2. Графтағы тереңдікке іздеу
3. Графтағы еніне іздеу
4. Керуші ағаштар (каркастар)
5. Графтан циклдердің фундаменталды жиындырын табу
6. Графтағы Эйлер жолдары
7. Қайтымды алгоритмдер
8. Графтан ең қысқа жолдарды табу
9. Тіркелген шыңнан келетін ең қысқа жолдар
10.
Дейкстра алгоритмі
11.
Контурсыз графтағы жолдар
8.1 Графтардың машиналық көрінісі
Графтарды адамға үйреншікті әдіспен, яғни жазықтықтағы шыңдар
мен оларды қосатын қабырғалар (доғалар) түрінде көрсету – графтармен
байланысты ЭЕМ-да шешілетін мәселелер жағдайында мүлдем пайдасызы
анық. Графтарды көрсететін сәйкес деректер құрылымын таңдау
алгоритмдердің эффективтілігіне тікелей әсерін тигізеді. Сондықтан алдымен
бейнелеудің бірнеше әдісін көрсетіп, олардың артықшылықтары мен
кемшіліктерін талдайық.
Бағытталған және бағытталмаған графтарды да қарастырамыз. Графты
G=,
Деп белгілейміз, мұндағы V – шыңдар жиынтығы, ал Е – қабырғалар
жиынтығы, сонымен қоса
V
V
E
×
⊆
- бағытталған графтар үшін
}
^
,
:
}}
,
{{
y
x
V
y
x
y
x
E
≠
∈
⊆
- бағытталмаған графтар үшін.
Сонымен
қоса
m
Е
n
V
=
= ,
(жиынтық
қуаты)
белгіленулерін
қолданамыз.
Графтар теориясында графты көрсетудің классикалық әдісі болып
инциденциялар матрицасы табылады. Бұл шыңдарына сәйкес n жолы бар
және қабырғаларына сәйкес m бағандары бар А матрицасы. Бағытталған
граф үшін (х,у)€Е доғасына сәйкес келетін бағанның х шыңына сәйкес
келетін жолында +1 болса, у шыңына сәйкес келетін жолда -1, ал қалған
жолдарда 0 болады. Ілмек, яғни (х, х) түріндегі доғаны басқа мәнмен
көрсеткен қолайлы, мысалы х жолында 2 деп алсақ.
Бағытталмаған граф үшін {х, у} қабырғасына сәйкес бағанның х және у
–ке сәйкес жолдарында 1 болады, ал қалған жолдарда – 0 болады (28-сур., 29-
сур.).
28-сур. Бағытталған граф үшін инциденциялар матрицасы
29-сур. Бағытталмаған граф үшін инциденциялар матрицасы
Алгоритмдік көзқарастан алғанда инциденциялар матрицасы графты
көрсетудің ең нашар әдісі болып табылады, өйткені:
• жадының n * m ұяшығы керек, олардың көбі 0-мен толтырылған;
• ақпаратқа ену қолайсыз, өйткені (х, у) доғасы бар ма? Х-тен шығатын
қабырғалар қандай шыңдарға апарады? деген сұрақтарға жауап беру үшін
барлық бағандарды қарап шығуды талап етеді, яғни m қадам жасалады.
Одан гөрі графты өлшемі n*m болатын В=[b
ij
] сыбайластық матрицасы
арқылы көрсеткен жөн, мұнда b
ij
=1, х-тен у-ке апаратын қабырға болса, және
b
ij
= 0 – кері жағдайда. Сонымен қоса, бағытталмаған графтың {х, у}
қабырғасы х-тен у-ке қарай және у-тен х-ке қарай жүреді. Сондықтан
бағытталмаған граф үшін сыбайластық матрицасы әрқашан симметриялы
болады. Біздің графтар үшін сыбайластық матрицасы мынандай болады:
Сыбайластық матрицасының басты артықшылығы – бір қадам ішінде
(х, у) доғасы бар ма? Деген сұраққа жауап беруге болады. Кемшілігі –
қабырғалар санына тәуелсіз жадыдағы алатын көлемі n
2
құрайды. Іс жүзінде
бұл қолайсыздықты кейде бір жолды немесе бағанды бір машиналық сөзде
(кіші n жағдайында) сақтап түзетуге болады.
Графтарды қабырғаларына сәйкес жұптар тізімі ретінде көрсету жады
тұрғысынан алғанда (әсіресе тығыз емес графтар үшін, т п-нен әлдеқайда
кіші болса) үнемді болып табылады. Егер граф бағытталған болса, (х,у) жұбы
(х, у) доғасына сәйкес келеді, және, егер граф бағытталмаған болса {х,
у}қабырғасына сәйкес келеді. Біздің жағдайымызда жұптар тізімі:
Бұл жағдайда жады көлемі 2m құрайтыны белгілі. Ыңғайсыздықты
туғызатын бір жай – берілген шыңнан жүргізілетін қабырғалар қай шыңдарға
апаратынын табу үшін жасалатын қадам саны (нашар жағдайда m ретті).
Достарыңызбен бөлісу: |
