Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

Листинг 5.45. Выделение связных вершин графа 
void SetEdgeR(int v) 
{ 
if (!Nodes[v].visit) 
{ 
VisitTrue(v); 
Lib.myStack.Push(v); 
int LL = 0; 
if (Nodes[v].Edge != null) 
{ 
LL = Nodes[v].Edge.Length; 
for (int i = 0; i <= LL - 1; i++) 
SetEdgeR(Nodes[v].Edge[i].numNode); 
} 
} 
18 / 23

---

203 
} 
public void SetEdge(int s) 
{ 
ClearVisit(); 
Lib.myStack = new MyStack(); 
SetEdgeR(s); 
} 
Докажем, что эта функция работает правильно. В самом деле, ничего, 
кроме связной компоненты незакрашенного графа, она закрасить не может. 
Проверим, что вся она будет закрашена. 
Пусть k — вершина, доступная из вершины i по пути i—j— ... —k, про-
ходящему только по незакрашенным вершинам. Будем рассматривать только 
пути, не возвращающиеся снова в i. Из всех таких путей выберем путь с наи-
меньшим j в порядке просмотра соседей в цикле процедуры. Тогда при рас-
смотрении предыдущих соседей ни одна из вершин j— ... —k не будет за-
крашена (иначе j не было бы минимальным), и потому k окажется в связной 
компоненте незакрашенного графа к моменту вызова SetColor(j), что и 
требовалось. 
Чтобы установить конечность глубины рекурсии, заметим, что на каж-
дом уровне рекурсии число незакрашенных вершин уменьшается хотя бы 
на 1. Оценим число действий. Каждая вершина закрашивается не более одно-
го раза — при первым вызове SetColor(i) с данным i. Все последующие 
вызовы происходят при закрашивании соседей — количество таких вызовов 
не больше числа соседей и сводятся к проверке того, что вершина i уже за-
крашена. Первый же вызов состоит в просмотре всех соседей и рекурсивных 
вызовах SetColor(j) для них. Таким образом, общее число действий, свя-
занных с вершиной i, не превосходит константы, умноженной на число ее 
соседей. Отсюда и вытекает требуемая оценка.