为什么在尝试将顶点添加到邻接列表时会遇到分段错误？

Question

我正在编写一个程序，在其中尝试使用邻接列表构建图形数据结构。图结构中的顶点具有 ID、x 和 y 坐标以及关联的邻接列表，其中包含有关子顶点是什么以及到达它们所需的权重的信息。

我尝试过使用 print 语句进行调试，例如 Graph 类中的 for 循环，但是我无法打印有关我已 push_back 放入名为 graph 的向量中的顶点的任何信息。此外，我知道坐标文件的所有内容都已读入，但每当我尝试从边缘文件创建邻接列表时，我都会收到分段错误（核心转储）。我尝试在 Visual Studio Code 上使用调试器，但它说程序能够运行，没有任何错误，尽管编译后出现分段错误。

我怎样才能停止出现这种分段错误？我也尝试过调整数组大小，但这也不起作用。我在尝试创建的 for 循环中遇到了分段错误。我不确定为什么顶点对象没有添加到我创建的向量中。有人可以指导我如何实际添加它们吗？

#ifndef VERTEX_H
#define VERTEX_H
#include <vector>

#define INF 1000000000

using namespace std;

class Vertex {
    public:
        int id;
        Vertex* parent;
        bool visited; // Flag to see if this vertex has been visited
        vector<pair<Vertex*, int>> children; // Connecting vertices to this vertex
        float g; // Path cost from source vertex to this vertex
        float h; // Heuristic ost from this node to goal node
        int x; // x-coordinate of vertex in graph space
        int y; // y-coordinate of vertex in graph space

        // Constructor
        Vertex(int id, int x, int y) {
            this->id = id;
            this->x = x;
            this->y = y;
            this->g = INF;
            this->h = INF;
            parent = NULL;
            visited = false;
        }

        // Add an edge to the vertex, populate the adjacency list
        void addEdge(Vertex* child, int weight) {
            children.push_back(make_pair(child, weight));
        }

        // Generic heuristic value calculation
        float f() {
            return g + h;
        }
};
#endif

#ifndef GRAPH_H
#define GRAPH_H
#include <iostream>
#include <fstream>
#include <cstdlib> 
#include <string>
#include <sstream>
#include <vector>
using std::ifstream;

#include "Vertex.h"

using namespace std;

class Graph {
    public:
        vector<Vertex*> graph;
        int vertexCount;
        string edges;
        string coordinates;

        // Constructor
        Graph(string edges, string coordinates, int vertexCount) {
            this->edges = edges;
            this->coordinates = coordinates;
            this->vertexCount = vertexCount;
            this->graph = createGraph(edges, coordinates, vertexCount);
        };

        vector<Vertex*> createGraph(string edges, string coordinates, int vertexCount) {
            vector<Vertex*> graph;
            // Read in coordinate information of vertices
            ifstream coordinateInput(coordinates);
            string line1, tempString1, tempString2, tempString3;
            int vertex; // Member ID of the vertex
            float x, y;
            while (getline(coordinateInput, line1)) {
                stringstream ss(line1);
                getline(ss, tempString1, ',');
                if (tempString1 == "--------------") break;
                vertex = stoi(tempString1);
                if (vertex >= graph.size()) {
                    graph.resize(vertex + 1); // Resize
                }
                getline(ss, tempString2, ',');
                x = stof(tempString2);
                getline(ss, tempString3, ',');
                y = stof(tempString3);
                graph.push_back(new Vertex(vertex, x, y));
            }
            coordinateInput.close();

            for (Vertex* v : graph) {
                std::cout << "here" << endl;
                std::cout << v->id << ' ' << v->x << v->y << endl;
            }
            std::cout << "Finished" << endl;

            // Read in edge information and add them to the graph
            ifstream edgeInput(edges);
            int src, dest, weight;
            string line2, tempString4, tempString5, tempString6;
            while (getline(edgeInput, line2)) {
                stringstream ss(line2);
                getline(ss, tempString4, ',');
                if (tempString4 == "--------------") break;
                src = stoi(tempString4);
                getline(ss, tempString5, ',');
                dest = stoi(tempString5);
                getline(ss, tempString6, ',');
                weight = stoi(tempString6);
                std::cout << graph[src]->id << endl;
                std::cout << src << ' ' << dest << ' ' << weight << endl;
                graph[src]->addEdge(graph[dest], weight);
            }
            edgeInput.close();
            return graph;
        }
};
#endif 

