邻接矩阵的dfs Stack overflow

Question

#include<iostream>
using namespace std;

#define MaxInt 32767
#define MaxVerTexNum 100
#define true 1

typedef int Status;
typedef int ArcType;
typedef char VerTexType;

//图的邻接矩阵存储表示
typedef struct//邻接矩阵两个表 vexs顶点表，arcs边表
{
    VerTexType vexs[MaxVerTexNum];
    ArcType arcs[MaxVerTexNum][MaxVerTexNum];
    int arcnum, vexnum;
}AMGraph;//邻接矩阵

//找到顶点的序号
Status LocateVex(AMGraph G, VerTexType w)
{
    for (int i = 0; i < G.vexnum; i++)
    {
        if (w == G.vexs[i])return i;
    }
    return -1;
}

//用邻接矩阵表示法创造无向网G
Status CreateUND(AMGraph& G)
{
    cin >> G.vexnum >> G.arcnum; 
    for (int i = 0; i < G.vexnum; i++)
        cin >> G.vexs[i]; 
    for (int i = 0; i < G.vexnum; i++)//记得初始化邻接矩阵
        for (int j = 0; j < G.vexnum; j++)
            G.arcs[i][j] = MaxInt;
    VerTexType v1, v2;
    ArcType w;
    int m, n;
    for (int k = 0; k < G.arcnum; k++)
    {
        cin >> v1 >> v2 >> w; 
        m = LocateVex(G, v1);
        n = LocateVex(G, v2);
        G.arcs[m][n] = w;
        G.arcs[n][m] = G.arcs[m][n];
    }
    return true;
}

bool visit[MaxVerTexNum];

void DFS(AMGraph G, VerTexType v)
{
    cout << v;
    int k = LocateVex(G, v);
    visit[k] = true;
    for (int w = 0; w < G.vexnum; w++) {
        if ((G.arcs[k][w] != MaxInt) && (!visit[w]))
            DFS(G, w);
    }
}

int main()
{
    AMGraph G;
    CreateUND(G);
    cout << "请输入要查找的点" << endl;
    VerTexType v;     
    cin >> v;
    DFS(G, v);
    return 0;
}

该代码在cs2022中会在dfs函数中显示0x00007FF6EF873947 处有未经处理的异常(在 图.exe 中): 0xC00000FD: Stack overflow (参数: 0x0000000000000001, 0x0000004143803000)。
该如何修改

Answer 1

引自免费微信小程序：皆我百晓生

针对你提供的代码，遇到的Stack overflow错误通常是因为递归调用栈溢出，这可能发生在递归深度过深时。在DFS函数中，每次递归调用都会在栈上分配空间，如果图的结构导致递归层数过多，就会耗尽栈空间，从而引发栈溢出。

解决这个问题的一种方法是将递归转换为迭代，通过显式地使用栈数据结构来控制深度优先搜索的流程。下面是一种修改后的非递归实现DFS的方法：

#include<iostream>
#include<stack>

using namespace std;

#define MaxInt 32767
#define MaxVerTexNum 100
#define true 1

typedef int Status;
typedef int ArcType;
typedef char VerTexType;

// 邻接矩阵存储表示
typedef struct{
    VerTexType vexs[MaxVerTexNum];
    ArcType arcs[MaxVerTexNum][MaxVerTexNum];
    int arcnum, vexnum;
}AMGraph;

// 找到顶点的序号
Status LocateVex(AMGraph G, VerTexType w){
    for (int i = 0; i < G.vexnum; i++){
        if (w == G.vexs[i]) return i;
    }
    return -1;
}

// 创建无向网G
Status CreateUND(AMGraph& G){
    cin >> G.vexnum >> G.arcnum;
    for (int i = 0; i < G.vexnum; i++)
        cin >> G.vexs[i];
    for (int i = 0; i < G.vexnum; i++)
        for (int j = 0; j < G.vexnum; j++)
            G.arcs[i][j] = MaxInt;
    VerTexType v1, v2;
    ArcType w;
    int m, n;
    for (int k = 0; k < G.arcnum; k++){
        cin >> v1 >> v2 >> w;
        m = LocateVex(G, v1);
        n = LocateVex(G, v2);
        G.arcs[m][n] = w;
        G.arcs[n][m] = G.arcs[m][n];
    }
    return true;
}

bool visit[MaxVerTexNum];

void DFS_iterative(AMGraph G, VerTexType v){
    stack<int> s;
    int start = LocateVex(G, v);
    s.push(start);
    visit[start] = true;

    while (!s.empty()){
        int current = s.top();
        s.pop();
        cout << G.vexs[current];

        for (int w = 0; w < G.vexnum; w++){
            if (G.arcs[current][w] != MaxInt && !visit[w]){
                visit[w] = true;
                s.push(w);
            }
        }
    }
}

int main(){
    AMGraph G;
    CreateUND(G);
    cout << "请输入要查找的点" << endl;
    VerTexType v;
    cin >> v;
    DFS_iterative(G, v);
    return 0;
}

这个版本的DFS使用了一个栈（std::stack）来追踪当前的节点及其邻居，避免了递归带来的潜在栈溢出问题。当栈不为空时，算法会不断从栈顶取出一个节点进行访问，并将其未被访问过的邻居加入栈中，直到所有可达的节点都被访问为止。这样，深度优先搜索就能在一个固定大小的栈空间内完成，避免了深度过大的递归调用。