C语言中的BFS算法

Question

C语言中的BFS算法

calgorithmbinary-treebreadth-first-search

3

我正在尝试寻找一个可用的C语言BFS（广度优先搜索）算法，但我找不到一个真正有效的。我有一个二叉堆（树实现），我想使用BFS算法来找到在我的树中插入新元素的正确位置。

注：我不知道将要插入的元素数量的确切值（如果这有帮助）。

- matrix

这里是伪代码：http://en.wikipedia.org/wiki/Breadth-first_search。 - Oliver Charlesworth

4个回答

2

那么从书中出现的程序中采用的通用实现怎么样：

《编程挑战：编程竞赛训练手册》作者Steven Skiena和Miguel Revilla，Springer-Verlag，纽约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;
}

这里是图表部分：

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");
    }
}

这是一个队列。

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");
}

- edgarmtze

2

向二叉堆中插入数据并不需要使用广度优先搜索。

- Zhou Tai

1

学习二叉堆和/或BFS，“算法导论”是一个不错的入门起点。 - Zhou Tai

我知道如何将元素插入到使用数组实现的二叉堆中，但对于树的实现（结构体），我认为需要使用BFS。 - matrix

如果您使用BFS插入元素，将在插入元素时获得O(n)的时间复杂度。我建议您使用指针在基于数组的堆中模拟操作，这样插入时将获得O(logn)的时间复杂度。这个想法是使用指针和倒置堆调整操作。 - Zhou Tai

1

使用此函数。

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++]);
    }
}

递归可能解决您的问题

- Rohit

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jim Mischel · Accepted Answer

将新项插入基于数组的二叉堆的步骤如下：

将新项添加到堆的末尾
上移该项

在使用数组实现时，向堆的末尾添加元素非常简单。

在使用基于树的实现时，您需要确定到达节点的路径，然后从根向下遍历该路径，并进行筛选。您必须知道堆中已有多少项，并且在开始时树已经正确平衡。

例如，假设堆中有4个节点：

    0
  1   2
3

您要添加的下一个节点将进入位置4——即节点1的右子节点。因此，您的任务是确定位置4在哪里。更准确地说，您必须确定位置4的父节点是哪个节点。

如果根节点为0，则任何节点的父节点都是节点(i-1)/2。因此，节点4的父节点是节点1，节点1的父节点是节点0。

您可以编写一个递归函数，给定一个节点编号，将遍历树以找到到达父节点的路径。在递归退出时，实际上会将节点向下筛选而不是向上冒泡，但复杂度相同：O(log n)。

请注意，这并不执行广度优先搜索。BFS将是一种可怕的低效方法。

额外信息

“偶数”或“奇数”情况不需要特殊处理。它们都隐含在树结构中。考虑以下方法，它将为您提供从根到树中插入点的路径：

（我的示例使用C#，只是因为这是我现在正在使用的语言。您应该能够轻松转换为C。）

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);
}

我已将其简化，仅显示整数节点编号而不进行实际的堆插入。您可以轻松修改代码，使其在输出路径而非节点时给出从根到插入点的实际节点。

根据您的实现，您可以遍历该路径，在正确位置插入节点，然后将其冒泡。或者，您可以从根到叶子遍历该路径，在过程中将新项向下筛选。