我试图读入的数据： 坐标：

1,42.66,73.78
2,33.76,84.40
3,30.30,97.75
4,42.32,71.09
5,42.90,78.85
6,51.00,114.00
7,35.21,80.83
8,41.84,87.68
9,41.48,81.67
10,32.80,96.79
11,39.73,104.97
12,41.59,93.62
13,31.79,106.42
14,48.87,-2.33
15,32.74,97.33
16,29.76,95.38
17,39.79,86.15
18,30.32,81.66
19,35.68,220.23
20,39.08,94.56
21,24.56,81.78
22,30.19,82.64
23,36.19,115.22
24,34.03,118.17
25,42.33,122.86
26,35.12,89.97
27,25.79,80.22
28,44.96,93.27
29,37.3,120.9
30,45.50,73.67
31,29.97,90.06
32,40.70,73.92
33,28.53,81.38
34,40.72,76.12
35,33.53,112.08
36,38.07,122.81
37,45.52,122.64
38,35.82,78.64
39,39.53,119.82
40,38.56,121.47
41,29.45,98.51
42,37.76,122.44
43,37.30,121.87
44,46.49,84.35
45,47.63,122.33
46,37.69,97.34
47,39.76,84.20
48,35.27,120.66
49,27.97,82.46
50,30.45,84.27
51,43.65,79.38
52,38.91,77.01
53,40.75,111.89
--------------

边：

1,30,226
1,2,1003
1,32,153
1,4,166
1,5,212
2,4,1075
2,26,456
2,50,308
3,16,186
3,13,577
3,15,190
3,41,79
3,31,511
4,5,455
4,32,215
4,30,161
4,28,1391
5,51,105
5,9,191
6,52,605
6,32,829
6,51,2116
7,18,432
7,38,165
7,8,987
8,28,511
8,46,361
9,34,476
9,47,214
9,51,292
9,10,1341
10,11,792
10,15,20
10,16,248
10,41,374
11,46,523
11,35,466
11,35,386
12,44,135
12,28,246
12,4,933
12,26,789
12,50,310
12,13,1132
13,41,580
13,35,320
13,35,328
14,34,3939
14,19,5313
15,44,314
15,17,413
16,15,101
16,31,321
17,18,1014
17,20,502
17,50,432
18,33,146
18,22,113
19,36,5131
19,48,5451
20,44,249
20,46,190
20,21,1092
20,22,1231
21,49,446
21,22,2341
21,29,892
22,27,902
22,49,169
22,50,104
22,23,421
23,24,275
23,53,486
23,39,439
24,43,124
24,48,182
24,29,328
25,37,275
25,36,365
26,44,413
27,33,235
27,49,282
27,21,159
28,32,463
28,25,1920
29,40,80
30,51,401
30,29,1080
31,50,388
31,32,1901
32,34,101
32,53,1311
32,24,1531
33,49,84
33,32,1343
34,14,3548
34,52,147
35,43,518
36,37,642
36,24,962
36,42,635
36,40,115
36,48,271
37,45,174
37,53,777
38,52,371
39,53,520
39,40,133
40,41,140
40,42,95
41,48,895
41,42,2093
42,43,50
42,48,232
43,48,168
44,32,882
44,51,436
45,52,115
46,53,335
47,17,165
47,46,795
47,9,212
48,51,2751
48,50,133
48,52,232
51,18,486
52,51,2095
49,50,275
49,51,1335
49,53,2328
50,11,795
50,52,2095
51,15,201
51,16,248
52,41,373
52,19,4869
53,52,2084
53,26,1243
53,51,2343
36,43,519
15,32,643
46,24,962
46,42,633
38,40,113
26,48,222
16,19,3431
27,40,123
35,43,1131
25,45,220
15,11,341
25,42,1232
--------------

Answer 1

这是一个带有嵌入数据的精简版本，演示了我如何解决这个问题。由于嵌入的数据集，我必须进行一些修改，但是您应该能够轻松地调整它以从文件中读取。溪流毕竟是蒸汽。

您应该注意 Vertex 类中的一项修改：

int x; // x-coordinate of vertex in graph space
int y; // y-coordinate of vertex in graph space

