Построение минимального остовного дерева

Есть построенный граф, в котором все вершины заданы экземплярами класса Vertex, а грани - Edge. Vertex имеют координаты float x и float y, а Edge точки Vertex a и Vertex b, длину double length. Попытка написать алгоритм построения минимального остовного дерева из графа Делоне по алгоритму Прима не увенчалась успехом. Получалось подобное:
Где белые ребра - ребра моего "древа", а серые в совокупности с белыми - исходный граф. Вот код моего алгоритма:
List tmpVertex = points; //вершины графа на входе List tmpEdges = DelanayTree; //ребра графа входе List selectedVertex = new List(); //вершины, по которым "прошелся" алгоритм List selectedEdges = new List(); // окончательный граф (список ребер) selectedVertex.Add(tmpVertex[0]); ///подготовка (чтобы не вызвать исключение) tmpVertex.RemoveAt(0); foreach (Edge e in tmpEdges) //расчет длинны для каждого ребра { e.length = Math.Sqrt((Math.Abs(e.b.x - e.a.x) * Math.Abs(e.b.x - e.a.x)) + (Math.Abs(e.b.y - e.a.y) * Math.Abs(e.b.y - e.a.y))); } while (tmpVertex.Count > 0) //алгоритм будет работать пока есть над чем работать { List conectedEdges = new List(); foreach (Vertex v in selectedVertex) //получение ребер, связывающих выбранные точки { List tmpConnEdges = v.getExtisEgdes(tmpEdges); foreach (Edge e in tmpConnEdges) conectedEdges.Add(e); } Edge minEdge = conectedEdges[0]; //чтобы не вызвать исключение foreach(Edge e in conectedEdges) //поиск ребра с меньшей длиной { if (e.length < minEdge.length) minEdge = e; } selectedEdges.Add(minEdge); //добавление его в финальный граф Vertex nonSelectedVertex; if (minEdge.a.vertexExtisInList(tmpVertex)) nonSelectedVertex = minEdge.a; //поиск второй (не выбранной) вершины этого ребра else nonSelectedVertex = minEdge.b; selectedVertex.Add(nonSelectedVertex); //добавление этой точки в финальный граф tmpEdges.Remove(minEdge); tmpVertex.Remove(nonSelectedVertex); } minimalTree = selectedEdges;
В чем может быть ошибка?

Ответ

Мой алгоритм так и не заработал (возможно из-за того что я его не правильно понял). Вчера нашел другую формулировку этого алгоритма:
Инициализируются списки с данными: ребра, не включенные в дерево, вершины, включенные в дерево, и вершины, не включенные в дерево. выбирается случайная начальная вершина, с которой начнется построение минимального остовного дерева. Цикл while будет продолжаться до тех пор, пока все вершины графа не будут включены в дерево
А в цикле уже: Производится поиск ребра с наименьшим весом, один конец которого – это вершина, входящая в дерево, а другой – нет/ Вершина, инцидентная найденному ребру, заносится в список использованных и удаляется из списка неиспользованных. Найденное ребро заносится в список ребер, составляющих дерево, и удаляется из списка неиспользованных ребер. Переписал код под свои цели:
List notUsedE = new List(DelaunayTree); //неиспользованные ребра есть копия ребер исходного графа List notUsedV = new List(points); //неиспользованные вершины есть копия вершин исходного графа List usedV = new List(); //список вершин по которым "проехался" алгоритм notUsedV[0].inUsedSide = true; //отмечаем что вершина используется usedV.Add(notUsedV[0]); //заносим её в список использованных notUsedV.Remove(usedV[0]); //удаляем из списка неспользованных while (notUsedV.Count>0) //пока есть вершины над которыми можно работать { List doubleSideE = new List(); //создание списка ребер у которых одна вершина используется, а другая нет foreach(Edge e in notUsedE) //для каждого неиспользованного ребра { if ((e.a.inUsedSide && !e.b.inUsedSide) || (e.b.inUsedSide && !e.a.inUsedSide)) doubleSideE.Add(e); //если у него одна вершина исп., а другая нет, то добавляем в список "двуликих" } Edge minE = doubleSideE[0]; //инициализация переменной для ребра, у которого минимальный вес foreach(Edge e in doubleSideE) //для каждого "двуликого" ребра { if (e.weight < minE.weight) minE = e; //если его вес меньше веса минимального, то делаем его минимальным } if (!minE.a.inUsedSide) //если вершина a ребра minE не используется { notUsedV.Remove(minE.a); //то удаляем вершину a из использованных minE.a.inUsedSide = true; //и делам её используемой usedV.Add(minE.a); } else { //а если b не используется notUsedV.Remove(minE.b); minE.b.inUsedSide = true; //то делаем её используемой usedV.Add(minE.b); } minimalTree.Add(minE); //добавляем минимальное ребро в конечный граф notUsedE.Remove(minE); //и удаляем его из неиспользованных, чтобы алгоритм не прошелся по нему еще раз }