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
    
    /*==================================================================*\
     *
     *  Graph als Adjazenzliste
     *
    \*==================================================================*/
    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"
    
    /*==================================================================*\
     *
     *  Graph als Adjazenzliste 
     *  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;
       printf("\nAdjacency-list");
       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 als Adjazenzlist */  
      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)


Log in to reply