Programmiererforum

Code: Select all

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

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

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