Vertex(int id, int x, int y) {

我将成员类型和构造函数参数更改为 float。数据被解析为浮点数，但在传递给构造函数时被截断。如果你打算这样做，那很好，但对我来说这似乎很奇怪。

您解析数据的方式并没有什么特别的问题，我只是对其进行了更改以显示替代方案。您应该知道，如果无法解析数据，stoi 和 stof 将抛出异常。您也不需要文件中的最后一行和 if (tempString4 == "----------------") break; 因为 std: :getline 将失败并在到达末尾时中断循环。

#include <iostream>
#include <sstream>
#include <string>
#include <vector>

#define INF 1000000000

using namespace std;

class Vertex {
public:
    int id;
    vector<pair<Vertex*, int>> children; // Connecting vertices to this vertex
    float x; // x-coordinate of vertex in graph space
    float y; // y-coordinate of vertex in graph space

    Vertex(int id, float x, float y) {
        this->id = id;
        this->x = x;
        this->y = y;
    }

    void addEdge(Vertex* child, int weight) {
        children.push_back(make_pair(child, weight));
    }
};

class Graph {
public:
    vector<Vertex*> graph;
    int vertexCount;

    Graph(std::istream& edges, std::istream& coordinates) {
        graph = createGraph(edges, coordinates);
        vertexCount = static_cast<int>(graph.size()) - 1;
    };

    ~Graph()
    {
        for (auto& v : graph)
        {
            delete v;
        }
    }

    vector<Vertex*> createGraph(std::istream& edges, std::istream& coordinates) {
        vector<Vertex*> ret(1);

        string line;
        while (getline(coordinates, line)) {
            stringstream ss(line);
            int vertex;
            float x;
            float y;
            char comma;
            if (ss >> vertex >> comma >> x >> comma >> y && ss.eof())
            {
                ret.push_back(new Vertex(vertex, x, y));

            }
            else
            {
                std::cout << "Data error parsing vertex from '" << line << "'\n";
            }
        }

        for (Vertex* v : ret) {
            if (v)
            {
                std::cout << v->id << ' ' << v->x << ", " << v->y << endl;
            }
        }

        while (getline(edges, line)) {
            stringstream ss(line);
            int src;
            int dest;
            int weight;
            char comma;
            if (ss >> src >> comma >> dest >> comma >> weight && ss.eof())
            {
                if (src < static_cast<int>(ret.size()) && ret[src])
                {
                    //hack to force dest into range 1, 10 of limited dataset
                    dest = 1 + dest % 10;

                    ret[src]->addEdge(ret[dest], weight);
                }
                else
                {
                    std::cout << "Data error: src " << src << " invalid\n";
                }
            }
            else
            {
                std::cout << "Data error parsing edge from '" << line << "'\n";
            }
        }
        return ret;
    }
};

int main()
{
    std::istringstream coordinates(
        "1, 42.66, 73.78\n"
        "2, 33.76, 84.40\n"
        "3, 30.30, 97.75\n"
        "4, 42.32, 71.09\n"
        "5, 42.90, 78.85\n"
        "6, 51.00, 114.00\n"
        "7, 35.21, 80.83\n"
        "8, 41.84, 87.68\n"
        "9, 41.48, 81.67\n"
        "10, 32.80, 96.79");

    std::istringstream edges(
        "1, 20, 226\n1, 2, 1003\n1, 32, 153\n1, 4, 166\n1, 5, 212\n"
        "2, 4, 1075\n2, 26, 456\n2, 50, 308\n"
        "3, 16, 186\n3, 13, 577\n3, 15, 190\n3, 41, 79\n3, 31, 511\n"
        "4, 5, 455\n4, 32, 215\n4, 30, 161\n4, 28, 1391\n"
        "5, 51, 105\n5, 9, 191\n"
        "6, 52, 605\n6, 32, 829\n6, 51, 2116\n7, 18, 432\n7, 38, 165\n7, 8, 987\n"
        "8, 28, 511\n8, 46, 361\n"
        "9, 34, 476\n9, 47, 214\n9, 51, 292\n9, 10, 1341\n"
        "10, 11, 792\n10, 15, 20\n10, 16, 248\n10, 41, 374"
    );

    Graph g(edges, coordinates);
    for (const auto& v : g.graph)
    {
        if (v)
        {
            std::cout << "\n";
            std::cout << v->id << ", " << v->x << ", " << v->y << "\n";
            for (const auto& e : v->children)
            {
                std::cout << "\t";
                std::cout << e.first->id << ", " << e.first->x << ", " << e.first->y << ", " << e.second << "\n";
            }
        }
    }
}

godbolt 示例