0

最小全域木問題のプリム法のプライオリティキューを使った方法で任意の入力をして結果を表示させたいが思うようにいきません。
addEdgeにcinを挿入して実行してみましたが出力が上手くいきません。
g.addEdge()のような形で入力の内容を代入できますか?解る方お願いします。

入力:

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

期待する出力結果: cin を用いて以下の出力にしたい。

0 - 1
1 - 2
1 - 3
5 - 4
3 - 5
3 - 6

現状の出力結果: 入力結果を受け付けておらず、出力結果が予定通りでない。

-1 - 0
-1 - 1
-1 - 2
-1 - 3
-1 - 4
-1 - 5
-1 - 6

ソースコード:

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const long long INF = 1e9;
typedef pair<int, int>P;
typedef vector<pair<int, int>>List;
int V, E;
int from, to, cost;
class Graph {
    int V;
    vector<pair<int, int>>*adj;
public:
    Graph(int V);
    void input();
    void addEdge(int from,int to,int cost);
    void prim();
};
Graph::Graph(int V)
{
    this->V = V;
    adj = new List[V];
}
void input() {
    cin >> V >> E;
}
void Graph::addEdge(int from, int to, int cost) {
  for (int i = 0; i < E; i++)
        cin >> from >> to >> cost;
    adj[from].push_back({ to,cost });
    adj[to].push_back({ from,cost });
}

void Graph::prim() {
    priority_queue<P, vector<P>, greater<P>>Q;
    int src = 0;
    vector<int>key(V,INF);
    vector<int>parent(V, -1);
    vector<bool>used(V, false);
    Q.push(make_pair(0, src));
    key[src] = 0;

    while (!Q.empty())
    {

        int from = Q.top().second;
        Q.pop();

        if (used[from] == true) {
            continue;
        }

        used[from] = true;

        List::iterator i;
        for (i = adj[from].begin(); i != adj[from].end(); i++)
        {
            int to = (*i).first;
            int cost = (*i).second;

            if (used[to] == false && key[to] > cost)
            {
                key[to] = cost;
                Q.push(make_pair(key[to], to));
                parent[to] = from;
            }
        }
    }

    for (int i = 0; i < V; i++) {
        cout << parent[i] <<" - " << i << endl;
    }
}
int main()
{
    input();
    Graph g(V);
    g.addEdge(from,to,cost);
    g.prim();
    return 0;
}
1
  • 3
    おそらく入力と出力の結果を見てざっくり問題点を洗い出すのではなくてまずはデバッグ方法を学んだほうが良いと思います。デバッガーを用いてプログラムが自分の想定通りに処理しているのか確認できれば問題点はおのずとわかってくると思います
    – keitaro_so
    2022年1月18日 1:26

1 件の回答 1

1

デバッグしてみたら出来ました。ありがとうございます。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const long long INF = 1e9;
typedef pair<int, int>P;
typedef vector<pair<int, int>>List;
int V, E;
int from, to, cost;
class Graph {
    int V;
    vector<pair<int, int>>*adj;
public:
    Graph(int V);
    void addEdge(int from,int to,int cost);
    void prim();
};
Graph::Graph(int V)
{
    this->V = V;
    adj = new List[V];
}

void Graph::addEdge(int from, int to, int cost) {
    adj[from].push_back({ to,cost });
    adj[to].push_back({ from,cost });
}

void Graph::prim() {
    priority_queue<P, vector<P>, greater<P>>Q;
    int cur = 0;
    vector<int>key(V,INF);
    vector<int>parent(V, -1);
    vector<bool>used(V, false);
    Q.push(make_pair(0, cur));
    key[cur] = 0;

    while (!Q.empty())
    {
        
        int from = Q.top().second;
        Q.pop();

        if (used[from] == true) {
            continue;
        }

        used[from] = true;

        List::iterator i;
        for (i = adj[from].begin(); i != adj[from].end(); i++)
        {
            int to = (*i).first;
            int cost = (*i).second;
            

            if (used[to] == false && key[to] > cost)
            {
                key[to] = cost;
                Q.push(make_pair(key[to], to));
                parent[to] = from;
            }
        }
    }

    for (int i = 1; i < V; i++) {
        cout << parent[i] <<" - " << i << endl;
    }
}
int main()
{
    cin >> V >> E;
    Graph g(V);
    for (int i = 0; i < E; i++) {
        cin >> from >> to >> cost;
        g.addEdge(from, to, cost);
    }
    g.prim();
    return 0;
}

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。