Теория:

Пусть имеется связный граф. Это означает, что из любой вершины можно, двигаясь по ребрам, добраться до любой другой его вершины. Тогда можно составить алгоритм, позволяющий из заданной вершины совершить обход всех остальных вершин и, значит, заведомо добраться до нужно вершины. Но нельзя составить алгоритм, который позволяет по заданным вершинам построить путь из одной вершины в другую.
 
Рассмотрим несколько таких алгоритмов, которые можно составить.  
Алгоритм поиск в глубину. Пусть зафиксирована начальная вершина 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\).  
Метод поиск в глубину получил такое название за то, что при его реализации можно дальше уйти от исходной вершины, а когда идти уже некуда, возвращаемся в ту вершину, откуда идет хотя бы одно ребро в не пройденные еще вершины.
 
Если граф задан таблицей смежности, организуем одномерный массив \(В\), число элементов в котором совпадает с числом вершин в графе. На \(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;
    }
}
Источники:
Гейн А.Г., Сенокосов А.И. Информатика и ИКТ: учебник для общеобразовательных учреждений. - Москва: Просвещение, 2012. -227 с.