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

Листинг 5.43. Алгоритм Краскала 
public void Craskal() 
{ 
ClearVisit(); 
Lib.myStack = new MyStack(); 
int N = Nodes.Length; int m = 0; 
// 
формируем массив всех ребер 
for (int i = 0; i <= N - 1; i++) 
{ 
14 / 23

---

199 
int L = 0; 
if (Nodes[i].Edge != null) 
{ 
L = Nodes[i].Edge.Length; 
for (int j = 0; j <= L - 1; j++) 
if (!Find(i, Nodes[i].Edge[j].numNode)) 
{ 
Array.Resize(ref Edges, ++m); 
Edges[m - 1].n1 = i; 
Edges[m - 1].n2 =
Nodes[i].Edge[j].numNode; 
Edges[m - 1].A = Nodes[i].Edge[j].A; 
} 
} 
} 
TEdges h = new TEdges(); 
// 
Сортируем ребра графа по возрастанию весов 
for (int i = 0; i <= m - 2; i++) 
for (int j = m - 1; j >= i + 1; j--) 
if (Edges[j].A < Edges[j - 1].A) 
{ 
h = Edges[j]; Edges[j] = Edges[j - 1];
Edges[j - 1] = h; 
} 
int[] Link = new int[N]; 
// 
Вначале все ребра в разных компонентах связно-
сти 
for (int i = 0; i <= N - 1; i++) Link[i] = i; 
int numEdge = 0; // 
номер ребра 
int q = N - 1; // 
номер вершины 
while ((numEdge <= m - 1) && (q != 0)) 
15 / 23

---

200 
{ 
// 
если вершины в разных компонентах связности 
if (Link[Edges[numEdge].n1] !=
Link[Edges[numEdge].n2]) 
{ 
int t = Edges[numEdge].n2; 
Lib.myStack.Push(numEdge);
// 
поместить в стек номер ребра 
for (int j = 0; j <= N - 1; j++) 
if (Link[j] == t) 
Link[j] = Link[Edges[numEdge].n1];
// 
в один компонент связности 
q--; 
} 
numEdge++; 
} 
SetColorEdge(); // 
закраска ребер 
} 
Функция SetColorEdge() извлекает номера ребер из стека и пере-
крашивает ребра структуры Node[i] (листинг 5.44).