[C/C++] [Suche] Tiefen - Breitensuch Algorithmus mit vorgegebenen punkten

Dieses Thema im Forum "Programmierung & Entwicklung" wurde erstellt von Ehmteakay, 14. Juni 2010 .

  1. 14. Juni 2010
    Zuletzt von einem Moderator bearbeitet: 14. April 2017
    [Suche] Tiefen - Breitensuch Algorithmus mit vorgegebenen punkten

    No File | xup.in

    Hab davon keinen blassen dunst

    und ein kollege von mir muss das programmieren und er hat auch keine ahnung :-D

    weil ich kann nur bissjn java udn php^^

    das muss hier doch irgendein absoluter crack innerhalb von 2 minuten machen können^^

    gaaanz viele bws gibst für den retter in der not

    grüße
    ehmteakay
     
  2. 14. Juni 2010
    AW: [Suche] Tiefen - Breitensuch Algorithmus mit vorgegebenen punkten

    Du brauchst zuerst einmal eine Datenstruktur, die den Graphen hält. Eine sehr einfache Implementierung könnte so aussehen:

    Code:
    class Node
    {
     private Node parent;
     private List<Node> children;
     
     public Node(Node parent)
     {
     this.parent = parent;
     this.children = new ArrayList<Node>();
     }
     
     public List<Node> getChildren()
     {
     return children;
     }
     
     public void addChild(Node node) {...}
    }
    
    Für die Breitensuche müssen immer erst alle Kinder eines Knotens durchsucht werden, bevor tiefer in den Graphen gegangen wird.

    Code:
    public boolean breadthFirstSearch(Node root, Node goal)
    {
     Queue<Node> agenda = new LinkedList<Node>();
     agenda.add(root);
     
     while(!agenda.isEmpty())
     {
     Node current = agenda.poll();
     if(goal.equals(current))
     {
     return true;
     } else
     {
     for(Node child : current.getChildren())
     {
     agenda.add(child);
     }
     }
     }
     
     return false;
    }
    
    Ich habe jetzt mal angenommen, dass es keine Schleifen im Graphen gibt, sonst müsstest du immer noch nachsehen, ob du ein Element schon einmal hattest.

    Die Tiefensuche ist eigentlich ähnlich, nur dass immer erst ein Zweig bis zum Ende verfolgt wird. Wenn du dafür auch noch Hilfe benötigst, schreib mir nochmal. Übrigens: Diese beiden Grafiken von Wikipedia verdeutlichen die Unterschiede sehr gut.
    Datei:Breadth-First-Search-Algorithm.gif – Wikipedia
    Datei epth-First-Search.gif – Wikipedia
     
  3. 14. Juni 2010
    AW: [Suche] Tiefen - Breitensuch Algorithmus mit vorgegebenen punkten

    das ging ja fix

    schonmal dickes danke werd ich direkt weiterleiten

    aber Leider Nicht in C++

    ich brauch das in c++
     
  4. 14. Juni 2010
    Zuletzt von einem Moderator bearbeitet: 14. April 2017
    AW: [Suche] Tiefen - Breitensuch Algorithmus mit vorgegebenen punkten

    Also ich muss echt sagen das Tiefen und Breitensuche extrem einfach ist

    Wir haben es in unserem Script schon als Pseudocode drin,.. ich lads dir mal eben hoch... edit folgt.

    Bild


    Bild

    Von Pseudo zu c++ oder Java Code solltet ihr eht hinbekommen, sonst seit ihr in dem Studium eh falsch ^^°
    Gerade bei den einfachen Algorithmen....
     
  5. Video Script

    Videos zum Themenbereich

    * gefundene Videos auf YouTube, anhand der Überschrift.