Теорія

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

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

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

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

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

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