Was für eine Laufzeit und was für einen Speicheraufwand hat dieser Tiefensuche Algorithmus?
DFS(node, goal)
{
if (node == goal)
{
return node;
}
else
{
stack := expand (node)
while (stack is not empty)
{
node' := pop(stack);
DFS(node', goal);
}
}
}
Ich hätte gedachte O(|V| + |E|) für die Laufzeit und O(|V|) für den Speicher. Stimmt das denn auch, wegen der rekursiven Aufrufe überhaupt?
Informatik
