Parallel BFS OpenMP C

Question

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:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<time.h>
#include<omp.h>
#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()
{
create_graph();
BFS(v);
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){
                    parents[j]=frontier[i];
                    next[index] = j;
                    index++;
                }
            }
        }
    }

  }

}
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))
    {
    
      topDownStep(frontier,next,parents);
      printf("Visited frontier:\n");
      for (int i=0;i<n;i++){
        if(frontier[i]!=-1)
            printf("%d\t",frontier[i]);
          
      }
      printf("\n");
      memcpy(frontier,next,n*sizeof(int));
      memset( next, -1, n*sizeof(int) );
    }
}

void create_graph(){
adj = malloc(dim* sizeof(long));
int count,max_edge,origin,destin;
srand(time(NULL));
// 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;
        if(i!=val){
            long offset = i*MAX+val;
            adj[offset]=1;
    }
    }
}
}

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.