c++ - 我的广度优先算法无法正常工作

Question

我尝试做广度优先算法。这就是我目前所拥有的。

void BreadthFirst(int A[][100], int a, int nNodes)
{
// Local variables
// Queue of nodes Q
int visited[100];
for (int i = 0; i < nNodes; i++)
    visited[i] = 0; // initially all nodes are not visited
// Initialize Q to be empty
    int Q[100];
    int readPtr = 0, writePtr = 0;
    // Mark 'a' visited
    visited[a] = 1;
    // Write 'a'
    cout << char(a + 'a');
    // Enqueue (Q,a)
    Q[writePtr++] = a;
    // While 'a' is not empty do
    while (readPtr != writePtr)
    {
        for (int n = 0; n < nNodes; n++)
        {
            if (A[n][readPtr] == 1)
            {
                // If 'n' is not visited
                if (visited[n] == 0)
                {
                    // Mark 'n' as visited
                    visited[n] = 1;
                    // Write 'n'
                    cout << char(n + 'a');
                    // enqueue (Q,n)
                    Q[writePtr++] = n;
                }
            }
        }
        readPtr++;
    }
    cout << endl;
}

我用下图来测试它:

具有以下邻接表:

使用该表我编写了我的主要功能:

int main()
{
int nNodes = 11;
int a = 0;
int A[][100] =
{
    { 0,1,0,0,1,0,0,1,1,0,0 },
    { 1,0,1,0,0,0,0,0,0,0,0 },
    { 0,1,0,1,1,1,0,0,0,0,0 },
    { 0,0,1,0,0,1,1,0,0,0,0 },
    { 1,0,1,0,0,0,0,1,0,1,0 },
    { 0,0,1,1,0,0,1,0,0,0,0 },
    { 0,0,0,1,0,1,0,0,0,0,0 },
    { 1,0,0,0,1,0,0,0,1,1,1 },
    { 1,0,0,0,0,0,0,1,0,0,1 },
    { 0,0,0,0,1,0,0,1,0,0,0 },
    { 0,0,0,0,0,0,0,1,1,0,0 },
};
BreadthFirst(A, a, nNodes);
return 0;
}

而且它不起作用。输出应该是

abhicjkdfg

相反我得到

abehicdfgjk

你能帮我解决一下吗？

Answer 1

您没有在 while 循环中正确访问队列而不是 A[n][readPtr] 它应该是 A[n][Q[readPtr]]在这个 while 循环中

while (readPtr != writePtr)
{
    for (int n = 0; n < nNodes; n++)
    {
        if (A[n][Q[readPtr]] == 1)
        {
            // If 'n' is not visited
            if (visited[n] == 0)
            {
                // Mark 'n' as visited
                visited[n] = 1;
                // Write 'n'
                cout << char(n + 'a');
                // enqueue (Q,n)
                Q[writePtr++] = n;
            }
        }
    }