如何使用 Prim 算法从输入文件中找到具有给定坐标集的最小生成树？
How to find a Minimum Spanning Tree with a given set of coordinates from an input file using Prim's Algorithm?
好的，伙计们，我在互联网上的任何地方都没有看到这个，我已经尝试了好几天了。如何使用 Prim 算法从输入文件中找到一组坐标的 MST。有一些关于如何着手去做的事情，但是跟随它们并且是 C++ 的新手，它们并没有多大帮助。谁能告诉我如何解决这个问题的代码（最好）？
假设我在输入文件 "Something.txt" 中有一组坐标包含：
(N个nodes/vertices)
(x 坐标), (y 坐标)
等...
例如：
9
50 100
100 150
200 150
300 150
350 100
300 50
200 50
100 50
150 100
鉴于这些点已经被绘制出来，Prim 的算法将如何编写？我明白这很多，但作为 C++ 的新学习者，我在这一点上感到非常困惑。 （是的，我试过拼凑代码，我试过查看其他示例并扭曲它们以使其工作，除了查看它是如何完成的之外，我已经尝试了几乎所有的东西，所以我可以进一步理解我的东西继续失踪。）
提前致谢。
编辑：代码使用您传递给它的参数 .txt 输入文件通过 pygraphics 绘制点，然后进入 .dat 文件，然后通过预先创建的绘图文件发布：
class Point
{
public:
// Constructor.
Point()
{
x = 0; y = 0;
} // end constructor
Point(int a, int b, int id)
{
x = a; y = b; pointID = id;
} // end constructor
int getX() { return x; }
int getY() { return y; }
int getID() { return pointID; }
string data;
Point(string x)
{
data = x;
}
private:
int x = 0;
int y = 0;
int v;
int xVert;
int yVert;
int pointID = 0;
list<Point*> pointList;
list<Point*> neighbors;
//vector<Neighbor> myNeighborvector;
//locate point containg value x
Point * findPoint(string x)
{
for(Point * v : pointList)
{
if (v->data == x)
return v;
}
return NULL;
}
//add Neighbor going from x to y
void addDirectedNeighbor(string x, string y)
{
Point * xVert = findPoint(x);
Point * yVert = findPoint(y);
xVert->neighbors.push_back(yVert); //I would think that this should only add y to x's neighbors, but when I try to display I get x as one of y's neighbors
}
void addNeighbor(string x, string y)
{
addDirectedNeighbor(x, y);
addDirectedNeighbor(y, x);
}
}; // end class Point
//--------------------------------------------------------------------------
class Edge
{
public:
// Constructor.
Edge()
{
} // end constructor
Edge(Point ptA, Point ptB)
{
pointA = ptA;
pointB = ptB;
length = sqrt(pow(abs(pointA.getX() - pointB.getX() ), 2) + pow(abs(pointA.getY() - pointB.getY() ), 2) );
} // end constructor
Point getPtA() { return pointA; }
Point getPtB() { return pointB; }
double getLen() { return length; }
int getPtAID() { return pointA.getID(); }
int getPtBID() { return pointB.getID(); }
private:
Point pointA;
Point pointB;
double length;
}; // end class Edge
//--------------------------------------------------------------------------
/*class Neighbor
{
public:
// Constructor.
Neighbor()
{
length = sqrt(pow(abs(pointA.getX() - pointB.getX() ), 2) + pow(abs(pointA.getY() - pointB.getY() ), 2) );
} // end constructor
double getLen() { return length; }
private:
double length;
int pointID = 0;
};*/ // end class Neighbor
vector<Point> myPointvector; // vector will expand as needed
vector<Edge> MinSpanTree;
int main (int argc, char *argv[])
{
ifstream fin;
int coordPairs; // number of coordinate pairs in the file
int ptX, ptY;
int loopCounter;
int pointCounter = 0;
double MSTLength = 0.0;
// Check the number of arguments. Expected: filename of a file
if (argc != 2) // This check is often hardcoded
{ // If failure in parameters, offer advice for correction
cout << "\nThis program uses command-line argument.\n";
cout << "Usage: a.exe <filename>\n";
exit(0);
}
try // All lines within this block are part of the same exception handler
{
fin.open(argv[1]);
}
catch (exception& ex)
{
cout << ex.what(); // display standard explanation of the exception
exit(0); // exit the program
}
// Read from the file, one token at a time. If the type of token is known, it
// can be read into a corresponding variable type, such as
// in >> x; // Read the first item into an integer variable x.
// in >> str; // Read the next item into a string variable str.
// This line provides the graphic window setup.
cout << "800 600 white" << endl;
fin >> coordPairs;
cout << coordPairs << endl;
while (fin >> ptX)
{
// Do something with the element read from the file
// cout << ptX << endl;
fin >> ptY;
// cout << ptY << endl;
cout << "circle " << ptX << " " << ptY << " " << 20 << " seagreen" << endl;
Point dummyPoint(ptX, ptY, pointCounter++);
myPointvector.push_back(dummyPoint); // vector will expand as needed
cout << "Now myPointvector has size " << myPointvector.size() << endl;
} // end while
fin.close();
return 0;
}
这将需要几次迭代。
你有 Point 和向量。现在编写一个函数来计算两个点之间的距离，以及一个函数来读取数据文件并生成一个点向量。另外，写一个 class Neighbor 来保存 ID 号和距离，并给 Point 一个数据成员，它是 Neighbor.
的向量
然后给 Point 一些成员函数 1) 添加一个 Neighbor，2) 删除一个 Neighbor（由 ID 指定），以及 3) return Point 的最近 Neighbor 的副本。
完成后，尝试从向量中弹出一个点 A，然后迭代剩余的向量，计算与 A[=53] 的距离=] 依次指向对方，并构建 A 的 Neighbors 集合。
一切正常时，请对此答案发表评论。
编辑 1：
这是一个很有希望的开始，但是 代码的每次迭代都正确是至关重要的。 它不必做所有事情（或最初做任何事情），但它必须 1) 编译和 2) 运行 没有崩溃。此代码无法编译。在 Neighbor() 中，您引用了 pointA 和 pointB 而没有声明它们；它们应该是构造函数的参数。在Point中，你指的是vertex、findVertex、xvert和neighbors，其中none是定义甚至声明的。 （这个Edgeclass很有意思，但是不清楚你打算怎么用。）
支撑 Point 和 Neighbor classes（或放弃 Neighbor 支持 Edge）以便它们可以编译和 运行，即使他们没有取得多大成就。我会在几个小时后回来查看。
编辑 2：
最新版本的代码中有一些功能可能是不必要的，但我们会看到。
我们的想法是构建一棵树，那么如何使用这些 classes 呢？尝试编写一个小的测试函数来构造三个点（具有硬编码值）并将它们组装成一棵树。一旦成功，请考虑如何将 Prim 算法应用于这三个点。
好的，伙计们，我在互联网上的任何地方都没有看到这个，我已经尝试了好几天了。如何使用 Prim 算法从输入文件中找到一组坐标的 MST。有一些关于如何着手去做的事情，但是跟随它们并且是 C++ 的新手，它们并没有多大帮助。谁能告诉我如何解决这个问题的代码（最好）？
假设我在输入文件 "Something.txt" 中有一组坐标包含：
(N个nodes/vertices)
(x 坐标), (y 坐标)
等...
例如：
9
50 100
100 150
200 150
300 150
350 100
300 50
200 50
100 50
150 100
鉴于这些点已经被绘制出来，Prim 的算法将如何编写？我明白这很多，但作为 C++ 的新学习者，我在这一点上感到非常困惑。 （是的，我试过拼凑代码，我试过查看其他示例并扭曲它们以使其工作，除了查看它是如何完成的之外，我已经尝试了几乎所有的东西，所以我可以进一步理解我的东西继续失踪。）
提前致谢。
编辑：代码使用您传递给它的参数 .txt 输入文件通过 pygraphics 绘制点，然后进入 .dat 文件，然后通过预先创建的绘图文件发布：
class Point
{
public:
// Constructor.
Point()
{
x = 0; y = 0;
} // end constructor
Point(int a, int b, int id)
{
x = a; y = b; pointID = id;
} // end constructor
int getX() { return x; }
int getY() { return y; }
int getID() { return pointID; }
string data;
Point(string x)
{
data = x;
}
private:
int x = 0;
int y = 0;
int v;
int xVert;
int yVert;
int pointID = 0;
list<Point*> pointList;
list<Point*> neighbors;
//vector<Neighbor> myNeighborvector;
//locate point containg value x
Point * findPoint(string x)
{
for(Point * v : pointList)
{
if (v->data == x)
return v;
}
return NULL;
}
//add Neighbor going from x to y
void addDirectedNeighbor(string x, string y)
{
Point * xVert = findPoint(x);
Point * yVert = findPoint(y);
xVert->neighbors.push_back(yVert); //I would think that this should only add y to x's neighbors, but when I try to display I get x as one of y's neighbors
}
void addNeighbor(string x, string y)
{
addDirectedNeighbor(x, y);
addDirectedNeighbor(y, x);
}
}; // end class Point
//--------------------------------------------------------------------------
class Edge
{
public:
// Constructor.
Edge()
{
} // end constructor
Edge(Point ptA, Point ptB)
{
pointA = ptA;
pointB = ptB;
length = sqrt(pow(abs(pointA.getX() - pointB.getX() ), 2) + pow(abs(pointA.getY() - pointB.getY() ), 2) );
} // end constructor
Point getPtA() { return pointA; }
Point getPtB() { return pointB; }
double getLen() { return length; }
int getPtAID() { return pointA.getID(); }
int getPtBID() { return pointB.getID(); }
private:
Point pointA;
Point pointB;
double length;
}; // end class Edge
//--------------------------------------------------------------------------
/*class Neighbor
{
public:
// Constructor.
Neighbor()
{
length = sqrt(pow(abs(pointA.getX() - pointB.getX() ), 2) + pow(abs(pointA.getY() - pointB.getY() ), 2) );
} // end constructor
double getLen() { return length; }
private:
double length;
int pointID = 0;
};*/ // end class Neighbor
vector<Point> myPointvector; // vector will expand as needed
vector<Edge> MinSpanTree;
int main (int argc, char *argv[])
{
ifstream fin;
int coordPairs; // number of coordinate pairs in the file
int ptX, ptY;
int loopCounter;
int pointCounter = 0;
double MSTLength = 0.0;
// Check the number of arguments. Expected: filename of a file
if (argc != 2) // This check is often hardcoded
{ // If failure in parameters, offer advice for correction
cout << "\nThis program uses command-line argument.\n";
cout << "Usage: a.exe <filename>\n";
exit(0);
}
try // All lines within this block are part of the same exception handler
{
fin.open(argv[1]);
}
catch (exception& ex)
{
cout << ex.what(); // display standard explanation of the exception
exit(0); // exit the program
}
// Read from the file, one token at a time. If the type of token is known, it
// can be read into a corresponding variable type, such as
// in >> x; // Read the first item into an integer variable x.
// in >> str; // Read the next item into a string variable str.
// This line provides the graphic window setup.
cout << "800 600 white" << endl;
fin >> coordPairs;
cout << coordPairs << endl;
while (fin >> ptX)
{
// Do something with the element read from the file
// cout << ptX << endl;
fin >> ptY;
// cout << ptY << endl;
cout << "circle " << ptX << " " << ptY << " " << 20 << " seagreen" << endl;
Point dummyPoint(ptX, ptY, pointCounter++);
myPointvector.push_back(dummyPoint); // vector will expand as needed
cout << "Now myPointvector has size " << myPointvector.size() << endl;
} // end while
fin.close();
return 0;
}
这将需要几次迭代。
你有 Point 和向量。现在编写一个函数来计算两个点之间的距离，以及一个函数来读取数据文件并生成一个点向量。另外，写一个 class Neighbor 来保存 ID 号和距离，并给 Point 一个数据成员，它是 Neighbor.
然后给 Point 一些成员函数 1) 添加一个 Neighbor，2) 删除一个 Neighbor（由 ID 指定），以及 3) return Point 的最近 Neighbor 的副本。
完成后，尝试从向量中弹出一个点 A，然后迭代剩余的向量，计算与 A[=53] 的距离=] 依次指向对方，并构建 A 的 Neighbors 集合。
一切正常时，请对此答案发表评论。
编辑 1：
这是一个很有希望的开始，但是 代码的每次迭代都正确是至关重要的。 它不必做所有事情（或最初做任何事情），但它必须 1) 编译和 2) 运行 没有崩溃。此代码无法编译。在 Neighbor() 中，您引用了 pointA 和 pointB 而没有声明它们；它们应该是构造函数的参数。在Point中，你指的是vertex、findVertex、xvert和neighbors，其中none是定义甚至声明的。 （这个Edgeclass很有意思，但是不清楚你打算怎么用。）
支撑 Point 和 Neighbor classes（或放弃 Neighbor 支持 Edge）以便它们可以编译和 运行，即使他们没有取得多大成就。我会在几个小时后回来查看。
编辑 2：
最新版本的代码中有一些功能可能是不必要的，但我们会看到。
我们的想法是构建一棵树，那么如何使用这些 classes 呢？尝试编写一个小的测试函数来构造三个点（具有硬编码值）并将它们组装成一棵树。一旦成功，请考虑如何将 Prim 算法应用于这三个点。