广度优先搜索
code
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N(10000);
struct node
{
int adj;
struct node *next;
};
node *g[N];
int n,en;
bool visited[N];
queue<int> q;
void init()
{
int i,x,y;
node *p;
cin>>n>>en;
memset(g,0,sizeof(g));
for (i=0;i<en;i++)
{
cin>>x>>y;
p=new node; p->adj=y; p->next=g[x]; g[x]=p;
p=new node; p->adj=x; p->next=g[y]; g[y]=p;
}
memset(visited,0,sizeof(visited));
}
void bfs(int k)
{
node *p;
int i;
cout<<k<<" ";
visited[k]=true;
q.push(k);
while (!q.empty())
{
i=q.front();
q.pop();
p=g[i];
while (p)
{
if (!visited[p->adj])
{
cout<<p->adj<<" ";
visited[p->adj]=true;
q.push(p->adj);
}
p=p->next;
}
}
}
int main()
{
init();
for (int i=1;i<=n;i++)
if (!visited[i])
bfs(i);
system("pause");
return 0;
}
posted on 2011-10-29 14:00
龙在江湖 阅读(145)
评论(0) 编辑 收藏 引用 所属分类:
图论