# Graphen : BFS-Algorithmus mit Adjazenzliste

• Hallo, erstmal der Code

``````//graph.h
#include "feld_queue.h"
#define SIZE 20
#define INFINIT 1000
#define WHITE 0
#define GRAY 1
#define BLACK 2

/*==================================================================*\
*
*
\*==================================================================*/
typedef struct Neighbour* NeighbourPtr;

struct Neighbour {
int vertex;
NeighbourPtr next;
};

typedef struct {
NeighbourPtr vlist[SIZE];
int color[SIZE];
int dist[SIZE];
int predecessor[SIZE];
int size;
} Graph;

/*==================================================================*\
*
*  Funktions-Prototypen
*
\*==================================================================*/

NeighbourPtr new_neighbour( int v );
void initGraph ( Graph* g );
void print ( Graph* g );
void bfs ( Graph* g, int s, Queue* Q );

//graph.c
#include <stdio.h>
#include <stdlib.h>
#include "graph.h"

/*==================================================================*\
*
*  funktionen
*
\*==================================================================*/

NeighbourPtr new_neighbour( int v ) {
NeighbourPtr temp;
temp = (NeighbourPtr) malloc( sizeof *temp  );
temp->vertex = v;
temp->next = NULL;
return temp;
}

/*==================================================================*/

void initGraph ( Graph* g ){
int i, j, v;
int anzahl;
printf("Size of your graph? ", i );
scanf("%d", &(g->size) );
NeighbourPtr temp;
for( i=0; i<g->size; i++ ) {
g->vlist[i] = NULL;
g->predecessor[i] = NIL;
}
for( i=0; i<g->size; i++ ) {
printf("How many neighbours has vertex %d? ", i );
scanf("%d", &anzahl);
for( j=0; j<anzahl; j++ ) {
printf("Neighbour? ");
scanf("%d", &v );
temp = new_neighbour( v );
temp->next = g->vlist[i];
g->vlist[i] = temp;
}
}
for( i=0; i<g->size; i++ ) {
g->color[i]=WHITE;
g->dist[i]=INFINIT;
}
}

/*==================================================================*/

void printGraph ( Graph* g ){
int i;
NeighbourPtr temp;
for( i=0; i<g->size; i++ ) {
temp = g->vlist[i];
printf("\nvlist[%d]", i );
while ( temp != NULL ) {
printf( " %d ", temp->vertex );
temp = temp->next;
}
}
printf( "\n\ncolors: \n" );
for( i=0; i<g->size; i++ ) {
printf("color[%d]=", i );
switch ( g->color[i] ) {
case WHITE: printf("WHITE  ");   break;
case GRAY: printf("GRAY  ");   break;
case BLACK: printf("BLACK  ");   break;
}
}
printf( "\n\ndistance: \n" );
for( i=0; i<g->size; i++ ) {
printf("dist[%d]=", i );
if( g->dist[i]>= INFINIT )
printf("INFINIT  ");
else
printf("%d  ", g->dist[i]);
}
printf( "\n\npredecessors: \n" );
for( i=0; i<g->size; i++ ) {
printf("pred[%d]=%d  ", i, g->predecessor[i] );
}
printf( "\n\n" );
}

/*==================================================================*/

void bfs ( Graph* g, int s, Queue* Q ) {
NeighbourPtr current = g->vlist[s];
printf("Starte BFS mit s = %d\n", s);
g->dist[s] = -1;

do {
while ( current != NULL ) {
printf("current ist jetzt : %d\n", current->vertex);
if ( g->color[current->vertex] == WHITE ) {
g->color[current->vertex] = GRAY;
printf("color[%d] = GRAY\n", current->vertex);
g->predecessor[current->vertex] = s;
printf("pred[%d] = %d\n", current->vertex, s);
g->dist[current->vertex] = g->dist[g->predecessor[current->vertex]] + 1;
printf("dist[%d] = %d\n", current->vertex, g->dist[current->vertex]);
enqueue ( Q, current->vertex);
printf("%d wurde in Warteschlange eingefuegt.\n", current->vertex);
}
current = current->next;

}
g->color[s] = BLACK;
printf("color[%d] = BLACK\n", s);
printf("%d wurde aus der Warteschlange entfernt.\n", dequeue (Q));
current = g->vlist[kopf(Q)];
s = current->vertex;

} while ( ! empty (Q) );

}
/*==================================================================*/

//main.c
#include <stdio.h>
#include <stdlib.h>
#include "graph.h"

int main(int argc, char *argv[])
{
/* Hilfswarteschlange fÃ¼r den BFS-Algorithmus */
Queue q;
Queue* queue = &q;

Graph g;
Graph* graph = &g;
int first_vertex = 0;

initQueue( queue );
initGraph( graph );
printGraph( graph );

bfs( graph, first_vertex, queue );
printGraph( graph );

system("PAUSE");
return 0;
}
``````

Den Queue wollt ich jetzt nich auch noch posten, der funktioniert Das Programm war so vorgegeben, meine Aufgabe ist es nur, die bfs-funktion zu schreiben, und das da oben ist bisher dabei rausgekommen
Laufen tut das Programm schon, aber es tut natÃ¼rlich nicht das, was es soll Problem bei der Funktiion scheint

``````while ( current != NULL )
``````

zu sein. Jedesmal wenn current->vertex 0 ist, wird die while-Bedingung nicht erfÃ¼llt, was mich wundert. Current zeigt doch auf eine Datenstruktur, und da kann doch nicht die NULL-Konstante rauskommen, wenn der Wert von vlist[0]->vertex = 0 ist, oder ?!? Wie krieg ich das hin ?

• bfs == breitensuche? was macht die nochmal?
erklÃ¤r mal, ist bei mir schon ein gutes semester her
wozu brauchst du mehr als eine markierung?
was isn NIL?
warum ist die queue nicht funktionslokal?

-- leuchtturm

• oh, NIL ist im header vom queue definiert als -1.

Ich versuch so gut ich kann zu erklÃ¤ren was die Breitensuche soll:
Gegeben ist ein ungerichteter Graph, die Nachbarn werden in der init in die Adjazenzliste geschrieben. Dann wird der Graph von einem Eckpunkt aus traversiert ( in diesem Fall s ), wobei unbesuchte Knoten die Farbe WHITE bekommen, besuchte Knoten bekommen GRAY, und Knoten von denen alle Nachbarn bereits besucht worden sind, bekommen BLACK und gelten damit als vollstÃ¤ndig entdeckt. WÃ¤hrenddessen wird halt noch der kÃ¼rzeste Weg zum Startknoten in g->dist[] gespeichert, und der VorgÃ¤nger, von dem aus der Knoten entdeckt wurde, wird in g->predecessor[] gespeichert.

Und wieso soll der queue funktionslokal sein ?

Ich hoff mal ich hab das verstÃ¤ndlich ausgedrÃ¼ckt ist, weiÃŸ auch dass der Algorithmus logisch noch nicht ganz korrekt ist, aber mir geht es erstmal darum, warum nicht in die while-schleife gegangen wird, wenn current->vertex = 0 ist. Es wird doch nur current mit NULL verglichen, nicht die Zahl die darin gespeichert ist. current ist doch nur ein pointer auf den Typ Neighbour, der nur NULL sein sollte, wenn es keine Nachbarn gibt

• die queue gehÃ¶rt ganz eindeutig nur zum code in der funktion bfs ().

ist das wirklich der kÃ¼rzeste weg? antwort: nein. du speicherst die wege im aufspannenden baum des graphen, die nicht wirklich interessant sind.

-- leuchtturm, ohne zeit

• 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)