как стек используется для отметки времени в DFS - PullRequest
Новая
       31

как стек используется для отметки времени в DFS

1 голос
/ 28 апреля 2020

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

например.

, если в графе есть узел 1 в качестве начального узла. 1 переходит на 2, а 2 - на 3.

Я реализовал часть кода ниже. Он должен возвращать 2d массив для времени начала и конца каждой вершины. 

boolean[] visited = new boolean[g.getNumberOfVertices()-1]
LinkedList<Integer> stack = new LinkedList<integer>();
int[][] times = new int[g.getNumberOfVertices()][2]; //[i][0] == start,  [i][1] == end

int timer = 0;
stack.push(startingVertex);

while(!stack.isEmpty())
{
    int v = stack.pop();
    timer++;
    times[v][0] = timer; //start time
    int children = 0;
    for (int i = 0; i < g.getEdgeMatrix()[v].length; i++)
    {    
        if(g.getEdgeMatrix()[v][i] == 1)
        { 
            children++;
            if(visited[i] == false)
            {
                stack.push(i)
                visited[i] = true;
            }
         }
     }
    if(children == 0)
    {
        times[v][1] == timer + 1; // end time
    }
}

Это может быть закодировано неправильно, но я немного потерян здесь.

Вот как это работает ниже:

узел 1 вытолкнут и запускается в момент времени 1. узел 2 добавляется в стек, затем выталкивается запускается в момент 1. узел 3 добавляется в стек, а затем выталкивается запускается в момент 3. Нет дочерних элементов, поэтому время заканчивается в 4 для узел 3. стек пуст! выходит, пока l oop.

Как мне вернуться назад к узлу 1, чтобы закончить время?

...