effiziente Schleife einer Karte in einer Karte C++

Question

Ich versuche, eine effiziente Schleife über eine Kartendatenstruktur zu finden.

Die Map-Struktur bildet die folgenden Zahlen:

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

Die resultierende Karte sieht wie folgt aus:

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

Start : 4 
Result : 
1(1) 2(2) 5(1) 3(2) 6(2) 7(2) 8(2) 

Kann jemand vorschlagen, wie effizient Schleife (möglicherweise rekursive Methode), so dass ein gegebener Beginn von sagen 4, wäre das Ergebnis

1(1), 2(2), 5(1), 3(2), 6(2), 7(2), 8(2), 9(3), 10(4) 

So ist die Idee zu verwenden jeder innere Schlüssel, als äußerer Schlüssel, beginnend mit einem gegebenen äußeren Schlüssel. Mit äußeren 4 zum Beispiel sind die inneren Schlüssel 5 und 1. So verwenden Sie 5 und 1 als äußere Schlüssel, um innere Schlüssel zu erhalten (3 6 7 8) und (2), der Prozess sollte fortfahren, die inneren Schlüssel zu äußeren Schlüsseln zuzuordnen. Eine laufende Summe sollte pro "Sprung" gehalten werden. Es löst also wahrscheinlich eher ein rekursives Problem als eine Schleife.

Der Prozess sollte beendet werden, wenn entweder der Anfangspunkt erreicht wird, 4 im obigen Szenario, oder keine inneren Schlüssel mehr vorhanden sind, z. B. hat 10 keine Zuordnung.

Die Schleife ab Zeile 44, führt nur die oben genannten, bis zu zwei Ebenen, die nicht ausreichend ist.

#include <iostream> 
#include <map> 
#include <sstream> 

int digit_count(int number) { 
    int digits = 0; 
    if (number < 0) digits = 1; // remove this line if '-' counts as a digit 
    while (number) { 
     number /= 10; 
     digits++; 
    } 
    return digits; 
} 

int main() { 

    int v1, v2; 
    std::map< int, std::map< int, int> > m; 
    std::istringstream stm {"1 2 2 3 3 1 4 1 4 5 5 3 5 6 5 7 5 8 6 4 7 6 8 9 9 10"}; 

    while (stm >> v1 >> v2) { 
    m[v1]; 
    m[v1][v2] = 1; 
    } 

    std::cout << "Map layout " << "\n"; 
    std::string ss = ""; 
    int dc = digit_count(m.rbegin()->first); // equals max number 

    for (const auto & p : m) { 
    std::cout << p.first << ss.append(" ", (dc - digit_count(p.first))) << "| "; 
    for (const auto & val : p.second) 
     std::cout << val.first << " "; 
    ss = ""; 
    std::cout << "\n"; 
    } 

    int start {4}; 

    std::cout << "\nStart : " << start << "\n"; 
    std::cout << "Result : " << "\n"; 

    // efficient loop 
    for (const auto & e : m[start]) { 
    std::cout << e.first << "(" << e.second << ") "; 
    for (const auto & x : m[e.first]) 
     std::cout << x.first << "(" << (e.second + x.second) << ") "; 
    } 
    std::cout << "\n"; 
    return 0; 
} 

Jede Hilfe würde sehr geschätzt werden.

Answer 1

Nahm mich eine Weile, aber ich habe meine eigene Frage beantwortet und dachte, ich würde den Beitrag aktualisieren. Die einzige Möglichkeit, eine Lösung zu finden, war eine rekursive Funktion. Ich denke nicht, dass es möglich ist, mit Schleifen zu erreichen. Ich habe den Dijkstra-Algorithmus nicht ausgewählt, da keine Gewichtungen zu berücksichtigen sind und die Ergebnisse dieser rekursiven Funktion als Eingabe für einen rotschwarzen Baum dienen, wo jeder Knoten des rotschwarzen Baums eine Hash-Tabelle (unordered_map) enthält. Also das Ergebnis der Abfrage auf der kombinierten rotschwarzen Baum/Hash-Tabelle ist Log n, um den kürzesten Weg zu finden. Das Problem besteht darin, dass die Eingabe, wie Sie von unten sehen können, rekursiv und ineffizient ist.

#include <iostream> 
#include <map> 
#include <sstream> 
#include <set> 
#include <vector> 
#include <fstream> 

int digit_count(int number) { 
    int digits = 0; 
    if (number < 0) digits = 1; // remove this line if '-' counts as a digit 
    while (number) { 
     number /= 10; 
     digits++; 
    } 
    return digits; 
} 

struct vertex { 
    int point; 
    mutable bool visited{false}; 
    int id; 
}; 

void clear_visited(std::map<int, vertex>& verteces) { 
    for (const auto & e : verteces) { 
    e.second.visited = false; 
    } 
} 

void traverse_graph(std::map<int, vertex>& verteces, const vertex & v, std::map< vertex, std::map< vertex, int> >& graph, int& counter) { 
    if (verteces[v.id].visited) 
    return; 

    ++counter; 
    verteces[v.id].visited = true; 

    std::cout << v.point << "(" << counter << ") "; 
    for (const auto & e : graph[v]) { 
    traverse_graph(verteces, e.first, graph, counter); 
    } 
} 

void start_traverse_graph(std::map<int, vertex>& verteces, const vertex & v, std::map< vertex, std::map< vertex, int> >& graph) { 
    if (verteces[v.id].visited) 
    return; 

    verteces[v.id].visited = true; 

    for (const auto & e : graph[v]) { 
    int counter{0}; 
    clear_visited(verteces); 
    verteces[v.id].visited = true; 
    traverse_graph(verteces, e.first, graph, counter); 
    } 
} 

bool operator<(vertex a, vertex b) { return a.point < b.point; } 

int main (int argc, char *argv[]) { 

    vertex v1, v2; 
    std::map< vertex, std::map< vertex, int> > m; 
    std::istringstream stm {"1 2 2 3 3 1 4 1 4 5 5 3 5 6 5 7 5 8 6 4 7 6 8 9 9 10"}; 
    std::set<vertex> vertecesSet; 
    std::map<int, vertex> verteces; 

    while (stm >> v1.point >> v2.point) { 
    v1.id = v1.point; 
    v2.id = v2.point; 
    m[v1]; 
    m[v1][v2] = 1; 
    vertecesSet.insert({v1.point, false, v1.point}); 
    vertecesSet.insert({v2.point, false, v2.point}); 
    } 

    for(auto & el : vertecesSet) 
    verteces[el.id] = std::move(el); // dont need set objects anymore so move them 

    std::cout << "Map layout " << "\n"; 
    std::string ss = ""; 
    int dc = digit_count(m.rbegin()->first.point); // equals max number 

    for (const auto & p : m) { 
    std::cout << p.first.point << ss.append(" ", (dc - digit_count(p.first.point))) << "| "; 
    for (const auto & val : p.second) 
     std::cout << val.first.point << " "; 
    ss = ""; 
    std::cout << "\n"; 
    } 

    vertex start {5,false,5}; 

    std::cout << "\nStart : " << start.point << "\n"; 

    start_traverse_graph(verteces, start, m); 
    std::cout << "\n"; 
    return 0; 
}