Пошук в глибину (або обхід в глибину) є одним з основних і найбільш часто вживаних алгоритмів обходу всіх вершин і ребер графа. Згідно з цим алгоритмом обхід здійснюється за наступним правилом: у графі G вибираємо довільну вершину, наприклад a, і починаємо з неї пошук. Початкова вершина a (називається коренем пошуку в глибину) після цього вважається пройденою. На наступному кроці, вибираємо ребро (a,b), інцидентне вершині a (орієнтуємо при цьому його напрямок з a в b), і з його допомогою, переходимо у вершину b. Відмітимо, що ребро (a,b)після цих дій вважається переглянутим і називається ребром дерева, а вершина називається батьківською по відношенню до вершини b.
У загальному випадку, коли ми перейшли в будь-яку вершину графа, в нашому випадку це вершина b, виникають два варіанти можливих дій:
-Якщо всі ребра, інцидентні b, вже переглянуті, то повертаємося до батьківської вершини для b і продовжуємо пошук з цієї вершини. Вершина b з цього моменту називатиметься повністю сканованою.
-Якщо існують не переглянуті ребра, інцидентні b, то вибираємо одне з таких ребер, наприклад, (b,c) і орієнтуємо його з b в c. Ребро (b,c) з цього моменту вважатиметься переглянутим. При цьому, необхідно розглянути два випадки: якщо c раніше не була пройдена, то використовуючи ребро (b,c) переходимо у вершину c і продовжуємо пошук з неї. В цьому випадку ребро (b,c) називається ребром дерева, а вершина b — батьком вершини c; якщо c раніше була пройдена, то продовжуємо пошук іншого не пройденого ребра, інцидентного b. В цьому випадку ребро (b,c) називається зворотним ребром.

Зауваження: під час пошуку в глибину, коли вершину b проходять вперший раз, їй зіставляється ціле число i, якщо b є i-ю по порядку проходження вершиною і яке називається глибиною b. Ясно, що глибина вказує порядок, в якому проходять вершини при пошуку в глибину.
Обхід графа в глибину завершується, коли ми повертаємося в корінь і всі вершини графа пройдені. Якщо після повернення в корінь залишаються не пройдені вершини, можна вибрати одну з них і повторювати процес, і робити так до тих пір, поки не пройдемо всі вершини графа.
З всього сказаного вище можна зробити висновок, що пошук в глибину розбиває ребра графа G на ребра дерева і зворотні ребра. Легко помітити, що ребра дерева утворюють остов графа G. Також хочеться зазначити, що пошук в глибину вводить орієнтацію на ребра графа G. Одержуваний в результаті орієнтований граф ми будемо позначати через G. Ребра дерева з орієнтацією утворюватимуть орієнтований остов G. Цей орієнтований остов будемо називати деревом пошуку в глибину. Відмітимо, що спосіб проходження графа з допомогою даного дереве не є єдиним, так як ребра, інцидентні вершині, можуть вибиратись для розгляду в довільному порядку.
Обхід графа в глибину — приклад:
Використовуючи розглянутий алгоритм побудувати дерево пошуку в глибину наступного неорієнтованого графа:

Отже, починаючи з довільно обраної вершини, наприклад вершини номер «1» рухаємося по першому зустрічному нам ребру (1,2). Так як вершину «2» ми ніколи раніше не відвідували, залишаємося в «2» і проходимо по першому не пройденому ребру, інцидентному «2», а саме (2,3). Тепер у вершині «3» першим не пройденим ребром являється ребро (3,1). Проходимо його і виявляємо, що вершина «1» вже відвідувалася раніше. Тому повертаємося в «3» і помічаємо ребро (3,1) як зворотне (пунктирною лінією). Повернувшись у вершину «3», шукаємо інше не пройдене ребро і йдемо по першому зустрічному з них, скажімо (3,4). Так як «4» — нова вершина, залишаємося в ній і шукаємо не пройдене ребро. В даному випадку таким являється ребро (4,2). Оскільки вершина «2» відвідувалася раніше, позначати ребро (4,2) пунктирною лінією і повертаємося в «4». Через те, що не пройденних ребер, інцидентних «4», не залишилось, повертаємрся у «3».
Побудова дерева обходу в глубину для неорієнтованого графа
У «3» виявляємо не пройдене ребро (3,5) і проходимо його. Оскільки «5» — нова вершина, залишаємося в ній і шукаємо не прйдене інцидентне їй ребро, яким являється ребро (5,1). Так як «1» — вже пройдена вершина, помічаємо ребро (5,1) пунктирною лінією. Тепер вершина «5» повністю переглянута, що свідчить про те, що необхідно повернутись у батьківську по відношенню до неї, тобто у вуршину «3». У «3» немає ребер, що залишилися не пройденими, тому, аналогічним чином, рухаємося назад в «2» і, нарешті, в «1». Всі ребра, інцидентні «1», пройдені, що означає кінець процедури.