十度好友问题
题目:
比如A认识B,B认识C,但是A不认识C, 那么称C是A的二度好友。找出某个人的所有十度好友. 数据量为10万;
本题是BFS算法的一个经典应用;
首先图的定义如下:
void find(node_pointer graph[],int n,int start,int deepth){std::queue<int> q;int visited[N];for(int i=0;i<N;i++)visited[i]=false;int cur,count,last;q.push(start);while(!q.empty()&&deepth>-1){int count=0;last=q.size();while(count<last){cur=q.front();current=graph[cur];q.pop();visited[cur]=true;while(current!=NULL){if(!visited[current->vertex])q.push(current->vertex);current=current->link;}count++}deepth--;}cout<<"The deephth friends of "<<start<<" are :"<<endl;while(!q.empty()){cout<<q.front()<<" ";q.pop();}}