BFS algorithm in C

Question

I am trying to find a BFS algorithm in C but I can't find one that actually works. I have a binary heap (tree implementation) and what I want to do is use the BFS algorithm in order to find the right place to insert a new element in my tree.

P.S I don't know the exact number of the elements that will be inserted (if that helps).

Answer 1

The procedure for inserting into an array-based binary heap is:

1. Add the new item to the end of the heap
2. Bubble it up

In an array implementation, adding to the end of the heap is trivial.

In a tree based implementation, you determine the path to the node and then traverse that path from the root down, sifting as you go. You have to know how many items are already in the heap, and that the tree is correctly balanced when you start.

Say, for example that there are 4 nodes in the heap:

    0
  1   2
3

The next node you add will go into position 4--the right child of node 1. So your job is to determine where position 4 is. More correctly, you have to determine which node is the parent of position 4.

If the root node is 0, then the parent of any node is node (i-1)/2. So the parent of node 4 is node 1, and the parent of node 1 is node 0.

You can write a recursive function that, given a node number, will traverse the tree to find the path to the parent. On the way out of the recursion, you actually end up sifting the node down the tree rather than bubbling it up, but the complexity is the same: O(log n).

Note that this doesn't do a breadth-first search. BFS would be a horribly inefficient way to do things.

Additional info

There's no special handling required for "even" or "odd" cases. It's all implicit in the tree structure. Consider this method, which will give you the path from the root to the insertion point in the tree:

