suche hilfe für Graphentheorie mit BFS

[cLd]

hallo zusammen,
ich sitzte gerade in der schule und werde von meinem info lehrer gequält mit der aufgabenstellung eine BFS procedure zu schreiben mit deren hilfe ich den zusammenhang /bzw. den nichtzusammenhang eines Graphen überprüfen soll
ich habe a) keine ahung wie das gehen soll und
b) bin ich langasam am verzweifeln.
könnte mir bitte jemand sage wie das gehn soll?

als vorinformation haben wir folgendes bekommen:

Eingabe: Ein Graph G=(V,E)
Ausgabe: Eine Nummerierung bfsnum : V ==> {1,...|V|}

Delphi-Quellcode:

begin
   Forall v (element) V do bfsnum(v):=0;
   count:=1;
   queue:=0;
   while es ein v(element)V mit bfsnum(v)=0 exsitiert
     do begin
       wähle v(element)V mit bfsnum(v)=0;
       bfsnum(v):=count;
       inc(count);
       push(queue,v);
       while queue <>0
       do begin
   v:=pop(queue);
   forall w(element)N(v) mit bfsnum(w)=0
   do begin
          bfsnum(w):=count;
          inc(count);
          push(queue,w);
      end;
     end;
     end;
     end.

für eine antwort wäre ich dankbar

mfg cLd aka sören hinz

[edit=Sharky]Delphi-Tags gesetzt. Mfg, Sharky[/edit]

[Sharky]

Hai cLd,

ersteinmal: "Herzlich Willkommen in der Delphi-PRAXIS".

Sei doch bitte so gut und ändere den Titel deines Threads (das geht über den Edit-Butten rechts oben).
Um so aussagekräftiger der Titel um so eher bekommst Du Antworten ;-)

Danke :-D

[shmia]

Du musst einfach wie Mr. Spock rein logisch und Schritt für Schritt vorgehen.
An deinem Pseudocode ist zu sehen, dass du einen Stack oder eine Queue brauchst (wg Push & Pop).
Also programmierst du dir zuerst eine Stack, Queue und/oder Double-ended-Queue Klasse
oder du bedienst dich im Internet:
easy data structures library for delphi

[cLd]

den queue hab ich einzeln geproggt.... also ausgegliedert.
was ich nicht verstehe wie das programm hinterher laufen soll... bzw wie dieser quelltext zu interpretieren sein soll.

wenn mir jemand einen ansatz liefern könnte wäre ich dankbar

mfg cLd aka sören hinz

[QuickAndDirty]

Zitat:

Zitat von cLd (Beitrag 147304)

Eingabe: Ein Graph G=(V,E)
Ausgabe: Eine Nummerierung bfsnum : V ==> {1,...|V|}

Delphi-Quellcode:

   Forall v (element) V do bfsnum(v):=0;
   count:=1;
   queue:=0;
   while es ein v(element)V mit bfsnum(v)=0 exsitiert
     do begin
       wähle v(element)V mit bfsnum(v)=0;
       bfsnum(v):=count;
       inc(count);
       push(queue,v);
       while queue <>0
       do begin
   v:=pop(queue);
   forall w(element)N(v) mit bfsnum(w)=0
   do begin
          bfsnum(w):=count;
          inc(count);
          push(queue,w);
      end;
     end;
     end;
     end.

Danke...
ich versuch das mal zu übersetzen weil ich es gerade gut gebrauchen kann.

Delphi-Quellcode:

  //I will use containers instead of states, so "waiting" is the default
  WaitingContainer.LoadFromStream(graphStream);         //Forall v (element) V do bfsnum(v):=0;
  //count:=1;                                          //  count:=1;
  //queue:=0;                                          //  queue:=0;

  while WaitingContainer.count > 0 do                  //while es ein v(element)V mit bfsnum(v)=0 exsitiert
  begin
                                                       //wähle v(element)V mit bfsnum(v)=0;
    SelectedNode := WaitingContainer[0];

    //Change node state top "open"                     //bfsnum(v):=count;
    WaitingContainer.delete(0);
    OpenContainer.Add(SelectedNode);            //OpenContainer.count //inc(count);
 
    
    
    Queue.enqueue(SelectedNode);                       //push(queue,v);
    while Queue.count > 0 do                           //while queue <>0 do 
    begin
      SelectedNode := Queue.Dequeue;                   //v:=pop(queue);
      for SelectedSubNode in SelectedNode.Nodes do     //for w(element)N(v) mit bfsnum(w)=0 do 
      begin
        i := WaitingContainer.indexOf(SelectedSubNode);
        if i > 0 then
        Begin 
          WaitingContainer.delete(i);                  //bfsnum(w):=count;
          OpenContainer.Add(SelectedSubNode);          //OpenContainer.count //inc(count);
          Queue.Enqueue(SelectedSubNode);              //push(queue,w);
        end;
      end;
    end;
  end;

Weil es mir so noch nichts bringt, muss ich noch den WaitigContainer rausschmeißen und mit OpenContainer und CloseContainer arbeiten....

Weil ich ja unmöglich im voraus das gesammte Internet in den WaitingContainer laden kann...
Und mit nem OpenContainer und CloseContainer kann das dingen schon mal ne zeit lang arbeiten bevor dem Computer die Ressourcen ausgehen.