0

私はクラスカルのアルゴリズムを C++ で構築しようとしており、その一部を書きました。コードは次のとおりです。

#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstdlib>
using namespace std;

class Edge {
    public:
        int to;
        int from;
        int weight;
        Edge();
        void print_edge();
};

Edge::Edge(void) {
}

void Edge::print_edge() {
    cout << "Edge to " << to << " from " << from << " of weight " << weight << endl;
}

int main() {
    int *vertex_sets;
    int vertex_size;
    int edge_size = 0;

    Edge* edges = new Edge[vertex_size * (vertex_size - 1) / 2];
    Edge* mst_edges = new Edge[vertex_size];

    cin >> vertex_size;
    vertex_sets = new int[vertex_size];

    for (int i = 0; i < vertex_size; i++) {
        int vertex_num;
        cin >> vertex_num;
        cout << "Assigning vertex set " << i << endl;
        vertex_sets[i] = i;
        int num_adjacent;
        cin >> num_adjacent;

        for (int j = 0; j < num_adjacent; j++) {
            edges[edge_size] = Edge();
            edges[edge_size].from = i;

            cin >> edges[edge_size].to >> edges[edge_size].weight;
            edge_size++;
        }
        cout << "Vertex " << i << " is in set " << vertex_sets[i] << endl;
        cout << "Vertex " << 0 << " is in set " << vertex_sets[0] << endl;
    }

    cout << endl;

    for (int i = 0; i < vertex_size; i++) {
        cout << "Vertex " << i << " is in set " << vertex_sets[i] << endl;
    }
}

しかし、何らかの理由で (int j = 0... ループ中に vertex_sets 配列が変更され、なぜこれが発生するのかわかりません。したがって、print ステートメントを使用します。

8
0
2
4 2
5 6
1
1
6 1
2
2
3 2
4 2
3
4
2 2
4 3
6 5
7 4
4
3
0 2
2 2
3 3
5
2
0 6
6 2
6
3
1 1
3 5
5 2
7
1
3 4

私はの出力を得る

Assigning vertex set 0
Vertex 0 is in set 0
Vertex 0 is in set 0
Assigning vertex set 1
Vertex 1 is in set 1
Vertex 0 is in set 0
Assigning vertex set 2
Vertex 2 is in set 2
Vertex 0 is in set 0
Assigning vertex set 3
Vertex 3 is in set 3
Vertex 0 is in set 3
Assigning vertex set 4
Vertex 4 is in set 4
Vertex 0 is in set 3
Assigning vertex set 5
Vertex 5 is in set 5
Vertex 0 is in set 3
Assigning vertex set 6
Vertex 6 is in set 6
Vertex 0 is in set 3
Assigning vertex set 7
Vertex 7 is in set 7
Vertex 0 is in set 3

Vertex 0 is in set 3
Vertex 1 is in set 2
Vertex 2 is in set 4
Vertex 3 is in set 3
Vertex 4 is in set 4
Vertex 5 is in set 5
Vertex 6 is in set 6
Vertex 7 is in set 7

これは、ループの 4 回目の反復中になんらかの理由で、インデックス 0 の vertex_sets の値が 0 から 3 に変化していることを意味します。その理由はわかりません。なぜこれが起こっているのか誰にもわかりますか？

4

1 に答える 1

1

初期化されていない変数を使用して新しい配列を割り当てると、うまくいきません。

Edge* edges = new Edge[vertex_size * (vertex_size - 1) / 2];
Edge* mst_edges = new Edge[vertex_size];

cin >> vertex_size;
于 2014-11-18T23:08:58.047 に答える