c++ - 打印图的邻接表时出现重复数据

Question

我只是想实现一个基于邻接表的图，我无法弄清楚为什么第二个值在输出打印中出现两次:

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main() {
int k = 0;
int n = 0;
cin>>k;
while(k>0){
    cin>>n;
    //Declare Adjacency List
    vector<vector<pair<int, int>>> G;
    G.resize(n);
    //Add an edge u,v of weight w
    while(n>0){
        int u=0,v=0,w=0;
        cin>>u>>v>>w;
        G[u].push_back({v,w});
        n--;
    }
    int i=0;
    vector<vector<pair<int,int>>>::iterator it;
    vector<pair<int,int>>::iterator it1;
    for(it=G.begin() ; it < G.end(); it++,i++ ) {

        for (it1=G[i].begin();it1<G[i].end();it1++){
            for(pair<int,int> p: G[i]){
            cout <<"  "<<i<<"-> (w = "<<p.second<<") -> "<<p.first;
        }
        cout<<endl;
        }


    }
    k--;
 }


 return 0;
 }

输入:

1
5
1 2 2
2 3 1
2 4 4
4 5 3

输出:

0-> (w = 0) -> 0
1-> (w = 2) -> 2
2-> (w = 1) -> 3  2-> (w = 4) -> 4
2-> (w = 1) -> 3  2-> (w = 4) -> 4
4-> (w = 3) -> 5

我想学习实现。
任何新的实现也将受到欢迎，我想实现一个无向的加权图。

Answer 1

因为你的第二个for循环

for (it1=G[i].begin();it1<G[i].end();it1++)

你得到一个重复的输出。

我假设您使用 C++11。这是你的程序的一个稍微改进的版本。首先，我添加了读取顶点和边数的选项。

#include <iostream>
#include <utility>
#include <vector>

int main() {
    int k = 0;
    std::cin >> k;

    while (k > 0) {
        // read in number of nodes and edges
        auto n = 0;
        auto m = 0;
        std::cin >> n >> m;

        // Adjacency list
        std::vector<std::vector<std::pair<int, int>>> G;
        G.resize(n);

        // Add an edge (u,v) with weight w
        while (m > 0) {
            int u=0, v=0, w=0;
            std::cin >> u >> v >> w;
            G[u].emplace_back(v,w);
            --m;
        }

        // Print out adjacency list
        for (auto i = 0; i < G.size(); ++i) {
            for (const auto pair: G[i]) {
                std::cout << "  " << i << "-- (w = " << pair.second << ") --> " << pair.first;
            }
            std::cout << '\n';
        }
        --k;
     }
     return 0;
 }

用你的例子输入

1
5
4
1 2 2
2 3 1
2 4 4
4 5 3

表示一个有 5 个顶点和 4 个边的图，我们得到以下输出:

  1-- (w = 2) --> 2
  2-- (w = 1) --> 3  2-- (w = 4) --> 4

  4-- (w = 3) --> 5