C++图DFS遍历报reference binding to null-pointer错误排查

求解LeetCode题目「查找图中是否存在有效路径」时出现如下运行时错误：

Line 1034: Char 9: runtime error: reference binding to null pointer of type 'std::vector<int, std::allocator<int>>' (stl_vector.h)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_vector.h:1043:9

原错误实现代码：

class Solution {
public:
    void dfs(int *visited,int node,vector<vector<int>>&adj)
    {
        visited[node]=1;
        for(auto child:adj[node])
        {
            if(visited[child]==-1)
                dfs(visited,child,adj);
        }
    }
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        vector<vector<int>>adj;
        for(auto it:edges)
        {
            adj[it[0]].push_back(it[1]);
            
        }
        int visited[n];
        for(int i=0;i<n;i++)
            visited[i]=-1;
        
        dfs(visited,source,adj);
        
        return visited[destination]==1;
    }
};

代码共有3处明确问题，也是做其他图论题时频繁触发同类报错的核心原因：

• 邻接表未初始化就按下标访问：声明vector<vector<int>> adj时没有指定大小，此时adj是空vector，直接写adj[it[0]]属于越界访问不存在的元素，会触发空引用的未定义行为，和报错信息完全对应。
• 无向图邻接表构建逻辑错误：题目中的图是无向图，边是双向连通的，原代码只给边的一个端点添加了邻接关系，漏了反向的邻接关系，就算不报错也会出现路径遍历不全的问题。
• 使用非标准的可变长数组：int visited[n]是GCC的扩展语法，不属于C标准规范，在LeetCode的clang编译环境、其他OJ的标准C编译环境下很容易出现内存越界、脏数据等问题。

修正后的可运行代码如下：

class Solution {
public:
    void dfs(vector<int>& visited, int node, vector<vector<int>>& adj)
    {
        visited[node] = 1;
        for (int child : adj[node])
        {
            if (visited[child] == -1)
            {
                dfs(visited, child, adj);
            }
        }
    }

    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        // 邻接表初始化时直接分配n个节点的存储空间
        vector<vector<int>> adj(n);
        for (auto& e : edges)
        {
            int u = e[0], v = e[1];
            // 无向图双向添加邻接关系
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        // 用标准vector替代可变长数组，初始化时直接把所有值设为-1
        vector<int> visited(n, -1);
        dfs(visited, source, adj);
        return visited[destination] == 1;
    }
};

• 邻接表声明后必须先按节点总数初始化大小，空vector绝对不能直接按下标读写
• 加边前先判断图类型：有向图只加单向边，无向图必须加双向边
• 所有长度由运行时参数决定的数组，统一用vector实现，不要用编译器扩展的可变长数组，避免跨环境异常

内容的提问来源于stack exchange，提问作者Vatsal A Mehta