Programmiererforum

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

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) {}
};

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

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]Time: O(V + E)
Space: O(V)
[/code]
[b] iterativ: [/b]
[code]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) {}
};
[/code]
[b] Algorithmus (Vorbestellungsdfs) [/b]
[code]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;
}

[/code]