Datenduplizierung beim Drucken der Adjazenzliste eines Graphen

Question

ich gerade einen Adjazenzliste basierten grafische Darstellung umzusetzen versuche, ich bin zu klären, nicht in der Lage, warum zweiter Wert erscheint zweimal in der Ausgabe Druck:

#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; 
} 

Input:

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

Ausgang:

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 

ich möchte Implementierung lernen.
Jede neue Implementierung wird ebenfalls begrüßt werden, ich möchte eine ungerichtete, gewichtete Grafik implementieren.

Answer 1

Aufgrund Ihrer zweiten for-Schleife

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

Sie eine doppelte Ausgabe erhalten.

Ich nehme an, Sie verwenden C++ 11. Hier ist eine etwas verbesserte Version Ihres Programms. Zuallererst habe ich die Option hinzugefügt, um die Anzahl der Eckpunkte und Kanten einzulesen.

#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; 
} 

Mit Ihrem Beispiel-Eingang

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

, die ein Diagramm mit 5 Ecken und Kanten 4 bezeichnet erhalten wir die folgende Ausgabe:

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

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