Erreichbare Scheitelpunkte in gerichteten Graphen aus Vektor von Vektoren

Question

Ich arbeite an einer einfachen Programmieraufgabe für meine Studien und ich habe ein Problem festgestellt. Die Zuweisung hat eine vordefinierte Kopfzeile, die nicht geändert werden kann, also muss ich die gesetzten Strukturen verwenden, wodurch das Problem komplizierter wird, als es sein sollte.

Ich muss eine Funktion implementieren, die einen Vektor aller Vertices zurückgibt, die vom Startknoten aus erreichbar sind. Das wäre eine einfache Aufgabe, wenn ich dafür eine komplexere Struktur verwenden könnte, aber der ganze Graph wird als ein Vektor von Vektoren dargestellt, was mich davon abhält, wie ich es machen soll. Jede Hilfe würde sehr geschätzt werden.

Die Graphenstruktur bedeutet, dass zum Beispiel der Graph {{1,2,3}, {3}, {3}, {}} bedeutet, dass der Vertex 0 zu den Vertices 1,2,3 führt; Vertex 1 führt zu 3, Vertex 2 führt zu 3, Vertex 3 führt zu nichts.

graph.hpp

#include <vector> 
#include <algorithm> 

/* 
* Struct representing graph, that is, vertices and edges between the vertices. 
* Vertices are identified with indices, where 0 stands for 1st added vertex, 
* 1 stands for 2nd added vertex, 2 stands for 3rd added vertex, etc... 
* 
* The edges between vertices are directed. 
*/ 
struct graph { 
    std::vector<std::vector<int>> connections; 
}; 

// Other functions manipulating the graph here 

/* 
* Return vertices that are reachable from given vertex. 
* That is, the vertex itself, 
      all vertices connected to the given vertex, 
      all vertices connected to these vertices, 
      etc... 
* 
* Can only be called with existing vertex. 
*/ 
std::vector<int> reachable_vertices(const graph& g, int vertex); 

Ich habe eine Art naiven Brute-Force-Ansatz versucht, aber es funktioniert nicht.

graph.cpp

#include "graph.hpp" 

// Other functions manipulating the graph here 

std::vector<int> reachable_vertices(const graph& g, int vertex) { 
    if (g.connections.size() < vertex) { 
     return{}; 
    } 
    std::vector<int> reachables; 
    for (auto vert : g.connections[vertex]) { 
     if (vert > vertex) { 
      reachables = reachable_vertices(g, vert); 
     } 
    } 
    reachables.push_back(vertex); 
    std::sort(reachables.begin(), reachables.end()); 
    reachables.erase(std::unique(reachables.begin(), reachables.end()), reachables.end()); 
    return reachables; 
} 

Answer 1

Die Grenze beginnt mit einem einzelnen Knoten aus. Sie nehmen einen Knoten von der Grenze (, wenn Sie Zykluserkennung benötigen: und fügen Sie es zu einer Reihe von besuchten Knoten hinzu). Führen Sie eine Funktion auf dem Knoten aus. Nehmen Sie dann alle Knoten, die von diesem Knoten aus direkt erreichbar sind, und fügen Sie sie zur Grenze hinzu (, wenn Sie eine Zykluserkennung benötigen: es sei denn, der Knoten wurde zuvor besucht). Fahren Sie fort, bis keine weiteren Knoten übrig sind.

Abhängig davon, wie Sie Knoten zur Grenze "hinzufügen" und wie Sie einen Knoten von der Grenze nehmen, ist dies eine Beschreibung einer ganzen Klasse von Suchstrategien.

Eine Warteschlange (am Ende hinzufügen, von vorne) gibt Ihnen ein BFS, ein Stapel (Hinzufügen von oben, von oben) gibt Ihnen ein DFS.

"Führen Sie eine Funktion aus" wäre in Ihrem Fall "fügen Sie es der Gruppe der erreichbaren Knoten hinzu".