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?

1 Antwort

AlexTbg

10.06.2023, 20:01

Die Laufzeit des Tiefensuche-Algorithmus (DFS) beträgt O(|V| + |E|), wobei |V| die Anzahl der Knoten und |E| die Anzahl der Kanten im Graphen ist. Der Speicheraufwand beträgt O(|V|), da der Algorithmus eine Markierung für jeden Knoten im Graphen speichern muss, um zu verfolgen, ob er bereits besucht wurde oder nicht.

Ähnliche Beiträge

Iterativen Code in Rekursiven umwandeln?

Hi zusammen,

Ich soll einen Code erfinden, der das tägliche Gehalt (angefangen bei 1 Cent) jeden gearbeiteten Tag verdoppelt und die Funktion soll nur einen Parameter erhalten.

Den iterative habe ich bereits:

def print_gehalt_iterativ(tage):

a = 1

while tage > 0:

a = a + a

tage = tage - 1

print(a)

Ich komme leider nicht zur rekursiven Variante....

def print_gehalt_rekursiv(tage):

a = 1

if tage == 0:

return a

if tage > 0:

a = a + a

return a

else:

return print_gehalt_rekursiv(tage - 1)

kann mir einer helfen bitte? :) Danke, Lucia

...zum Beitrag

Was macht throw in c++?

Grüßt euch ihr Lieben,

ich würde gerne wissen, was der Ausdruck

 throw

in einem Quellcod macht. Ich habe einen Quellcode indem

else{
throw(char*)  "Error: stack empty";
}

steht. Ich weiß abe nicht, was das bedeutet. Ich finde darüber auch nicht wirklich viel.

...zum Beitrag

Maze Solving Algorithmus?

Hi,

ich will mehrere Algorithmen implementieren, womit ich ein Maze lösen kann. Dabei gehts mir um Geschwindigkeit. Das gesamte Maze ist schon bekannt, also die "Maus" kann von jedem Punkt erfahren ob es eine Wand, oder ein Weg ist.

Derzeit habe ich den Wavepropagation, den Wallfollower und einen Kombi algorithmus implementiert. Der Kombi algorithmus entstand, nachdem ich Rekursion versucht hatte, bis ich gemerkt habe, dass das ja garnicht in C# geht xD

Dann hab ich per While loop einfach immer geguckt welche Richtungen sind möglich und dann halt random eine Richtung gewählt. Wenns deadend ist, halt wieder zurück, bis eine unbesichtigte Zelle kommt. Vllt habt ihr ja eine Idee wie der heißt.

Für mich neuling kling der Wavepropagation algorithmus derzeit am optimalsten, denn er hört auf, sobald das ziel gefunden ist.

Man könnte evtl. den noch Optimieren, indem man an an jeder Kreuzung ein Node setzt.

Der Djiktra klingt für mich als Neuling wie ähnlich des Wavepropagation Algorithmus, zumindest wenn man nicht die Map in nodes (bei jeder Kreuzung) plaziert.

Gibts einen viel schnelleren?

Die Map ist so um die 10k x 10k bis 15k x15k

Evtl auch mehr, wenn ich diese nicht painten würde, sondern nur als byte array lasse. Dauert aber so schon lang genug xD

Generiert wird dieses per Binary Tree derzeit. Dieser ist wenigstens Ultra schnell. Prims algorithmus ist mir zu langsam für diese Größenordnung.

...zum Beitrag

Array nach Wert prüfen rekrusiv (java)?

Hi sagen wir mal ich habe einen COde der so aussieht:

  public static int calculateBinomialCoefficient (int n, int k)
   {
      if (k == 1)
         return n;
      else if (n >= k && k == 0)
         return 1;
      else
       return (n * calculateBinomialCoefficient(n - 1, k - 1) / k);
 
   }
}

