Първи по ширина алгоритми за търсене в графики - MathHelpPlanet
Дискусии и решаване на проблеми по математика, физика, химия, икономика
Часова зона: UTC + 3 часа [лятно часово време]
Въведение в анализа
Теория на опашките (QS)
Търсенето с дълбочина първо е един от начините за изграждане на максимално обхващащата гора. При първоначалното търсене в дълбочина всеки ръб, по който стигаме от текущия връх до предварително необозначен връх, ще бъде дърво. Всеки ръб, който не е дърво, ще бъде назад. Максималната обхващаща гора, открита от алгоритъма за търсене с дълбочина, се нарича дълбочина за обхващане на гората или дълбоко обхващаща гора.
Имайте предвид, че класификацията на ръбовете зависи от хода на алгоритъма, който се определя от началния връх и местоположението на върховете в списъците за съседство.
По този начин алгоритъмът за първо търсене в дълбочина в ненасочена графика може да се използва за изчисляване на набора от основни цикли на графика, т.е. решаване на една от задачите на глобалния анализ.
Имайте предвид, че не всяка максимална обхващаща гора може да бъде получена с помощта на алгоритъма за търсене на дълбочина първо. Например за графиката, показана на фиг. 5.23, разпределената максимална обхващаща гора не може да бъде получена при търсене в дълбочина, без значение от кой връх започваме търсенето.
За да се организира работата на алгоритъма за първо търсене в дълбочина, се използва метод за съхранение на данни, наречен стек. Елементите в стека се подреждат в реда, в който пристигат. Новите елементи могат да се добавят към стека и да се изскачат от него. В този случай е наличен само последният добавен елемент - горната част на стека, който определя режима на работа на стека (последно дошъл - първи вляво). Образно, стек може да бъде представен като стек от плочи. От стека може да се вземе само горната плоча, а нова може да се добави само към горната. Обикновено стекът се изпълнява като списък.
Алгоритъмът за първо търсене в дълбочина използва стек от върхове. Ще приемем, че информацията може да се чете от стека, без да се променя съдържанието му, но в реда, в който тя ще бъде премахната от стека. Ще ни е необходима посочената операция за четене, за да намерим основни цикли.
Алгоритъм за търсене с дълбочина първо
Вход. Графика [математика] G = (V, E) [/ математика], дадена от съседни списъци.
Изход. Наборите Дърво на дърво и Задни ръбове, съответно; набор [math] F_c [/ math] на основните цикли, масив [math] D [/ math], съдържащ D-числа на върховете.
0. Прегледайте масива от лидери и оформете множеството [math] V_0 [/ math] на върховете на графиката. Този набор се използва за съхраняване на нови (необработени от алгоритъма) върхове. По време на работата на алгоритъма обработените върхове ще бъдат премахнати от този набор.
По време на работата на алгоритъма, за всеки връх v е необходимо да се знае кои върхове от списъка му за съседство [math] L [v] [/ math] са били обработени при предишните стъпки на алгоритъма. За това се формира масив [math] L_p [/ math] с размер [math] | V_0 | [/ math], в който номерата на първите върхове на списъка за съседство [math] L [v] [/ math ] на всеки връх [математика] [/ математика]. Първоначално всички елементи на масива [math] L_p [/ math] са зададени равни на 1.
Задайте стека от STACK върхове и списъка от върхове на основния цикъл Цикъл празен [математика] (STACK = \ varnothing,
Наборите Дърво на ръбовете на дърво, Гърб на задни ръбове и [math] F_c [/ math] на основните цикли са празни [math] (Tree = \ varnothing,
Назад = \ varnothing, F_c = \ varnothing) [/ math]. Масив от D-числа [math] D [/ math] до нула.
Задайте началния връх за търсене [math] (v = v_0) [/ math]. (Обикновено това е първият връх на водещия масив.) Задайте брояча на D-числата на върховете count, равен на 1 (count = 1).
1. Ако множеството [math] V_0 [/ math] не е празно [math] (V_0 \ ne \ varnothing) [/ math], преминете към стъпка 2, в противен случай преминете към стъпка 8 (изход).
2. Ако стекът е празен [math] (STACK = \ varnothing) [/ math] и алгоритъмът започва от върха [math] v_0 [/ math] (count = 1), след това преминете към стъпка 3, в противен случай изберете от множеството [math] V_0 [/ math] произволен връх, от който ще продължи търсенето с дълбочина първо [math] (v = u, \, u \ in V_0) [/ math] и преминете към стъпка 3 .
3. Натиснете текущия връх [math] [/ math] върху стека STACK. Присвояване на връх [math] [/ math] D-число [math] (D [v] = count) [/ math]. Увеличете брояча на D-числа с 1 [math] (count = count + 1) [/ math]. Премахнете върха [math] [/ math] от множеството [math] V_0 [/ math] на нови върхове. Отидете на стъпка 4 .
4. Проверете от елемента [math] L_p [v] [/ math], че не е достигнат краят на списъка за съседство [math] L [v] [/ math] на текущия връх [math] [/ math] . Ако в списъка за съседство все още има необработени върхове, вземете следващия връх от списъка за съседство [math] w [/ math], увеличете [math] L_p [v] [/ math] с 1 и преминете към стъпка 6 .
Ако списъкът за съседство [math] L [v] [/ math] на връх v е обработен напълно, премахнете връх [math] [/ math] от стека STACK и преминете към стъпка 5 .
5. Ако стекът STACK е празен, върнете се към стъпка 1, в противен случай вземете върха в горната част на стека като текущ връх [math] [/ math] и преминете към стъпка 4 .
6. Ако върхът [math] w [/ math] е нов [math] (w \ in V_0) [/ math], след това добавете ръба [math] \ [/ math] към множеството ръбове на дърво
направете върха [math] w [/ math] текущ [math] (v = w) [/ math] и се върнете към стъпка 3. Ако върхът w не е нов [math] (w \ notin V_0) [/ math], преминете към стъпка 7 .