I'm trying to develop the code to make a parallel version of the BFS (topDown) algorithm on a graph. This is the code I have developed so far:

#define MAX 10000
int n; 
int v;
long dim = (long) MAX*MAX;
long* adj;
void create_graph();
void BF_Traversal();
void BFS(int v);

int main()
return 0;

bool isEmpty(int* array){
  for (int i=0;i<n;i++){
    if (array[i] != -1)
      return false;
  return true;
void topDownStep(int* frontier, int* next, int* parents){
  int index = 0;
  #pragma omp parallel for num_threads(4) 
  for (int i=0;i<n;i++){
    if (frontier[i]!=-1){
        for (int j=0;j<n;j++){
            long offset= frontier[i]*MAX + j;
            if (adj[offset]==1 && j!=v){
                if (parents[j] ==-1){
                    next[index] = j;


void BFS(int startVertex){
    int* frontier = malloc(n * sizeof(int));
    int* next = malloc(n * sizeof(int));
    int* parents = malloc(n * sizeof(int));
    memset( frontier, -1, n*sizeof(int) );
    memset( next, -1, n*sizeof(int) );
    memset( parents, -1, n*sizeof(int) );
    frontier[0] = startVertex;

    while (!isEmpty(frontier))
      printf("Visited frontier:\n");
      for (int i=0;i<n;i++){
      memset( next, -1, n*sizeof(int) );

void create_graph(){
adj = malloc(dim* sizeof(long));
int count,max_edge,origin,destin;
// FILE *in_file  = fopen("graph.txt", "r");
// fscanf(in_file, "%d %d", &n , &v);
// printf("%d - %d",n,v);
// max_edge = n*(n-1);
// while ( fscanf(in_file, "%d %d", &origin,&destin) != EOF )  { 
//     if((origin == -1) && (destin == -1))
//         break;
//     if(origin>=n || destin>=n || origin<0 || destin<0)
//         printf("Invalid edge!\n");
//     else
//         adj[origin][destin] = 1;
//         adj[destin][origin] = 1;
//     } 
n = MAX;
v= 0;
max_edge = n*(n-1);
for(int i =0;i<n;i++){
    for(int j=0;j<2;j++){
        int val = rand()%MAX;
            long offset = i*MAX+val;

I'm not sure if this approach is good or not for parallelizing such algorithm (see topDownStep).

The code seems to work correctly as the frontiers are visited in the right order, but I have a feeling that the code is not optimized.

Also I am afraid that race conditions may occur even if from the tests I have done it seems that this does not happen.

I look forward to your advice and I always thank you for your availability.

  • \$\begingroup\$ Please remove any commented out code, code that is commented out is not ready to be reviewed. \$\endgroup\$
    – pacmaninbw
    Feb 26, 2022 at 15:33
  • \$\begingroup\$ I have 2 comments from OpenMP point of view: 1) Your code does have race condition (when parents[j] is written and read by different threads), which is easy to fix, you just have to use atomic operations. 2) The much bigger problem is that your algorithm does depend on the order of execution of loop i. Try using #pragma omp parallel for num_threads(4) schedule(static,1) and you will see that the result may be different in each run. \$\endgroup\$
    – Laci
    Mar 19, 2022 at 8:57


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.