Nun hat mein Prof gemeint, dass die rekursion nicht linear ist und zu vielen gleichen Aufrufen mit gleichen Parameterkombis führt. EIne Möglichkeit damit das besser läuft ist es berechente Binomialkoeffizienten in einem zwei dimensionalen Array zu speichern und vor einem rekursiven Aufruf zu prüfen, ob die Lösung bereits 1x exisitert hat. EInen Array haben wir schon gegeben, mit der perfekten Länge.Dann habe ich mir das überlegt:

 public static int calculateBinomialCoefficient (int n, int k)
  {
   if (k == 1)
     return n;
   else if (n >= k && k == 0)
     return 1;
   else
for (int a=0; a<array.length;a++)
{
for (int b=0; b<array.length;b++)
{
if (array[a][b]==(n * calculateBinomialCoefficient(n - 1, k - 1) / k)
{
return array[a][b];
}else{
return (n * calculateBinomialCoefficient(n - 1, k - 1) / k);
if(array[a][b]==0){
array[a][b]==(n * calculateBinomialCoefficient(n - 1, k - 1) / k);
}
}
}
}
     
 
  }
}

(Ich hoffe kann man erkennen Tabs sind bisschen verrückt.)

Aber warum funktioniert das nun nicht? Habe doch alles beachtet oder?

...zum Beitrag

Türme von Hanoi rekursiv in Java?

Also, ich habe hier diesen Java-Code, welcher die Türme von Hanoi simuliert:

public class Hanoi {
  private static void bewege(char a, char b, char c, int n) {
    if (n == 1)
      System.out.println("Lege die oberste Scheibe von " + "Turm " + a + " auf Turm " + c + ".");
    else {
      bewege(a, c, b, n - 1);
      bewege(a, b, c, 1);
      bewege(b, a, c, n - 1);
    }
  }

  public static void main (String[] args) {
    bewege('a', 'b', 'c', 5);
  }
}

Ich verstehe alles, außer diesen Teil:

bewege(a, c, b, n - 1);
bewege(a, b, c, 1);
bewege(b, a, c, n - 1);

Was macht der Algorithmus da? Es wäre nett, wenn mir jemand auf die Sprünge helfen könnte.

Danke im Voraus.

...zum Beitrag

Speicherzugriffsfehler in Assembler?

Hey ich habe folgenden rekursiven Fibonacci Code geschrieben. Ich erhalte beim ausführen immer einen Speicherzugriffsfehler

Pastebin-Link: https://pastebin.com/qNWcyBa5

.intel_syntax noprefix

.section .data

n: .quad 10 # define the fibonacci number that should be calculated

.section .text

.global _start

_start:

# call Fibonacci function f(n)

push [n] # parameter: fibonacci number to calculate

call f # call function

add rsp, 8 # remove parameter from stack

# print calculated Fibonacci number on stdout

#call printnumber

# exit process with exit code 0

mov rax, 1

mov rbx, 0

int 0x80

# f: Calculates a Fibonacci number

# f(n) = {n, if n<=1; f(n-1)+f(n-2), else}.

# Parameter: Integer n >= 0, passed on stack

# Returns: Fibonacci number f(n), returned in rax

.type f, @function

push rbp # basepointer auf stack pushen

mov rbp, rsp # basepointer bekommt Wert des stackpointers

add rbp, 8 # 1.Parameter

mov rbx, [rbp] # rbx= 1.Paramter

cmp rbx, 0 # wenn n=0 passiert nichts, jmp zu end

je end

cmp rbx, 1 # wenn n=1 jmp zu baseone

je baseone

dec rbx # n-1

push [rbx] # push n-1

call f # call f(n-1)

dec rbx # n-2

push [rbx] # push n-2

call f # call f(n-2)

baseone: add rdi, 1 # rdi = rdi + 1

end: pop rbp # basepointer wieder vom Stack entfernen

ret

weiß auch nicht warum gf hier so viele Leerzeichen reinmacht. Naja hab das meiste kommentiert. Also wenn jemand einen Tipp hat wäre ich sehr dankbar.

Wer es kompilieren will.

as --gstabs -o Dateiname.o Dateiname.asm

ld -m elf-x86-64 -o Name Dateiname.o

