使用邻接矩阵的深度优先算法无法正常工作

Question

我尝试做一个深度优先算法。这就是我到目前为止所拥有的。

void DepthFirst(int A[][100], int a, int visited[], int nNodes)
{
// Here I'm supposed to list all the nodes in the graph, starting with 'a'

// Mark 'a' visited (1)
visited[a] = 1;
// Write a
cout << char(a + 'a') << " , ";
// For each node n adjacent to 'a' do
for (int n = 0; n < nNodes; n++)
{
    if (A[a][n] = 1)
    {// If n is not visited, then
        if (visited[n] == 0)
        {
            DepthFirst(A, n, visited, nNodes);
        }
    }
}

我用下图来测试它：

具有以下邻接关系 table：

使用那个 table 我写了我的主要功能：

int main()
{
int a = 0;
int v[100] = { 0 };
int nNodes = 8;

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 },
};
DepthFirst(A, a, v, nNodes);
cout << endl;
return 0;
}

它不起作用。输出应该是

a,b,c,d,f,g,e,h,i,k,j,

相反，我得到

a,b,c,d,e,f,g,h

有人可以帮我解决吗？

Answer 1

您的代码中有两个问题。如果您足够好地询问编译器，第一个很容易找到。 g++ 与 -Wall tells you the first mistake right away - in DepthFirst, you wrote if (A[a][n] = 1) when you meant if (A[a][n] == 1). The next mistake is int nNodes = 8; in main. You have a graph with 11 nodes. Fix them both and profit!

使用邻接矩阵的深度优先算法无法正常工作

Depth first algorithm using an adjacency matrix not working properly

c++

depth-first-search