java - Java /广度优先遍历：为什么不应该打印出倍数？

Question

邻接矩阵如下所示：

   A  B  C  D  E  
A  0  1  0  1  1  
B  1  0  0  1  1  
C  0  0  0  1  0  
D  1  1  1  0  0  
E  1  1  0  0  0 

但它输出

阿布德贝克

这是我的搜索代码，我想知道你是否能告诉我哪里出错了。应该确保这封信尚未被查看，但似乎没有。提前致谢。

public static void breadthFirst(int[][] adjM)
{
    int x = 0, y = 0;
    Queue<Character> queue = new Queue<Character>();
    ArrayList<Character> track = new ArrayList<Character>();

    //finding a vertex to use to search. 
    char ch1;
    outerloop:
    for (int i = 0; i < adjM.length; i++)
    {
        for (int j = 0; j < adjM.length; j++)
        {
            if (adjM[i][j] == 1)
            {
                x = i; y = j;
                ch1 = ((char)(x+65));
                queue.enqueue(ch1); 
                track.add(ch1);
                adjM[i][j] = 3; adjM[j][i] = 3;
                break outerloop;
            }
        }
    }

    while (!queue.isEmpty())
    {
        char c = queue.dequeue();
        System.out.print(c + "  ");

        for (int i = 0; i < adjM.length; i++)
        {
            for (int j = 0; j < adjM.length; j++)
            {   
                char chari = ((char)(i+65));
                char charj = ((char)(j+65));
                if (adjM[i][j] != 0)
                {
                    if (!track.contains(chari))
                    {
                        queue.enqueue(chari);
                        track.add(chari);
                        adjM[i][j] = 0; adjM[j][i] = 0;
                    }
                    else if (!track.contains(charj))
                    {
                        queue.enqueue(charj);
                        track.add(chari);
                        adjM[i][j] = 0; adjM[j][i] = 0;
                    }

                }
            }
        }
    }
}

Answer 1

在您的实施中：

                else if (!track.contains(charj))
                {
                    queue.enqueue(charj);
                    track.add(chari); // this should be charj
                    adjM[i][j] = 0; adjM[j][i] = 0;
                }

一个更简单的方法是这样的。不要修改邻接矩阵，只跟踪你访问过的东西。

while (!queue.isEmpty())
{
    char c = queue.dequeue();
    System.out.print(c + "  ");
    char chari = ((int)(c-65));
    track.add(chari)

    for (int j = 0; j < adjM.length; j++)
    {

        char charj = ((int)(j+65));
        if (adjM[chari][j] != 0  && !track.contains(chari))
        {
             queue.enqueue(charj);
        }
    }
}