2 replies to this topic

[code2learn]

The code for the use of BFS ie Breadth First Search in C++.

#include<stdio.h>
    #define maxx 101
    
    int Q[maxx];
    int first ,last;
    int node, edge;
    
    char linker[maxx][maxx];
    char var[maxx];
    int path[maxx];
    
    void Ini() {
    int i, j;
    for(i = 1; i<= node; i++) {
    for(j = 1; j<= node; j++) {
    linker[i][j] = 0;
    }
    path[i] = i;
    var[i] = 0;
    }
    }
    
    //Inserts element in the Q ie ENQUEUE
    void Insert(int n) {
    Q[last++] = n;
    last %= maxx;
    }

    int Pop() {
    int n = Q[first++];
    first %= maxx;
    return n;
    }
    
    int isEmpty() {
    if(first == last) return 0;
    return 1;
    }
    
    void Printpath(int n) {
    if(n == path[n]) {
    printf("%d",n);
    return;
    }
    Printpath(path[n]);
    printf(" %d",n);
    }

    int BFS(int s, int ter) {
    int u, v, i;
    Insert(s);
    var[s] = 1;
    while(isEmpty() == 1) {
    v = Pop();
    if(v == ter) {
    Printpath(v);
    return 1;
    }
    
    for(i = 1; i<= node; i++) {
    if(linker[v][i] == 1 && var[i] == 0)  {
    var[i] = 1;
    Insert(i);
    path[i] = v;
    }
    }
    }
    return -1;
    }
    
    void main() {
    int i, u, v;
    scanf("%d%d",&node,&edge);
    Ini();
    while(edge--) {
    scanf("%d%d",&u,&v);
    linker[u][v] = linker[v][u] = 1;
    }
    scanf("%d%d",&u,&v);
    BFS(u,v);
    printf("\n");
    }

Edited by WingedPanther, 01 January 2011 - 09:21 AM.
delete spammy links, add code tags

[WingedPanther]

0) CODE TAGS! Use them when posting. You'll need to reformat your text so it displays in a readable format.
0.5) I removed your spammy links, but please don't post poor tutorials in an effort to promote yourself, it will just backfire.
1) use const, not #define. It's type-safe, and part of good C++ style
2) This should really be wrapped inside a class.
3) Using arrays in C++ for this type of storage is less appropriate than a vector.
4) Use cin instead of scanf.
5) Don't use global variables. They should be declared in main(), and buy wrapping them in a class you can provide all the methods as part of the class with appropriate access to the variables. It would also make all of the code more useful in other applications.

[code2learn]

WingedPanther said:

0) CODE TAGS! Use them when posting. You'll need to reformat your text so it displays in a readable format.
0.5) I removed your spammy links, but please don't post poor tutorials in an effort to promote yourself, it will just backfire.
1) use const, not #define. It's type-safe, and part of good C++ style
2) This should really be wrapped inside a class.
3) Using arrays in C++ for this type of storage is less appropriate than a vector.
4) Use cin instead of scanf.
5) Don't use global variables. They should be declared in main(), and buy wrapping them in a class you can provide all the methods as part of the class with appropriate access to the variables. It would also make all of the code more useful in other applications.

my dear i knw wat i m writing and wat links i m giving.. Though i will keep in mind and put into use wat u wrote. THEIR IS NO PROMOTION thing going around we both are here because we love programming and we should work and help each other and everyone here.