./Name

Lg Tischtennisftw

...zum Beitrag

Sollte man Informatik nicht studieren, wenn man auf solch einem Niveau ist?

Ich kenne einigen, die so in Gruppen schreiben:

Ich brauch Nachhilfe in Datenstrukturen und Algorithmen

Tiefensuche ,

Fluss und Flussnetzwerk ,

Z-Algorithmus , Suffixbäume ,

Dynamisches Programmieren ,

Hashing ,

Rekursive Algorithmen ,

NP-Vollständigkeit (light) , Approximationsalgorithmen ,

Ich verstehe nicht alles gut.

Man kann nicht selbststaendig lernen und recherchieren.

Ingenieure entwickeln hochkomplexe Loesungen.

Deutschland ist Exportnation; aber wir exportieren nicht die Massenware, sondern High Tech, Spezialmaschinen, Premiumfahrzeuge und Gedöns. Dafür brauchen wir schlaue Köpfe, die uns einen möglichst einen technologischen Vorsprung erarbeiten; sonst kauft die Welt anderswo.

...zum Beitrag

Hilfe bei Java-Programm Binäre Suche (Rekursiv)?

Ich habe ein iteratives JavaProgrogramm zur Binären Suche erstellt, welches nun in eine rekursive Form gebracht werden soll.
Zudem sollen Testfälle vorbereitet werden, in denen min. 5 verschiedene Folgen F nach Schlüsseln gesucht werden kann. Eine Folge soll die Länge 1, eine weitere die Länge 2 haben, die restlichensollen länger als 10 Elemente sein. Nach dem Start des Programms soll die i-te Folge per Tastatureingabe ausgewählt und ein Suchschlüssel eingegeben werden. Anschließend soll das Programm die Indexposition ausgeben oder melden, dass der Schlüssel nichtgefunden wurde.

Hier das Programm in iterativer Form:

public class BinarySearch {

public static void main(String[] args) {
    new BinarySearch(); 
}

BinarySearch() {
    int[] f = {0, 1, 2, 4, 5, 8, 9, 12, 13, 18};
    int position = binarySearch(f, 5);
    System.out.println("Schlüsseln 5an Postition: "+ position);
}
int NO_KEY = -1;

int binarySearch(int[] f, int key){
    int i1 = 0, i2 = f.length - 1;
    while (i1 <= i2){
        int m = (i1 + i2) / 2;
        if ( key == f [m]) {
            return m;
        }else if (key < f[m]){
            i2= m - 1;
        }else {
            i1= m + 1;
        }
    }
    return NO_KEY;

} }

...zum Beitrag

GGT porgrammiern?

kann mir jmd erklären, was ich anders machen soll oder ob ich was vergessen hab, damit das Programm läuft? (es geht um den größten gemeinsamen Teiler)

Danke

...zum Beitrag

C Programmierung: Scanf-befehl funktioniert nicht nach If- Anweisung

Guten Tag habe da ein Problem bei einem Programm an dem ich gerade arbeite: Ich soll mit Kommandos (list, pop, push und exit) einen Stack mit zeichen füllen, das letzte zeichen löschen, eine Liste des Stacks ausgeben oder das Programm verlassen. Momentan funktioniert nur das verleassen des Programms, da der Scanf-befehl hinter der if-Anweisung nach dem Kompilieren nicht ausgeführt wird, um ein Zeichen einzulesen. (fgetc() hat auch nicht funktioniert).

Vielleicht kann mir ja jemand erklären woran es liegt.

Quelltext:

include include include define NSTACK 15

