BFS使用deque

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的所有实例，才能意识到它代表当前顶点。
• 使用n进行计数器并不是一个好主意。
• 算法实现中的输入是一个很大的非零。