There is a constructed graph in which all vertices are given by instances of the Vertex class, and the faces are given by the Edge . Vertex have coordinates float x and float y , and Edge points Vertex a and Vertex b , the length double length . An attempt to write an algorithm for constructing a minimum spanning tree from the Delone graph using the Prima algorithm did not succeed. It turned out like this: Bad graph

Where the white edges are the edges of my "tree", and the gray ones in combination with the white ones are the original graph. Here is the code of my algorithm:

 List<Vertex> tmpVertex = points; //вершины графа на входе List<Edge> tmpEdges = DelanayTree; //ребра графа входе List<Vertex> selectedVertex = new List<Vertex>(); //вершины, по которым "прошелся" алгоритм List<Edge> selectedEdges = new List<Edge>(); // окончательный граф (список ребер) selectedVertex.Add(tmpVertex[0]); ///подготовка (чтобы не вызвать исключение) tmpVertex.RemoveAt(0); foreach (Edge e in tmpEdges) //расчет длинны для каждого ребра { e.length = Math.Sqrt((Math.Abs(ebx - eax) * Math.Abs(ebx - eax)) + (Math.Abs(eby - eay) * Math.Abs(eby - eay))); } while (tmpVertex.Count > 0) //алгоритм будет работать пока есть над чем работать { List<Edge> conectedEdges = new List<Edge>(); foreach (Vertex v in selectedVertex) //получение ребер, связывающих выбранные точки { List<Edge> 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;

What could be the error?

  • a.vertexExtisInList (e) checks for the existence of edge a in the list evgetExtisEgdes (tmpEdges) returns all edges connected to v in the list tmpEdges. - Xiadner
  • one
    Please comment your code and attach at least some description to it. - hedgehogues
  • And then maybe the question will be solved by itself;)) - Oleg GranRCM
  • @hedgehogues, supplied the code with comments. Is something cleared up? - Xiadner
  • So, and yet, specify what is the "Count Delone"? Do I understand correctly that the weight of each edge is the length, which is calculated here: Math.Sqrt((Math.Abs(ebx - eax) * Math.Abs(ebx - eax)) + (Math.Abs(eby - eay) * Math.Abs(eby - eay))) ? - hedgehogues

1 answer 1

My algorithm did not work (perhaps due to the fact that I did not understand it correctly). Yesterday I found another formulation of this algorithm:

  1. The lists with data are initialized: edges not included in the tree, vertices included in the tree, and vertices not included in the tree.
  2. a random initial vertex is selected from which the construction of the minimum spanning tree will begin.
  3. The while loop will continue until all vertices of the graph are included in the tree.


And in the cycle already:

  1. The search for the edge with the lowest weight is performed, one end of which is the vertex entering the tree and the other not /
  2. The vertex incident to the found edge is entered in the list of used and removed from the list of unused.
  3. The edge found is added to the list of edges that make up the tree, and is removed from the list of unused edges.

Rewrote the code to your goals:
  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 ((eainUsedSide && !ebinUsedSide) || (ebinUsedSide && !eainUsedSide)) 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); //и удаляем его из неиспользованных, чтобы алгоритм не прошелся по нему еще раз }