搜索算法

Posted by

广度优先搜索算法

广度优先搜索(BFS)之所以如此得名是因为该算法始终是将已发现结点和未发现结点之间的边界, 沿其广度方向向外扩展.即算法需要在发现所有距离源结点s为k的所有结点之后,才会发现距离原点s为k + 1的其他结点.

BFS通常用来解决一些最优化问题,一些经典例子比如迷宫最短路问题,单源最短路等.

对于在图论上的BFS,首先要了解邻接表建图.

struct edge
{
    int to, next, w;
} s[1000];
int n, num, head[1000];

void build( int u, int v, int w )
{
    s[++num].w = w;
    s[num].next = head[u];
    s[num].to = v;
  	head[u] = num;
}

void work()
{
    int u, v, w;
    for ( int i = 0; i < n; i ++ )
    {
        scanf("%d %d %d", &u, &v, &w);
        build( u, v, w );
    }
}

用一个

Leave a Reply

邮箱地址不会被公开。 必填项已用*标注