Пошук у глибину

Теорія

Існує багато алгоритмів на графах, в основі яких лежить систематичний перебір вершин графа, такий що кожна вершина переглядається в точності один раз. Тому важливою задачею є знаходження гарних методів пошуку в графі.

Опишемо такий метод пошуку у неорієнтованому графі, який став однією з основних методик проектування графових алгоритмів. Цей метод називається пошуком в глибину.

Загальна ідея цього метода полягає у наступному. Ми починаємо пошук з деякої фіксованої вершини v₀, потім обираємо довільну вершину u, суміжну з v₀, і повторюємо наш процес від u. В загальному випадку припустимо, що ми знаходимось у вершині v. Якщо існує нова (ще непереглянута) вершина u, така, що існує ребро (u, v), то ми розглядаємо цю вершину (вона перестає бути новою), і , починаючи з неї, продовжуємо пошук. Якщо ж не існує жодної нової вершини, суміжної з v, то ми говоримо, що вершина v використана, повертаємося у вершину, з якої ми потрапили у v, і продовжуємо процес (якщо v=v₀, то пошук закінчено). При виконанні обходу вглиб ми намагаємося проникнути вглиб графа так далеко, як це можливо, потім відступаємо на крок назад та знову намагаємося пройти вперед і таке інше.

Для того, що здійснювати обхід графа вглиб використовується структура даних стек (від англ. Stack - пачка, стос : у пачку кладуть зверху і беруть також зверху).

Стек можна уявити у вигляді трубки, запаяної з одного кінця. Наочною ілюстрацією такої трубки є магазин автомата чи гвинтівки. Особливістю магазина є те, що патрон у ньому можна покласти лише з одного кінця (через вікно магазину), при цьому патрони, що там були, протискуються вглиб. І вийняти патрон можна лише через вікно, з того ж кінця; при цьому у вікні з'являється новий патрон із глибини магазин. Легко помітити, що виймати патрони можна лише у порядку, зворотному тому, в якому ми їх клали - це і є особливістю магазину - стеку.

Стеки гарно моделюють стоси об'єктів, таких, як обідні тарілки. Коли тарілка миється, вона поміщається на верхівку стосу. Коли хтось захотів поїсти, то тарілка береться також з верхівки. Стек є належною структурою даних для розв'язання цієї задачі, оскільки все рівно, яка тарілка буде використана наступною.

Пошук у глибину.pptx

Задача

g1={1: [4, 5], 2: [3, 5, 7, 8], 3: [2, 5, 10], 4: [1,6, 8], 5: [1, 2,3,8,9]}

n=5

a=2

b=10

stek=[]

stek.append(a)

seen=[False]*n

seen[a]=True

while stek and seen[b]==False: # поки не завершаться вершини або поки не досягнемо потрібної

k=stek[len(stek)-1] #беремо останній елемент стеку

if len(g1[k])>0: #якщо до цього елемента ще є зв'язки

x=g1[k].pop(0) #вилучаємо перший зв'язок цього елемента

if seen[x]==False: #якщо його ще не розглядали

stek.append(x) #додаємо до стеку

seen[x]=True #і позначаємо розглянутим

elif len(g1[k])==0: # якщо в елемента більше немає зв'язків

stek.pop() # вилучаємо елемент зі стеку, це фактично повернення на крок назад

print(stek)