C++实现字符类型图的DFS与BFS时出现段错误问题求助

你直接将ASCII字符作为数组/向量的下标访问导致内存越界：你的字符节点是'A'-'I'，对应ASCII值为65-73，但你申请的邻接表长度仅为9，访问adj['A']等价于访问adj[65]，远超出数组边界，触发非法内存访问导致段错误。

• 内存管理混乱：手动实现栈时用new申请节点，却用free释放，C++中new申请的堆内存必须用delete释放，混用会触发未定义行为
• 使用非标准变长数组：代码中bool visited[v]、vector<char> adj[v]等写法属于GCC扩展，不符合C++标准，可移植性差
• 全局栈指针设计不合理：全局的top指针没有每次调用DFS前重置，多次调用DFS会出现栈数据混乱

1. 新增字符到索引的映射函数，将'A'-'I'映射为0-8的合法下标：

inline int char2idx(char c) {
    return c - 'A';
}

2. 所有使用字符作为下标访问数组的位置，都先通过上述函数转换为整数索引
3. 将free(temp)替换为delete temp
4. 替换所有变长数组为std::vector，例如将bool visited[v]改为vector<bool> visited(v, false)
5. 每次调用DFS前重置全局栈top为NULL，或者直接使用C++标准库的std::stack替换手动实现的栈，避免全局变量污染

以Graph类的addEdge和DFS函数为例：

void Graph::addEdge(char v, char w) {
    // 字符转合法下标后再访问邻接表
    adj[char2idx(v)].push_back(w);
}

void Graph::DFS(char s) {
    vector<bool> visited(V, false);
    // 每次DFS前重置栈
    top = NULL;
    push(s);

    while (!isEmpty()) {
        char curr = peek();
        pop();
        int curr_idx = char2idx(curr);
        if (!visited[curr_idx]) {
            cout << curr << " ";
            visited[curr_idx] = true;
        }
        for (auto i = adj[curr_idx].begin(); i != adj[curr_idx].end(); ++i) {
            if (!visited[char2idx(*i)]) {
                push(*i);
            }
        }
    }
}

BFS相关的逻辑同理，所有用字符当下标的位置都先转换为0-8的索引即可。

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