Теория:

Рассмотрим одну из часто встречающихся задач: найти длину кратчайшей цепи от заданной вершины до любой другой. Для решения этой задачи нам нужен волновой алгоритм.
Длина цепи — это количество ребер, которые содержатся в этой цепи.
Волновой алгоритм. Исходной вершине припишем число \(0\). Каждой смежной с ней вершине припишем число \(1\). Каждой вершине, смежной с той, которая уже помечена числом \(1\) и не была помечена раньше, приписываем число \(2\). Каждой вершине, смежной той, которая уже помечена числом \(2\) и не была помечена раньше, приписывают число \(3\). И так далее до тех пор, пока такое действие можно будет производить. При этом могут оказаться вершины, добраться до которых так и не удастся.
Пример:
На рисунке 1 показан результат обработки графа волновым алгоритмом после первого шага.
 
в1.png
 
Рис. 1
 
На рисунке 2 полностью обработанный результат обработки графа волновым алгоритмом.
 
в2.png
 
Рис. 2
Для волнового алгоритма граф указывается таблицей смежности, где таблицей смежности с \(20\) вершинами графа является целочисленный массив G[1:20;1:20]; результатом работы алгоритма — одномерный целочисленный массив \(P[1 : 20]\), для которого каждое значение элемента \(P[k]\) равно длине пути от заданной вершины с номером \(k\). Элементу \(P[k]\) присваивается значение \(-1\), если вершина с номером \(k\) недостижима.
 
Алгоритм Кратчайший путь
цел: \(I, J, A, K, \)G[1:20;1:20]\(, P[1 : 20]\);
{ Запросить G[1:20;1:20];
   Запросить \(A\);   (*запрашивается номер начальной вершины*)
   Делать от \(I := 1\) до \(20\) 
  {  \(P[I] := -1\);   (*сначала все элементы массива-результатов равны -1*)
   }
   \(P[A] := 0\);    (*до исходной вершины добираемся за \(0\) шагов*)
   Делать от \(I := 0\) до \(19\) 
  {  Делать от \(K := 1\) до \(20\) 
       {  Если \(P[K] = I\) то
           {  Делать от \(J := 1\) до \(20\) 
              {  Если (\(P[J] = -1\) и \(G[J, K] = 1\)) то
                  {  \(P[J] := I + 1\);
                  }
              }
           }
        }
   }
   Делать от \(I := 1\) до \(20\)
   {  Сообщить "Кратчайший путь от вершины", \(A\);
       Сообщить "до вершины", \(I\);
       Сообщить "равен", \(P[I]\);
   }
}
 
Пусть имеется какая-нибудь система связи, например компьютерная сеть. Такую сеть легко представить в виде графа, в котором узлы связи — это вершины графа, а линии связи — его ребра. Такой граф должен быть связным, чтобы информация из любого узла связи могла быть передана в любой другой. Если какой-либо узел выйдет из строя, то сохранялась возможность передачи информации из одного узла связи в любой другой.
Точка сочленения — это вершина связного графа, если после ее удаления из графа (вместе с входящими в нее ребрами) граф перестает быть связным. А ребро связного графа называется мостом, если после его удаления граф перестает быть связным.
Двусвязный граф — это связный граф, не имеющий точек сочленения.
Полный граф — это граф, у которго каждая вершина соединена со всеми остальными.
Пример:
На рисунке 3 изображен граф, у которого вершины D, E, F и H — точки сочленения, а ребра DE и HI — мосты.
 
г1.png
Рис. 3 
 
На рисунке 4 изображен двусвязный граф.
 
u2.png
Рис. 4
Источники:
Гейн А.Г., Сенокосов А.И. Информатика и ИКТ: учебник для общеобразовательных учреждений. - Москва: Просвещение, 2012. -230 с.