这种写法的bfs和前面的最大区别在于它对队列的处理,之前的简单bfs是每次从队列中取出当前的访问节点后,之后就将它的邻接节点加入到队列中,这样明显不利于并行化,
为此,这里使用了两个队列,第一个队列上当前同一层的节点,第二个队列用来存储当前层节点的所有邻接节点,等到当前层的节点全部访问完毕后,再将第一个队列与第二个队列进行交换,即可。
这样做的优势在于便于以后的并行化。同一层的节点可以一起运行,不会受到下一层节点的干扰。
#include <stdio.h>
#include <queue>
#include <map>
#include <iostream>
#include <stdlib.h>
#include <omp.h>
#include <string>
#include <getopt.h>
#include "CycleTimer.h"
#include "graph.h"
#include "bfs.h"
using namespace std;
void clear(queue<int>& q) {
queue<int> empty;
swap(empty, q);
}
int main(){
string graph_filename="../../Data/facebook.txt";
graph g;
load_graph(graph_filename.c_str(),&g);
printf("Graph stats:\n");
printf(" Edges: %d\n", g.num_edges);
printf(" Nodes: %d\n", g.num_nodes);
queue<int> q1,q2;
int * distance=(int *)malloc(sizeof(int)*g.num_nodes);
for(int i=0;i<g.num_nodes;i++){
distance[i]=-1;
}
q1.push(1);
distance[1]=0;
while(!q1.empty()){
clear(q2);
for(int i=0;i<q1.size();i++){
int node=q1.front();
q1.pop();
cout<<node<<"->";
int start_edge=g.outgoing_starts[node];
int end_edge=(node==g.num_nodes-1)?g.num_edges:g.outgoing_starts[node+1];
for(int j=start_edge;j<end_edge;j++){
int outgoing=g.outgoing_edges[j];
if(distance[outgoing]==-1){
distance[outgoing]=1;
q2.push(outgoing);
}
}
}
swap(q1, q2);
}
return 1;
}