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

Листинг 5.44. Ракраска ребер минимального остова 
void SetColorEdge() 
{ 
while (!Lib.myStack.isEmpty()) 
{ 
int t = (int)Lib.myStack.Pop();
// 
взять из стека № ребра 
int N = Nodes.Length; 
for (int i = 0; i <= N - 1; i++) 
{ 
16 / 23

---

201 
int LL = 0; 
if (Nodes[i].Edge != null) 
{ 
LL = Nodes[i].Edge.Length; 
for (int j = 0; j <= LL - 1; j++) 
if (((i == Edges[t].n1) &&
(Nodes[i].Edge[j].numNode ==
Edges[t].n2)) | 
((i == Edges[t].n2) &&
(Nodes[i].Edge[j].numNode ==
Edges[t].n1))) 
SetEdgeBlack(i, j);
// 
закрасить ребро 
} 
} 
} 
} 
Результат работы алгоритма представлен на рисунке 5.25. 
Рис. 5.25. Раскраска ребер минимального остова 
17 / 23

---

202 
5.8.4. В
ЫДЕЛЕНИЕ КОМПОНЕНТ СВЯЗНОСТИ
 
Неориентированный граф – это набор точек (вершин), некоторые из 
которых соединены ребрами. Неориентированный граф можно считать част-
ным случаем ориентированного графа, в котором для каждого ребра есть об-
ратное ребро. 
Связной компонентой вершины i называется множество всех тех вер-
шин, в которые можно попасть из i, идя по ребрам графа. Поскольку граф 
неориентированный, отношение «j принадлежит связной компоненте i» явля-
ется отношением эквивалентности. 
Пусть дан неориентированный граф, для каждой вершины указано чис-
ло соседей и массив номеров соседей, как в предыдущей задаче. Составить 
алгоритм, который по заданному i печатает все вершины связной компонен-
ты i по одному разу (и только их). Число действий не должно превосходить 
O(общее число вершин и ребер в связной компоненте). 
Программа (листинг 5.45) в процессе работы будет закрашивать неко-
торые вершины графа. Незакрашенной частью графа будем называть то, что 
останется, если выбросить все закрашенные вершины и ведущие в них ребра. 
Функция SetEdge(v) закрашивает связную компоненту v в незакрашенном 
графе и ничего не делает, если вершина v уже закрашена.