(My example is in C#, simply because that's what I'm using these days. You should be able to convert to C with little trouble.)

private void HeapInsert(int node)
{
    if (node == 0)
        return;
    int parent = (node - 1)/2;
    HeapInsert(parent);
    Console.WriteLine("From node {0}, take {1} child to node {2}", parent, (node%2) == 0 ? "right" : "left", node);
}

I've simplified it in that it just shows the integer node numbers rather than doing the actual heap insertion. You can easily modify the code so that rather than outputting the path it, it gives you the actual nodes in the path from root to the insertion point.

Depending on your implementation, you can then traverse that path, insert the node in the proper place, and then bubble it up. Or, you can traverse the path from root to leaf, sifting the new item down in the process.

Answer 2

Insert into a binary heap need not use BFS.

Answer 3

What about generic implementation taken from program appearing in book:

"Programming Challenges: The Programming Contest Training Manual" by Steven Skiena and Miguel Revilla, Springer-Verlag, New York 2003.

#define TRUE    1
#define FALSE   0
#define MAXV        100     /* maximum number of vertices */
#define MAXDEGREE   50      /* maximum outdegree of a vertex */

typedef struct {
    int edges[MAXV+1][MAXDEGREE];   /* adjacency info */
    int degree[MAXV+1];     /* outdegree of each vertex */
    int nvertices;          /* number of vertices in the graph */
    int nedges;         /* number of edges in the graph */
} graph;
#define QUEUESIZE       1000

typedef struct {
        int q[QUEUESIZE+1];     /* body of queue */
        int first;                      /* position of first element */
        int last;                       /* position of last element */
        int count;                      /* number of queue elements */
} queue;

typedef int bool;


    bool processed[MAXV];   /* which vertices have been processed */
    bool discovered[MAXV];  /* which vertices have been found */
    int parent[MAXV];   /* discovery relation */

    bool finished = FALSE;  /* if true, cut off search immediately */

    initialize_search(graph *g)
    {
            int i;                          /* counter */

            for (i=1; i<=g->nvertices; i++) {
                    processed[i] = discovered[i] = FALSE;
                    parent[i] = -1;
            }
    }

    bfs(graph *g, int start)
    {
        queue q;            /* queue of vertices to visit */
        int v;              /* current vertex */
        int i;              /* counter */

        init_queue(&q);
        enqueue(&q,start);
        discovered[start] = TRUE;

        while (empty(&q) == FALSE) {
            v = dequeue(&q);
            process_vertex(v);
            processed[v] = TRUE;
            for (i=0; i<g->degree[v]; i++) 
                if (valid_edge(g->edges[v][i]) == TRUE) {
                if (discovered[g->edges[v][i]] == FALSE) {
                    enqueue(&q,g->edges[v][i]);
                    discovered[g->edges[v][i]] = TRUE;
                    parent[g->edges[v][i]] = v;
                }
                if (processed[g->edges[v][i]] == FALSE) 
                    process_edge(v,g->edges[v][i]);
                }
        }
    }


    /*
    bool valid_edge(edge e)
    {
        if (e.residual > 0) return (TRUE);
        else return(FALSE);
    }
    */


    dfs(graph *g, int v)
    {
        int i;              /* counter */
        int y;              /* successor vertex */

        if (finished) return;       /* allow for search termination */

        discovered[v] = TRUE;
        process_vertex(v);

        for (i=0; i<g->degree[v]; i++) {
            y = g->edges[v][i];
            if (valid_edge(g->edges[v][i]) == TRUE) {
                if (discovered[y] == FALSE) {
                    parent[y] = v;
                    dfs(g,y);
                } else 
                    if (processed[y] == FALSE)
                        process_edge(v,y);
            }
            if (finished) return;
        }

        processed[v] = TRUE;
    }


    find_path(int start, int end, int parents[])
    {
        if ((start == end) || (end == -1))
            printf("\n%d",start);
        else {
            find_path(start,parents[end],parents);
            printf(" %d",end);
        }
    }

/*The testing part*/
process_vertex(int v)
{
    printf("processed vertex %d\n",v);
}

process_edge(int x, int y)
{
        printf("processed edge (%d,%d)\n",x,y);
}


bool valid_edge(int e)
{
        return (TRUE);
}


int main()
{
    graph g;
    int i;

    read_graph(&g,FALSE);
    print_graph(&g);
    initialize_search(&g);
    bfs(&g,1);
    for (i=1; i<=g.nvertices; i++)
        printf(" %d",parent[i]);
    printf("\n");

    for (i=1; i<=g.nvertices; i++) 
        find_path(1,i,parent);
    printf("\n");
        return 0;
}

here is graph part:

initialize_graph(graph *g)
{
    int i;              /* counter */

    g -> nvertices = 0;
    g -> nedges = 0;

    for (i=1; i<=MAXV; i++) g->degree[i] = 0;
}

read_graph(graph *g, bool directed)
{
    int i;              /* counter */
    int m;              /* number of edges */
    int x, y;           /* vertices in edge (x,y) */

    initialize_graph(g);

    scanf("%d %d",&(g->nvertices),&m);

    for (i=1; i<=m; i++) {
        scanf("%d %d",&x,&y);
        insert_edge(g,x,y,directed);
    }
}

insert_edge(graph *g, int x, int y, bool directed)
{
    if (g->degree[x] > MAXDEGREE)
        printf("Warning: insertion(%d,%d) exceeds max degree\n",x,y);

    g->edges[x][g->degree[x]] = y;
    g->degree[x] ++;

    if (directed == FALSE)
        insert_edge(g,y,x,TRUE);
    else
        g->nedges ++;
}


delete_edge(graph *g, int x, int y, bool directed)
{
    int i;              /* counter */

    for (i=0; i<g->degree[x]; i++) 
        if (g->edges[x][i] == y) {
            g->degree[x] --;
            g->edges[x][i] = g->edges[x][g->degree[x]];

            if (directed == FALSE)
                delete_edge(g,y,x,TRUE);

            return;
        }

    printf("Warning: deletion(%d,%d) not found in g.\n",x,y);
}

print_graph(graph *g)
{
    int i,j;            /* counters */

    for (i=1; i<=g->nvertices; i++) {
        printf("%d: ",i);
        for (j=0; j<g->degree[i]; j++)
            printf(" %d",g->edges[i][j]);
        printf("\n");
    }
}

here is queue

init_queue(queue *q)
{
        q->first = 0;
        q->last = QUEUESIZE-1;
        q->count = 0;
}

enqueue(queue *q, int x)
{
        if (q->count >= QUEUESIZE)
        printf("Warning: queue overflow enqueue x=%d\n",x);
        else {
                q->last = (q->last+1) % QUEUESIZE;
                q->q[ q->last ] = x;    
                q->count = q->count + 1;
        }
}

int dequeue(queue *q)
{
        int x;

        if (q->count <= 0) printf("Warning: empty queue dequeue.\n");
        else {
                x = q->q[ q->first ];
                q->first = (q->first+1) % QUEUESIZE;
                q->count = q->count - 1;
        }

        return(x);
}

int empty(queue *q)
{
        if (q->count <= 0) return (TRUE);
        else return (FALSE);
}

print_queue(queue *q)
{
        int i,j;

        i=q->first; 

        while (i != q->last) {
                printf("%c ",q->q[i]);
                i = (i+1) % QUEUESIZE;
        }

        printf("%2d ",q->q[i]);
        printf("\n");
}

Answer 4

use this function

void bfs(int v)
{
    for(i=1;i<=n;i++)
    if(a[v][i] && !visited[i])
    q[++r]=i;
    if(f<=r)
    {
               visited[q[f]]=1;
               bfs(q[f++]);
    }
}

Recursion might solve your problem