int main(){ //Anfang Main

//Variablendeklaration char eingabe[6]; char stack[NSTACK]; char item; char z; //zwischenspeicher für zeichen int sp=0; //Ende Variablendeklaration

printf("\nStack auffüllen (bis 15 Zeichen)\n");
printf("Liste der Befehle:\n\n");
printf("list = Liste des Stacks anzeigen\n");
printf("push = Zeichen auf den Stack legen\n");
printf("pop = Zeichen vom Stapel nehmen\n");
printf("exit = Programm beenden\n\n");

 while(eingabe){    //Eingabeschleife

  printf("\nBitte geben Sie ihren Befehl ein: ");
  scanf("%s", &eingabe);
  printf("eingegebener Befehl: %s\n", eingabe);

  
  if (strcmp(eingabe,"exit") == 0){             //exit
printf("\n!!Das Programm wird beendet!!\n");
exit(1);
  } //ende exit
  
  else if (strcmp(eingabe,"push") == 0){            //push
scanf("%c", &z);
printf("Zeichen wird auf Stack gelegt\n");
  } //ende push
  else if (strcmp(eingabe,"pop") == 0){         //pop
printf("Das obertste Zeichen wird entfernt\n");
  } //ende pop
  else if (strcmp(eingabe,"list") == 0){            //liste ausgeben
printf("Die Liste des Stacks wird ausgegeben\n");
printf("%s\n", &stack);
  } //ende list
  
 }  //Ende eingabeschleife
 


printf("\ntest");

printf("\n\n"); return 0; } //Ende Main

...zum Beitrag

Binäre Suche: Iterativ vs rekursiv?

Ich habe beides in Java implementiert, verstehe aber nicht, warum die rekursive Variante mehr als doppelt so schnell ist. Müsste es normalerweise nicht anders herum sein? Oder habe ich bei der iterativen Variante irgendetwas suboptimal gelöst?

public static int binarySearchIterative(int[] a, int z) {
  int left = 0;
  int right = a.length - 1;

  while (left <= right) {
    int midpoint = (int)((left + right) / 2);

    if (z == a[midpoint]) {
      return midpoint;
    }

    if (z < a[midpoint]) {
      right = midpoint - 1;
    }
    else {
      left = midpoint + 1;
    }
  }

  return -1;
}

public static int binarySearchRecursive(int[] a, int z, int left, int right) {
  int midpoint = (int)((left + right) / 2);

  if (right < left) {
    return -1;
  }

  if (z == a[midpoint]) {
    return midpoint;
  }

  if (z < a[midpoint]) {
    return binarySearchRecursive(a, z, left, midpoint - 1);
  }
  else {
    return binarySearchRecursive(a, z, midpoint + 1, right);
  }
}

...zum Beitrag

Ternärer Baum als Pseudocode?

In dieser Aufgabe betrachten wir gewurzelte ternäre Bäume. Jeder Knoten v kann also ein linkes Kind v.L, ein mittleres Kind v.M und/oder ein rechtes Kind v.R haben. Wir möchten nun herausfinden, wie viele Knoten im Baum sind.Gebe jeweils einen rekursiven Algorithmus in Pseudocode an, der durch den Aufruf count(v0) die Anzahl n der Knoten im Baum mit Wurzel v0 bestimmt. Begründe die Korrektheit der Algorithmen.

a) Gehe für den Entwurf deines Algorithmus zuerst davon aus, dass der Baum vollständig ist, also jeder Knoten entweder genau drei Kinder oder gar kein Kind besitzt und für jedes Blatt der Weg von der Wurzel die gleiche Länge hat. Stelle eine Rekursionsgleichung für die Laufzeit auf und löse diese mithilfe des Master-Theorems. Der Algorithmus soll eine Laufzeit von o(n)haben.

b) Wie verändern sich Algorithmus und Laufzeit, wenn Sie allgemeine ternäre Bäume betrachten?

________________________________________________________

Es geht um Pseudo-Code. In der Vorlesung benutzen wir C (obwohl wir C eigentlich erst nächstes Semester lernen), also wir lassen immer Klammern auf und schließen diese erst in der nächsten oder ubernächsten Zeile und erhöhen Variablen durch i++.

Ich habe mir überlegt, weil das ganze ein ternärer Baum sein soll und die Länge gezählt wird:

var counter = 0
    for b = 0; b ≤ n; b++) {
        for (l = 1, l++) {
             l = l + 1
}
        for (m = m, m++) {
             m = m + 1
}
        for (r = r, r++) {
             r = r + 1
}
        counter = counter + 1
}

