Теория:

Пусть имеется связный граф. Это означает, что из любой вершины можно, двигаясь по ребрам, добраться до любой другой его вершины. Тогда можно составить алгоритм, позволяющий из заданной вершины совершить обход всех остальных вершин и, значит, заведомо добраться до нужно вершины. Но нельзя составить алгоритм, который позволяет по заданным вершинам построить путь из одной вершины в другую.
 
Рассмотрим несколько таких алгоритмов, которые можно составить.  
Алгоритм поиск в глубину. Пусть зафиксирована начальная вершина v0. Выберем смежную с ней вершину v1. Затем для вершины v1 выбираем смежную с ней вершину из числа еще не выбранных вершин и т.д.: если мы уже выбрали вершины v0,v1,...,vk, то следующая вершина выбирается смежной с вершиной vk из числа невыбранных. Если для вершины vk такой вершины не нашлось, то возвращаемся к вершине vk1 и для нее ищем смежную среди невыбранных. При необходимости возвращаемся назад и т.д. Так будут перебраны все вершины графа и поиск закончится.
Пример:
На рисунках 1 и 2 показаны реализации поиска в глубину для одного и того же графа (начальная вершина — \(0\)).
 
а1.png 
Рис. 1
  
а2.png
Рис. 2
 
Порядок  обхода графа с помощью алгоритма поиск в глубину для рисунка 1 — \(0, 1, 2, 3, 4, 5, 6, 9, 7, 10, 11, 8\), а для рисунка 2 — \(0, 1, 2, 4, 5, 3, 6, 7, 8, 9, 10, 11\).  
Метод поиск в глубину получил такое название за то, что при его реализации можно дальше уйти от исходной вершины, а когда идти уже некуда, возвращаемся в ту вершину, откуда идет хотя бы одно ребро в не пройденные еще вершины.
 
Рассмотрим граф, который задан таблицей смежности, и построим для него одномерный массив \(B\). Число вершин в графе — число элементов массива.
Номер вершины, в которую мы пришли на \(k-м\) шаге, будем записывать на \(k-м\)  месте нашего массива. Из всех смежных вершин будем выбирать вершину с наименьшим номером.
 
Реализуем поиск в глубину с помощью алгоритма.
  
Алгоритм Поиск в глубину
цел: \(k, m, s, t, u, n, a, v, i, G[1: n; 1: n], B[1: n]\);
{ Запросить \(n\);    (*запрос количества вершин*)
   Запросить G1:n;1:n;   (*вводим таблицу смежности, которая оформляется двойным циклом*)
   B1:=1;   (*исходная вершина — 1*)
   Делать от \(k := 2\) до \(n\)
  {  Bk:=0;
   }
   \(k := 1\);   (*счетчик количества пройденных вершин*)
   \(m := 0\);   (*k - m — порядковый номер вершины для следующего шага поиска*)
   Делать пока (\(k < n\))
   {  \(s := 1\);
      Делать от \(t := 1\) до \(n\)
      {  \(v := 1\);
         Делать от \(i := 1\) до \(k\)
         {  Если (Bi=t) то { \(v := 0\); } }
          Если ( \(v = 1\) иGBkm,t=1) то
          { \(a := t\);
            \(s := 0\);
          }
       }
 (*проверим есть ли еще вершины, которые не просматривались, если есть то  \(s = 0\)*)
       Если (\(s = 0\)) то
       {  \(k := k + 1\);
           Bk:=a;
           \(m := 0\);
        }
        иначе  { \(m := m + 1\); }
     }
     Делать от \(k := 1\) до \(n\)
    { Сообщить Bk,k;
    }
}
Алгоритм поиск в ширину. Пусть зафиксирована начальная вершина v0. Рассматриваем все смежные с ней вершины v1,v2,...,vk. Затем рассматриваем смежные вершины каждой из рассмотренных вершин v1,v2,...,vk, и т.д. Так будут перебраны все вершины графа и поиск закончится.
Пример:
На рисунках 3 и 4 показаны реализации поиска в ширину для одного и того же графа (начальная вершина — \(0\)).
 
б1.png
Рис. 3
   
б2.png
Рис. 4
 
Порядок  обхода графа с помощью алгоритма поиск в ширину для рисунка 3 — \(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 1,0, 11\), а для рисунка 4 — \(0, 1, 2, 3, 4, 5, 6, 10, 7, 8, 9, 11, 12\).
Алгоритм, реализующий поиск в ширину:
  
Алгоритм Поиск в ширину
цел: \(k, m, s, t, n, G[1: n; 1: n], B[1: n]\);
{ Запросить \(n\);    (*запрашивается количество вершин*)
   Запросить G1:n;1:n;   (*реально это действие — ввод таблицы смежности — оформляется двойным циклом*)
   B1:=1;   (*в качестве исходной взята вершина с номером 1*)
   Делать от \(k := 2\) до \(n\)
  {  Bk:=0;
   }
   \(s := 1\);
   Делать от \(k := 2\) до \(n\)
   {  \(t := 1\);     
       \(m := -1\);
       Делать пока (Gs,t=0 или\(t = s\) или Bt0)
      { \(t := t + 1\);
      }
      Если (\(t < n + 1\)) то
      {  Bt:=k;
          \(m := m + 1\);
       }
       иначе
       { \(s := k - m\);
        }
    }
    Делать от \(k := 1\) до \(n\)
    { Сообщить Bk,k;
    }
}