简单的说一下广搜算法,带个例题NYOJ115 城市平乱

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 01 月 21 日

广度优先搜索(BFS)的原理和应用

二叉树中的层序遍历就属于一种BFS(Board First Search)

层序遍历会得到ABCDEFG的层序优先序列(BFS序列)。在层序遍历过程中,可以注意到先访问的节点的孩子节点必然先被访问(如访问了A后访问B和C,那么B的孩子结点一定在C的孩子结点前被访问――仅针对下一层的孩子而言)。据这个特性,可以用队列来实现这个遍历。

void Layer(bitree *p)
{
queue Q; //定义一个队列
node *N;
Q.push(*p); //起始点入队
while(!Q.empty())
{
N=Q.front();
Q.pop();
cout<data<lchild!=NULL) //将扩展子结点(仅一层)全都入队
Q.push(N->lchild);
if(N->rchild!=NULL)
Q.push(N->rchild);
}
}

BFS比它更进一步,可以针对图的结构进行BFS遍历

的BFS(从V1开始)路径是

广搜的一般结构如下:

定义一个队列;

起始点入队;

while(队列不空){

队头结点出队;

若它是所求的目标状态,跳出循环;

否则,将它扩展出的子结点,全都入队;

}

若循环中找到目标,输出结果;

否则输出无解;

它的主要特点是:

n 每次队头元素出队时,扩展其全部的子结点,并用队列记录下来。

n 搜索过程没有回溯,是一种牺牲空间换取时间的方法。

下边是给出的例题的代码

#include<iostream>  
#include<cstring>  
#include<queue>  
using namespace std;  
int city[1005][1005];  
struct army  
{  
    bool ishave;  
    int len;  
}armys[1005];  
bool visited[1005];  
int bfs(int Q,int M)  
{  
    int sum=999999999,temp=0;  
    queue<int> que;  
    memset(visited,0,sizeof(visited));  
    que.push(Q);  
    visited[Q]=1;  
    while(!que.empty())  
    {  
        temp=que.front();  
        for (int i=1;i<=M;i++)  
        {  
            if(!visited[i] && city[temp][i])  
            {  
                visited[i]=1;  
                que.push(i);  
                armys[i].len +=city[temp][i]+armys[temp].len;  
                if(armys[i].ishave && sum>armys[i].len) sum=armys[i].len;  
            }  
        }  
        que.pop();  
    }  
    return sum;  
}  
int main()  
{  
    int T,N,M,P,Q,temp,a,b,c;  
    cin>>T;  
    while(T--)  
    {  
        memset(armys,0,sizeof(armys));  
        memset(city,0,sizeof(city));  
        cin>>N>>M>>P>>Q;  
        for (int i=0;i<N;i++)  
        {  
            cin>>temp;  
            armys[temp].ishave=1;  
        }  
        for (int i=0;i<P;i++)  
        {  
            cin>>a>>b>>c;  
            if(city[a][b]>c || city[a][b] ==0)  
            {  
                city[a][b]=c;  
                city[b][a]=c;  
            }  
        }  
        cout<<bfs(Q,M)<<endl;  
    }  
    return 0;  
}  

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

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

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期日, 2017 年 12 月 17 日