Х. ДосмҰхамедов
Ені бойынша іздеу (ағылш. Breadth-First search, BFS)
жүктеу/скачать 3 Mb.
|
| Ені бойынша іздеу (ағылш. Breadth-First search, BFS)
Графтың бір шыңынан басқасының барлығына қатысты қысқа жолдың ұзындығын (қабырғалар саны бойынша) анықтау үшін алгоритм қолданылады, ол ені бойынша іздеу (ағылш. Breadth-First search, BFS) деп аталады. Белгілі бір шыңнан бастап, іздеу оны аралық шыңдарына бағыттайды. Осы шыңдардан кейін олардың бұрын қарастырылмаған аралық шыңдарына бағытталады және т. с. с. Алгоритм жұмысы шоқтан алау оттың тарауына ұқсас. Жалын жанып жатқан шыңнан көршілеріне қарай кезекпен өтеді. Осылайша, жану аймағы «ені бойынша» үлкейеді. Іздеу процессі кезінде «жанған» шыңдар жиынға қосылады, ал бөлек жиында олардың жану көзінен алшақтығы (деңгейі) туралы ақпарат сақталады. Іздеу алгоритмі қарапайым: бастапқы шыңды кезекке кіргізу; кезектен бірінші шыңды алып тастап, оның кіріп-шығу деңгейін шыңдар тізіміне қосу; қарастырылмаған барлық аралық шыңды кезек тізіміне қосу; кезек бос болғанша 2 және 3-пунктерді қайталау. Алгоритм жұмысын нақты мысал арқылы қарастырайық. Бізге 5 шыңы бар граф берілсін. Басында бірде-бір шыңға кіріп шықпағандықтан, visited жиымындағы олардың әрқайсысында -1 мағынасы сақтаулы тұр, ал queue кезегі бос. 0 шыңынан іздеуді бастаймыз. Оны кезекке кіргіземіз. Бастапқы шың болғандықтан, оның деңгейі 0-ге тең. Оны «visited[0] = 0 жиым» деп белгілейміз. Кезектен алғашқы 0 шыңын аламыз. Кезекке оның барлық аралық шыңын (1, 2 және 3) қосамыз, себебі оларға бұрын кіріп-шықпаған. Олардың visited жиымындағы кіріп-шығу туралы ақпаратын өзгертеміз, сол уақытта шыңдар 1-деңгейде кіріп-шыққанын көреміз. Өткен қадамдарды қайталаймыз. Кезектен алғашқы шыңды аламыз. Қарастырылып отырған шың үш аралық шыңға ие. 0, 2 және 4. 0 және 2-шыңға кіріп-шыққан, сондықтан кезекке тек 4-шыңды қосып, оның кіріп-шығу деңгейін visited жиымында белгілейміз және ол бір бірлікке үлкен екенін байқаймыз, яғни visited[4] = 2. Тағы да кезекте тұрған бірінші шыңды аламыз. Бұл жолы кезек 2-шыңға келді. Ол үш аралық шыңға ие. Олар: 0, 1 және 4. Бірақ бұл шыңдарға бұрын кіріп-шыққандықтан, ешқайсысын кезекке қоспаймыз. Кезектегі 3 және 4-шыңдардың кіріп-шықпаған аралық шыңы жоқ. Сондықтан 4-шыңды қарастырғаннан кейін кезек бос болып, іздеу аяқталады. Осылайша, visited жиымында 0 шыңынан қалған әр шыңға өтуге арналған қажет қабырға саны туралы ақпарат сақталды. Біз қарастырған графтың бағдарламасына назар аударайық: Бұл кодтар кез келген бастапқы шыңнан іздеу орындауға мүмкіндік береді. Мысалы, 3 мәнін енгізген кезде 3-шыңынан басқа барлық шыңға қатысты қысқа жол ұзындығының (қабырға саны бойынша) тізімі шығарыды. Ол: [1, 2, 2, 0, 3]. жүктеу/скачать 3 Mb. Достарыңызбен бөлісу:
|