Iterative DFs mit optimierter Raumkomplexität ⇐ C++

[Anonymous]

Hintergrund
Ich kann anscheinend keine vorhandene Antwort finden, um diesen Zweifel an mir zu lösen. die Grafik. Das Diagramm wird durch Adjazenzlisten dargestellt.

Code: Select all

Time: O(V + E)
Space: O(V)

iterativ:

Code: Select all

Time: O(V + E)
Space: O(E)
< /code>
Der Grund für die Diskrepanz in der Raumkomplexität ist, dass wir in der iterativen Version alle Kanten des aktuellen Besuchsscheitungsscheitels in einem Stapel hinzufügen. Materialien. Der Schlüssel hier ist, Iteratoren zu verwenden, die eine endgültige Komplexität von: 
[b] Iterativ (Iteratoren) erreichen: [/b] 
Time: O(V + E)
Space: O(V)
< /code>
 Frage < /h1>
Ist meine Implementierung korrekt? (Es funktioniert für meine Beispiele): 
[b] Diagrammdarstellung [/b] 
struct Node {
int data;
list neighbours;
Node(int val) : data(val) {}
};

Algorithmus (Vorbestellungsdfs)

Code: Select all

void preDFSIter(vector& adjList) {
stack
::iterator, list::iterator>> nodes;
unordered_set visited;
for (Node* curStartNode : adjList) {
if (visited.count(curStartNode)) continue;
list startList = {curStartNode};
nodes.push({startList.begin(), startList.end()});
while (!nodes.empty()) {
auto&[curNodeIt, curNodeItEnd] = nodes.top();
if (curNodeIt != curNodeItEnd) {
Node* curNode = *curNodeIt;
++curNodeIt;
if (!visited.count(curNode)) {
visited.insert(curNode);
cout data) neighbours.begin(), curNode->neighbours.end()});
}
} else {
nodes.pop();
}
}
}
cout neighbours.begin(), curNode->neighbours.end()});
}
} else {
if (curParent) cout data) neighbours = {node3, node5};
node2->neighbours = {node5};
node3->neighbours = {node3, node6};
node4->neighbours = {node1, node3, node8};
node5->neighbours = {node0, node4, node7};
node6->neighbours = {node4};
node7->neighbours = {node4, node7};
node8->neighbours = {node6, node7};
vector  adjList = {node0, node1, node2, node3, node4, node5, node6, node7, node8};

preDFSIter(adjList);
postDFSIter(adjList);
return 0;
}