Breitensuche/Tiefensuche
Results 1 to 4 of 4
  1. #1

    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    534
    Thanks
    3
    Thanked 124 Times in 78 Posts

    Breitensuche/Tiefensuche

    Also stimmt das jetzt? Ich glaub schon.

    Breitensuche:
    Startknoten markieren und in Queue speichern;
    solange Queue nicht leer
    {
    Knoten p aus Queue holen und ausgeben;
    alle unmarkierten Nachbarn von p markieren und in Queue speichern;
    }

    Tiefensuche:
    Startknoten markieren und in Stack speichern;
    solange Stack nicht leer
    {
    Knoten p aus Stack holen und ausgeben;
    alle unmarkierten Nachbarn von p markieren und in Stack speichern;
    }

  2. #2
    #!/usr/bin/perl's Avatar
    Title
    Elite
    Join Date
    Jan 2002
    Posts
    291
    Thanks
    0
    Thanked 1 Time in 1 Post
    ja, bin mir ziemlich sicher; hier nochmal Pseudocode
    Code:
    BFS( G, s ) {   // G = Graph, s = Startknoten
            Graph g = neuer Graph( Adjazenzmatrix[][] );
            Queue q = neue Queue();
            q.nimmAuf( s );
            solange ( ! q.istLeer () ) {
                    Knoten k = q.entnimmElement();
                    k.markierKnoten();
                    Verarbeite k;   // wie oben
                    für alle w aus k.Nachbarschaft() {
                            q.nimmAuf( k );
                    }
            }
    }
    this is Unix land. In silent nights, you can hear Windows machines reboot...

  3. #3
    nix_is's Avatar
    Title
    Master
    Join Date
    Feb 2002
    Location
    Vienna
    Posts
    157
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Code:
    Verarbeite k; // wie oben
    was meinst du damit?
    Give a man a fish and he'll eat it for the day.
    Teach him how to fish and he will eat for the rest of his life...

  4. #4

    Title
    Elite
    Join Date
    Jan 2002
    Posts
    314
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @#!/usr/bin/perl:
    hmm... kanns nicht vorkommen, dass dein algorithmus elemente doppelt auf den stack legt?

    ich würd mich da eher an georgs pseudocode halten, den er am freitag an die tafel geschrieben hat.. und der auch sicher funktioniert..

    mfg, Chris
    hi, i'm a signature virus. copy me into your signature to help me spread.

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •