Х. ДосмҰхамедов
Дәріс №13. Графтағы алгоритмдер
жүктеу/скачать 3 Mb.
|
- Бұл бет үшін навигация:
- Графтағы алгоритмдер.
| Дәріс №13. Графтағы алгоритмдер
Дәріс мақсаты: Студенттерге графтағы алгоритмдер ұғымы қарастырылады. Дәріс жоспары: Графтағы алгоритмдер. Тереңдігі (ағылш. depth-first search, DFS) бойынша іздеу Ені бойынша іздеу (ағылш. Breadth-First search, BFS) Графтағы алгоритмдер. Тағайындалған пунктке дейін біз қысқа жолды іздейміз. Мысалы, үйден дүкенге дейінгі жол немесе мектепке дейінгі жол. Біз әрдайым қысқа жолды іздеуге тырысамыз. Мысалы, бізге көлікпен Нұр-Сұлтан қаласынан Шымкент қаласына дейін бару қажет. Google картасы қысқа жолдың Қызылорда арқылы 1482 км болатынын көрсетеді. Егер біз сызба ретінде қарастырсақ, онда келесі сурет шығады: 1-сурет 2-сурет Қысқа жол есебін шешу алгоритмі ені бойынша іздеу деп аталады. Мұндай сызбаларды зерттеу үшін граф қолданылады, ол – қабырғалар деп аталатын шыңдар мен олардың арасындағы байланыс жинағы. Сызбаға сәйкес шыңдар мен граф байланыстары туралы ақпаратты сақтау үшін кесте-матрицаны қолданады, мұндай матрицаны аралық матрица деп атайды. Сызбамызға сәйкес келесі аралық матрицаны алуға болады: 3-сурет 1 – А және В кесінділері қиылысындағы аралық. Бұл олардың байланысын білдіреді, ал 0 мұндай байланыстың жоқ екенін білдіреді. Барлық шыңның өзара байланысуын санап шығып, олардың аралық тізімін құрастыруға болады. A (B, D) B (A, C) C (B, D) D (A, C) – матрицаға сәйкес аралық тізім 4-сурет Сызбадағы шың басқа шыңдармен байланысқан. Шыңдар арасындағы жол саналатын граф байланысшы деп аталады. Граф шыңдарын әріптермен және цифрлармен белгілеуге болады. Цифрлармен белгілеу ыңғайлы, себебі оларды индекс ретінде қолдануға болады. Сол индекс бойынша біз қажет шыңды тез таба аламыз. Егер графтағы әр қабырғаның белгілі мөлшерде салмағы болса, онда ол өлшенген граф деп аталады. Бірақ ол өлшем бірлігіне тәуелді емес. Тізімде 0 немесе 1 деп жазылмайды, қабырға салмағы жазылады. Ол салмақтық матрица деп аталады. 5-сурет 6-сурет Егер қабырғада бағыт болса, қабырғаның басы және соңы болады. Онда мұндай қабырғалар доға деп аталады. Ал граф бағытталған, яғни орграф деп аталады. Бірақ мұндай графтың салмақтық матрицасы симметриялы болмауы мүмкін. 7-сурет 8-сурет жүктеу/скачать 3 Mb. Достарыңызбен бөлісу:
|