L
am besten eins nach dem anderen! also:
zuerst das überflüssige rausschmeissen. übrig bleibt:
void bfs ( Graph* g, int s, Queue* Q ) {
NeighbourPtr current = g->vlist[s];
do {
while ( current != NULL ) {
if ( g->color[current->vertex] == WHITE ) {
g->color[current->vertex] = GRAY;
enqueue ( Q, current->vertex);
}
current = current->next;
}
g->color[s] = BLACK;
current = g->vlist[kopf(Q)];
s = current->vertex;
} while ( ! empty (Q) );
}
mal angenommen, der graph enthält nur einen knoten, und ist ohne nachbarn. dann ist current == NULL folglich: kopf (Q) schlägt fehl, da nix in der queue ist. du musst vorher was reinstecken, damit du es auslesen kannst!
du kannst aber ganz am anfang den ersten knoten in die queue stecken, und in der schleife dann wieder rausholen. dann verschwindet das problem:
void bfs ( Graph* g, int s, Queue* Q ) {
NeighbourPtr current = NULL;
enqueue (Q, s);
do {
s = dequeue (Q);
current = g->vlist[s];
while ( current != NULL ) {
if ( g->color[current->vertex] == WHITE ) {
g->color[current->vertex] = GRAY;
enqueue ( Q, current->vertex);
}
current = current->next;
}
g->color[s] = BLACK;
} while ( ! empty (Q) );
}
welchen schleifentyp du nun benutzt, ist egal - ich bevorzuge while schleifen
void bfs ( Graph* g, int s, Queue* Q ) {
NeighbourPtr current = NULL;
enqueue (Q, s);
while (! empty (Q)) {
s = dequeue (Q);
current = g->vlist[s];
while ( current != NULL ) {
if ( g->color[current->vertex] == WHITE ) {
g->color[current->vertex] = GRAY;
enqueue ( Q, current->vertex);
}
current = current->next;
}
g->color[s] = BLACK;
}
}
wie werden wir nun das GRAY los? mal angenommen, du lässt es einfach weg. im ersten durchlauf werden alle nachbarknoten eingefügt, im zweiten alle nachbarknoten des ersten nachbarn des ersten knotens usw. unter umständen wird also ein knoten zweimal in die queue eingefügt.
V = {0, 1, 2}
E = {(0, 1), (0, 2), (1, 2) }
queue nach der ersten iteration: [1, 2]
queue nach der zweiten iteration: [2, 2]
die frage ist: stört das überhaupt? wenn nun in der dritten iteration der knoten 2 abgearbeitet wird, wird die farbe auf BLACK gesetzt - und das kannst du ja abfragen:
void bfs ( Graph* g, int s, Queue* Q ) {
NeighbourPtr current = NULL;
enqueue (Q, s);
while (! empty (Q)) {
s = dequeue (Q);
current = g->vlist[s];
if (g->color[s] != BLACK) {
/* knoten wurde noch nicht besucht */
/* hier kann irgendeine besuchermethode stehen */
while ( current != NULL ) {
enqueue ( Q, current->vertex);
current = current->next;
}
g->color[s] = BLACK;
}
}
}
in der vierten iteration passiert dann genau gar nix mehr, da g->color[s=2] == BLACK ist. das beispiel vollständig:
queue am anfang: [0]
erste iteration:
besuche knoten 0
queue nach while-schleife: [1, 2]
farbe von 0 ist BLACK
zweite iteration:
besuche knoten 1
queue nach while-schleife: [2, 2]
farbe von 1 ist BLACK
dritte iteration:
besuche knoten 2
queue nach while-schleife: [2]
farbe von 2 ist BLACK
vierte iteration:
knoten 2 hat farbe BLACK
ende
wobei farbe die markierung ist.
im buch Algorithmische Graphentheorie von Volker Turau sind AFAIR Codes drin.
einen blick ist es wert.
HTH
-- leuchtturm, mit einer heissen tasse glühwein
(und in der hoffnung, nicht zu viel mist zu erzählen)