c++ - BFS 使用双端队列

Question

真的很难弄清楚如何修复我的代码。我知道显然存在错误，因为它没有运行，但我不确定错误到底是什么，也不确定如何修复它们。任何帮助/见解将不胜感激。谢谢!!

struct vertices
{
    int value;
    int parent;
    int visited;
    int distance;
};


int BFS(vertices *v, int **adj_matrix, int num_nodes)
{
    int target;
    int cur_v = 0;
    bool found = false;
    int steps = 0;
    cin >> target >> num_nodes;
    adj_matrix [num_nodes][num_nodes];
    deque<int> q;

    for(int i = 0; i < num_nodes; i++)
    {
        v[i].visited = 0;
        v[i].distance = INFINITY;
        v[i].parent = 0;

        v[1].visited = 1;
        v[i].distance = 0;
        q.push_front(v[1].value);

        while(!q.empty())
        {
            cur_v = q.front();
            q.pop_back();
            v[cur_v].visited = 1;
            for(int n=0; n< num_nodes; n++)
            {
                if(adj_matrix[cur_v][i] == n)
                {
                    if(v[n].visited == 0)
                    {
                        v[n].visited = 1;
                        v[n].distance = ((v[cur_v].distance)+1);
                        v[n].parent = cur_v;
                        q.push_front(v[n].value);
                        steps ++;
                    }
                } 
            }
        }
    }
    return steps;
}

int main()
{
    int target;
    int num_nodes;

    cin >> target;
    cin >> num_nodes;

    vertices *v = new vertices[num_nodes];

    int **adj_matrix [num_nodes][num_nodes];

    for(int i=0; i < num_nodes; ++i)
    {
        int node;
        int value;
        cin >> node >> value;

        int num_edges;
        cin >> num_edges;

        for(int j=0; j<num_edges;++j)
        {
            int other_node;
            cin >> other_node;

            **adj_matrix[node][other_node] = 1;
            **adj_matrix[other_node][node] = 1;
        }
    }
}

Answer 1

第一个明显的错误是你使用了错误的数据 结构。当你实现矩阵等已知概念时， BFS，你需要花大量时间思考如何 从算法中实现输入、输出、数据结构。

有些人喜欢用std::vector<std::vector<int>>对于矩阵。我几乎总是使用 std::vector<int>用于矩阵数据。

第二个错误是您正在改变算法。那东西不是BFS。一开始并不明显。

• 您在 BFS 实现中调用多个 BFS 实例。使用相同的输入顶点，其元素正在被修改。在下一个循环中，您不会从干净的状态开始。
• 您正在扁平化算法，移除抽象。如果您现在必须使用邻接表怎么办？你必须修改整个东西。

第三个明显的错误是编码风格。你没有做得这么糟糕，因为顶点结构是不言自明的

• 我必须突出显示 cur_v 的所有实例to 意识到它代表当前顶点。
• 使用 n柜台不是个好主意。
• 在算法实现中接受输入是一个很大的禁忌。