Первый поиск по глубине дает неправильный вывод

Question

Я написал приведенный ниже код для обхода приведенного выше графика с использованием поиска в глубину, результат которого я получаю 0 1 3 6 4 5 2.

Я хочу проверить, является ли это правильный обход с использованием DFS, если нет, то каков правильный обход. Кроме того, какие изменения мне нужно включить в мой код, чтобы получить правильный вывод.

public void DFSTraversal()
{

    int v;
    int vFirst = 0;
    Stack<Integer> st = new Stack<Integer>();
    Boolean[] visited = new Boolean[vert];
    for(int j = 0 ; j < vert ; j++ )
    {
        visited[j] = false;
    }

    // st is a stack
    st.push(vFirst);

    while(!st.isEmpty())
    {
        v = st.peek();
        if(!visited[v])
        {
            System.out.printf("%d " , +v);
            visited[v]=true;
        }

            for (int i = 0; i < vert; i++)
            {
                if ((matrix[v][i] == 1) && (!visited[i]))
                {
                    st.push(i);
                    visited[i] = true;
                    System.out.printf("%d ", +i);
                    v = i;
                }
            }

            st.pop();
    }

Метрика смежности

`0 1 1 0 0 0 0`
`1 0 0 1 1 1 0`
`1 0 0 0 0 0 1`
`0 1 0 0 0 0 1`
`0 1 0 0 0 0 1`
`0 1 0 0 0 0 0`
`0 0 1 1 1 0 0`

Answer 1

Исходя из рисунка, предполагая, что ребра вершины расположены в порядке возрастания по узлу, на который они указывают, правильный вывод: 0 1 3 6 2 4 5.

Проблема, с которой вы столкнулись, заключается в том, что вы как бы смешали подход динамического программирования со стеком и итеративный подход с переписывающим циклом for по всем вершинам. Если у вершины есть ребро к другой вершине, у которой индекс ниже, чем у ее собственного индекса, то она не будет сразу посещать узел и вместо этого прибегнет к стеку; последняя вершина, имеющая первый край непосещенных ребер.

Вы исправляете это, используя только подход динамического программирования, затем зацикливаясь назад по краям, помещая их в стек, если они не посещаются. Это оставит ребро для вершины с наименьшим значением на вершине стека, готовое для посещения на следующей итерации.

Ваш первый цикл поиска по глубине становится:

while (!st.isEmpty()) {
  int vertex = st.pop();
  if (!visited[vertex]) {
    System.out.printf("%d ", vertex);
    visited[vertex] = true;

    for (int i = numVertices - 1; i >= 0; --i) {
      if (edges[vertex][i] == 1 && !visited[i]) {
        st.push(i);
      }
    }
  }
}

Таким образом, вы используете только один цикл (ваш while цикл), который продолжает выталкивать из стека. Когда вершина посещается, она помещает все свои не посещенные и связанные вершины в стек в обратном порядке. Это означает, что следующий из посещаемых вершин (DFS) - это наименьший дочерний элемент вершины. Если вершина посещена и находится глубже в стеке, она просто игнорируется при повторном посещении, как и ее дочерние вершины (они также уже были посещены).

Тогда это можно было бы довольно просто изменить на поиск в первую очередь, сделав стек очередью и добавив вершины в порядке возрастания.

Answer 2

    public void DFSTraversal() {

        int v;
        int vFirst = 0;
        Stack<Integer> st = new Stack<Integer>();
        Boolean[] visited = new Boolean[vert];
        for (int j = 0; j < vert; j++) {
            visited[j] = false;
        }

        // st is a stack
        st.push(vFirst);

        while (!st.isEmpty()) {
            v = st.pop();
            if (!visited[v]) {
                System.out.printf("%d ", +v);
                visited[v] = true;
            }

            for (int i = 0; i < vert; i++) {
                if ((matrix[v][i] == 1) && (!visited[i])) {
                    st.push(i);
                }
            }

        }
    }

Вы должны печатать вывод, когда извлекаете элементы из стека. Если вы печатаете его в цикле for, где вы проверяете все соседние узлы текущего узла, он станет поиском по ширине (BFS), а не DFS.

EDIT:

Добавлен полный код.