Легко заметить, что поиск в ширину выполняется для каждой вершины независимо, а значит можно поровну разделить множество вершин на все доступные процессы, после чего собрать с них частичные результаты.

В приведённом ниже коде для краткости опущен ввод/вывод, а также реализация самого поиска в ширину.

struct link_data
{
    int articles_count, links_count;
    std::vector link_indices, link_targets;
};

struct article_metrics
{
    int eccentricity;
    double average_dist;
    int farthest;
};

MPI_Datatype g_mpi_article_metrics;

void void_MPI_Finalize()
{
    MPI_Finalize();
}

void free_mpi_article_metrics()
{
    MPI_Type_free(&g_mpi_article_metrics);
}

int main(int argc, char * argv[])
{
    MPI_Init(&argc, &argv);
    atexit(void_MPI_Finalize);

    int * host, flag, rank, size;
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    MPI_Comm_size(MPI_COMM_WORLD, &size);
    MPI_Comm_get_attr(MPI_COMM_WORLD, MPI_HOST, &host, &flag);

    if (!flag)
        return EXIT_FAILURE;

    int article_metrics_blocklengths[] = { 1, 1, 1, 1 }; 
    MPI_Aint article_metrics_displacements[] = {
        offsetof(article_metrics, eccentricity),
        offsetof(article_metrics, average_dist),
        offsetof(article_metrics, farthest),
        sizeof(article_metrics)
    };
    MPI_Datatype article_metrics_types[] =
    { MPI_INT, MPI_DOUBLE, MPI_INT, MPI_UB };

    MPI_Type_struct(
        sizeof article_metrics_types / sizeof *article_metrics_types,
        article_metrics_blocklengths,
        article_metrics_displacements,
        article_metrics_types,
        &g_mpi_article_metrics
    );

    MPI_Type_commit(&g_mpi_article_metrics);
    atexit(free_mpi_article_metrics);

    int scalars[2];
    link_data data;
    std::vector components;

    if (rank == *host)
    {
        // вводим data и components

        scalars[0] = data.articles_count;
        scalars[1] = data.links_count;
    }

    MPI_Bcast(scalars, 2, MPI_INT, *host, MPI_COMM_WORLD);

    if (rank != *host)
    {
        data.articles_count = scalars[0];
        data.links_count = scalars[1];
        data.link_indices.resize(data.articles_count + 1);
        data.link_targets.resize(data.links_count);
        components.resize(data.articles_count);
    }

    MPI_Bcast(&data.link_indices.front(), data.articles_count + 1, MPI_INT,
        *host, MPI_COMM_WORLD);
    MPI_Bcast(&data.link_targets.front(), data.links_count, MPI_INT, *host,
        MPI_COMM_WORLD);
    MPI_Bcast(&components.front(), data.articles_count, MPI_INT, *host,
        MPI_COMM_WORLD);

    std::vector queue(data.articles_count);
    std::vector distances(data.articles_count);
    std::vector part_lengths(size), part_disps(size);

    int part_length = (data.articles_count + size - 1) / size;

    for (int i = 0; i < size; ++i)
    {
        part_lengths[i] = part_length;
        part_disps[i] = part_length * i;
    }

    if (part_length * size != data.articles_count)
        part_lengths[size - 1] = data.articles_count % part_length;

    std::vector partial_results(part_lengths[rank]);

    for (int i = 0; i < part_lengths[rank]; ++i)
    {
        if (components[i + part_disps[rank]] == -1) continue;

        calculate_metrics(i + part_disps[rank], data.articles_count,
            &data.link_indices.front(), &data.link_targets.front(),
            &components.front(), &queue.front(), &distances.front(),
            &partial_results[i]);
    }

    if (rank == *host)
    {
        std::vector full_results(data.articles_count);

        MPI_Gatherv(&partial_results.front(), part_lengths[rank],
            g_mpi_article_metrics, &full_results.front(), &part_lengths.front(),
            &part_disps.front(), g_mpi_article_metrics, rank, MPI_COMM_WORLD);

        // выводим full_results
    }
}