wobei b die, ich nenn's jetzt einfach mal "Oberschleife" ,für den Baum an sich ist und l, m und r jeweils Unterschleifen, wobei l = links, m = mitte, r = rechts. Glaube aber, dass ich's mir hiermit zu einfach mache.

Zudem muss das Ganze ja noch als rekursive Funktion geschrieben werden, also der Form T (n) = a * T (n/b) + f(n), wobei b in diesem Fall = 3 ist, weil es ja ein ternärer Baum ist. Aber was ist a? Man könnte ja theoretisch unendlich viele Kinderknoten haben? Oder versteh ich da was falsch?

...zum Beitrag

Beliebiges Element in einer Liste löschen (Java)?

Die Aufgabe lautet, dass wir ein beliebiges Element in einer Liste löschen können. Ich habe auch schon einen Ansatz. Doch ich komme jetzt leider nicht mehr weiter. Ich kann bisher nur das erste und letzte Element löschen. Doch noch keines in der Liste. Also das Dummy läuft durch die Queue bis zum vorletzten Element. Wenn nun der gesuchte Content mit dummy.getNext() übereinstimmt, dann soll gelöscht werden. Ich habe es auch schon so versucht zu programmieren aber irgendwie krieg ich es nicht ganz so hin, wie ich es mir vorgestellt habe.

Ist etwas in meiner Logik falsch oder etwas wie ich es programmiert habe? Kann mir wer helfen das weiter so zu programmieren? Danke

public void delete(String s) {
        Node dummy = first;
        Node last = getLast();
        Node nach = getNext();
        if(s.equals(first.getContent())) {
        delete();
        }
        else if(getLast().getContent().equals(s)) {
          delete();
        }
        
        while(!(dummy.getNext().getContent().equals(s))) {
            delete();
            dummy=dummy.getNext();
        }
        dummy.setNext(dummy.getNext().getNext());
    }

...zum Beitrag

Wie kann ich den String als JSON-Object konvertieren?

Hallo alle miteinander.

Ich benötige Hilfe weil ich eine eigene Programmiersprache mache.

Die Variablen speichere ich in einem JSON-String:

let variablen = 
    {
        dingsbumbs:"Das ist eine Variable"
    }
;

Das ist der Code mit dem lesen der Variablen:

// ...
// Art ist definiert und richtig
if(art == "sage"){
            let parameter = "";
            while(command.charAt(zeichenzahl) != "("){
                zeichenzahl++;
            }
            zeichenzahl++;
            if(command.charAt(zeichenzahl) == "`"){
                zeichenzahl++;
                while(command.charAt(zeichenzahl) != "`"){
                    parameter = parameter+command.charAt(zeichenzahl);
                    zeichenzahl++;
                  }
              }else{
                  let variablenname = "";
                  let variablendecoded = // JSON.parse(variablen) oder JSON.stringify(variablen) ?;
  
                   // Hier wird nur der Variablenname erkannt. (Funktioniert ebenfalls)
                   while(command.charAt(zeichenzahl) != ")"){
                      variablenname = variablenname+command.charAt(zeichenzahl);
                      zeichenzahl++;
                  }
                  // Aber der Befehl ist ein "undfined"
                  parameter = variablendecoded.variablenname;
              }
              console.log(parameter);
            zeichenzahl = command.length;
            commandfunc = true;
        }/*Hier ist kein Fehler*/else if(art == "C["){
            while(command.charAt(zeichenzahl) != "]"){
                zeichenzahl++;
            }
            commandfunc = true;
        }

Kann mir jemand helfen das ich aus der Variable(variablendecoded) das objekt dessen Name Variable(variablenname) hat, lesen kann.

Eine Antwort wäre hilfreich.

Danke im voraus:);).

PS.: Ich verwende Node JS(18.4.0)

...zum Beitrag

Was möchtest Du wissen?

Deinen Beitrag erstellen