Неориентированный граф -- набор точек (вершин), некоторые из которых соединены линиями (ребрами). Неориентированный граф можно считать частным случаем ориентированного графа, в котором для каждой стрелки есть обратная.
Связной компонентой вершины i называется множество всех тех вершин, в которые можно попасть из i, идя по ребрам графа. (Поскольку граф неориентированный, отношение << j принадлежит связной компоненте i>> является отношением эквивалентности.)
7.4.5. Дан неориентированный граф (для каждой вершины указано
число соседей и массив номеров соседей, как в
задаче о топологической сортировке).
Составить алгоритм, который по заданному i печатает
все вершины связной компоненты i по одному разу (и только
их). Число действий не должно превосходить (общее
число вершин и ребер в связной компоненте).
procedure add (i:1..n); begin | if вершина i закрашена then begin | | ничего делать не надо | end else begin | | закрасить i (напечатать и пометить как закрашенную) | | для всех j, соседних с i | | | add(j); | | end; | end; end;Докажем, что эта процедура действует правильно (в предположении, что рекурсивные вызовы работают правильно). В самом деле, ничего, кроме связной компоненты незакрашенного графа, она закрасить не может. Проверим, что вся она будет закрашена. Пусть k -- вершина, доступная из вершины i по пути ,проходящему только по незакрашенным вершинам. Будем рассматривать только пути, не возвращающиеся снова в i. Из всех таких путей выберем путь с наименьшим j (в порядке просмотра соседей в процедуре). Тогда при рассмотрении предыдущих соседей ни одна из вершин пути не будет закрашена (иначе j не было бы минимальным) и потому k окажется в связной компоненте незакрашенного графа к моменту вызова add(j). Что и требовалось.
Чтобы установить конечность глубины рекурсии, заметим, что на каждом уровне рекурсии число незакрашенных вершин уменьшается хотя бы на 1.
Оценим число действий. Каждая вершина закрашивается не более одного раза -- при первым вызове add(i) с данным i. Все последующие вызовы происходят при закрашивании соседей -- количество таких вызовов не больше числа соседей -- и сводятся к проверке того, что вершина i уже закрашена. Первый же вызов состоит в просмотре всех соседей и рекурсивных вызовах add(j) для всех них. Таким образом, общее число действий, связанных с вершиной i, не превосходит константы, умноженной на число ее соседей. Отсюда и вытекает требуемая оценка.
7.4.6. Решить ту же задачу для ориентированного графа (напечатать
все вершины, доступные из данной по стрелкам; граф может
содержать циклы).