c++ - 如何使用 Prim 算法从输入文件中找到具有给定坐标集的最小生成树？

Question

好的伙计们，我在互联网上的任何地方都没有看到这个，我已经尝试了好几天了。如何使用 Prim 算法从输入文件中找到一组坐标的 MST。有一些关于如何着手去做的事情，但是跟随它们并且是 C++ 的新手，它们并没有多大帮助。谁能告诉我如何解决这个问题的代码(最好)？

假设我在输入文件“Something.txt”中有一组坐标，其中包含:
(N 个节点/顶点)
(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;
}

Answer 1

这将需要几次迭代。

您有点 和 vector 。现在编写一个函数来计算两个点之间的距离，以及一个函数来读取数据文件并生成一个点 vector 。此外，编写一个包含 ID 号和距离的 Neighbor 类，并为 Point 提供一个数据成员，该数据成员是 Neighbor 的 vector 。

然后给 Point 一些成员函数 1) 添加一个 Neighbor，2) 删除一个 Neighbor(由 ID 指定)，以及 3) 返回 Point 的最近 Neighbor 的拷贝。

完成后，尝试从 vector 中弹出一个点 A，然后迭代剩余的 vector ，依次计算从 A 到其他点的距离，并构建 A 的邻居集合。

当一切正常时，请对此答案发表评论。

编辑 1:
这是一个很有希望的开始，但确保代码的每次迭代都正确是至关重要的。它不必做所有事情(或最初做任何事情)，但它必须 1) 编译和 2)运行而不会崩溃。此代码无法编译。在 Neighbor() 中，您引用了 pointA 和 pointB 而没有声明它们；它们应该是构造函数的参数。在Point中，你引用了vertex、findVertex、xvert和neighbors，没有其中定义甚至声明。 (Edge 类很有趣，但不清楚您打算如何使用它。)

支持 Point 和 Neighbor 类(或放弃 Neighbor 以支持 Edge)，以便它们可以编译和运行，即使它们没有完成多少。我会在几个小时后回来查看。

编辑 2:
最新版本的代码中有一些功能可能是不必要的，但我们会看到。

我们的想法是构建一棵树，那么如何使用这些类呢？尝试编写一个小的测试函数来构造三个点(具有硬编码值)并将它们组装成一棵树。一旦成功，请考虑如何将 Prim 算法应用于这三个点。