使用OpenMP并行化改进版BFS时代码段错误求助

关键问题分析 #

1. 未定义的n参数：make_tree_bfs_par函数中使用n初始化distances向量，但函数参数未传入n，导致未定义行为，这是段错误的核心诱因之一。
2. 未初始化的par数组：根节点的父节点值未设置，且par、vis未按节点数量正确初始化，引发无效内存访问。
3. 全局变量风险：vis和par作为全局变量使用，在并行环境中易引发状态混乱，且难以调试。

具体修复方案 #

1. 补充n参数到make_tree_bfs_par函数，确保所有向量能按节点数量正确初始化。
2. 将vis、par改为局部向量，通过引用传递给make_bfs_step，避免全局变量的并发风险。
3. 给根节点的父节点设置哨兵值（如-1），防止回边判断时访问未初始化内存。
4. 在回边判断逻辑中增加哨兵值校验，确保仅处理有效父节点的情况。

修正后的代码 #

#include <vector>
#include <omp.h>

using namespace std;
typedef vector<vector<int>> vvi;

const int NOT_VISITED_MARKER = -1;
const int NUM_THREADS = 4; // 根据硬件情况调整

void make_bfs_step(int u, int n, vector<int> &frontier, vector<int> &new_frontier, 
                   vector<int> &distances, vector<int> &vis, vector<int> &par,
                   vvi &backedge, vvi &adj, vvi &tree)
{
    #pragma omp parallel num_threads(NUM_THREADS)
    {
        vector<int> local_frontier;
        int id = omp_get_thread_num();
        int nthrds = omp_get_num_threads();
        
        // 分片处理当前frontier，避免线程竞争同一节点
        for (int i = id; i < frontier.size(); i += nthrds)
        {
            int node = frontier[i];
            for (auto v : adj[node])
            {
                // 原子操作保证每个节点仅被标记一次
                if (__sync_bool_compare_and_swap(&distances[v], NOT_VISITED_MARKER, distances[node] + 1))
                {
                    vis[v] = 1;
                    par[v] = node;
                    tree[node].push_back(v);
                    local_frontier.push_back(v);
                }
                // 仅当节点有有效父节点且v不是父节点时，记录回边
                else if (par[node] != -1 && par[node] != v)
                {
                    backedge[node].push_back(v);
                }
            }
        }
        
        // 临界区合并局部结果，避免并发写入冲突
        #pragma omp critical
        {
            new_frontier.insert(new_frontier.end(), local_frontier.begin(), local_frontier.end());
        }
    }
}

int make_tree_bfs_par(int u, int n, vvi &backedge, vvi &adj, vvi &tree)
{
    vector<int> frontier, new_frontier;
    vector<int> distances(n, NOT_VISITED_MARKER);
    vector<int> vis(n, 0);
    vector<int> par(n, -1); // 用-1标记无父节点的情况
    
    frontier.push_back(u);
    distances[u] = 0;
    vis[u] = 1;
    par[u] = -1; // 根节点无父节点
    
    while (!frontier.empty())
    {
        new_frontier.clear();
        make_bfs_step(u, n, frontier, new_frontier, distances, vis, par, backedge, adj, tree);
        swap(frontier, new_frontier);
    }
    
    return n; // 返回节点总数，可根据需求修改
}

额外注意事项 #

• 编译时需启用OpenMP支持（如GCC添加-fopenmp参数）。
• NUM_THREADS可改为omp_get_max_threads()以自动适配系统核心数。
• 若处理无向图，可进一步优化回边判断逻辑，避免重复记录双向边。

内容的提问来源于stack exchange，提问作者Ldr