Ответ 1

DFS без рекурсии в основном совпадает с BFS - но используйте stack вместо очереди в качестве структуры данных.

Тема Iterative DFS vs Recursive DFS и порядок разных элементов обрабатывает оба подхода и разницу между ними (и вы не будете пересекать узлы в тот же порядок!)

Алгоритм итеративного подхода в основном:

DFS(source):
  s <- new stack
  visited <- {} // empty set
  s.push(source)
  while (s is not empty):
    current <- s.pop()
    if (current is in visited):
        continue
    visited.add(current)
    // do something with current
    for each node v such that (current,v) is an edge:
        s.push(v)

Ответ 2

Это не ответ, а расширенный комментарий, показывающий применение алгоритма в @amit ответе на график в текущей версии вопроса, предполагая, что 1 - это начало node, а его соседи вставляются в порядок 2, 4, 3:

               1
             / |  \
            4  |   2
               3 /

Actions            Stack             Visited
=======            =====             =======
push 1             [1]               {}
pop and visit 1    []                {1}
 push 2, 4, 3      [2, 4, 3]         {1}
pop and visit 3    [2, 4]            {1, 3}
 push 1, 2         [2, 4, 1, 2]      {1, 3}
pop and visit 2    [2, 4, 1]         {1, 3, 2}
 push 1, 3         [2, 4, 1, 1, 3]   {1, 3, 2}
pop 3 (visited)    [2, 4, 1, 1]      {1, 3, 2}
pop 1 (visited)    [2, 4, 1]         {1, 3, 2}
pop 1 (visited)    [2, 4]            {1, 3, 2}
pop and visit 4    [2]               {1, 3, 2, 4}
  push 1           [2, 1]            {1, 3, 2, 4}
pop 1 (visited)    [2]               {1, 3, 2, 4}
pop 2 (visited)    []                {1, 3, 2, 4}

Таким образом, применение алгоритма, нажимающего 1 соседей в порядке 2, 4, 3, приводит к порядку посещения 1, 3, 2, 4. Независимо от порядка толчка для 1 соседей, 2 и 3 будут смежными в порядке посещения, потому что в зависимости от того, что посещено первым, будет нажато другое, которое еще не посещено, а также 1, который был посещен.

Ответ 3

Логика DFS должна быть:

1), если текущий node не посещен, посетите node и пометьте его как посещенный
2) для всех своих соседей, которые не были посещены, нажмите их в стек

Например, пусть определит класс GraphNode в Java:

class GraphNode {
    int index;
    ArrayList<GraphNode> neighbors;
}

и вот DFS без рекурсии:

void dfs(GraphNode node) {
    // sanity check
    if (node == null) {
        return;
    }

    // use a hash set to mark visited nodes
    Set<GraphNode> set = new HashSet<GraphNode>();

    // use a stack to help depth-first traversal
    Stack<GraphNode> stack = new Stack<GraphNode>();
    stack.push(node);

    while (!stack.isEmpty()) {
        GraphNode curr = stack.pop();

        // current node has not been visited yet
        if (!set.contains(curr)) {
            // visit the node
            // ...

            // mark it as visited
            set.add(curr);
        }

        for (int i = 0; i < curr.neighbors.size(); i++) {
            GraphNode neighbor = curr.neighbors.get(i);

            // this neighbor has not been visited yet
            if (!set.contains(neighbor)) {
                stack.push(neighbor);
            }
        }
    }
}

Мы можем использовать ту же логику, чтобы рекурсивно выполнять DFS, клонировать график и т.д.

Ответ 4

Рекурсия - это способ использования стека вызовов для хранения состояния обхода графика. Вы можете использовать стек явно, например, имея локальную переменную типа std::stack, тогда вам не понадобится рекурсия для реализации DFS, а просто цикл.

Ответ 5

в порядке. если вы все еще ищете Java-код

dfs(Vertex start){
    Stack<Vertex> stack = new Stack<>(); // initialize a stack
    List<Vertex> visited = new ArrayList<>();//maintains order of visited nodes
    stack.push(start); // push the start
    while(!stack.isEmpty()){ //check if stack is empty
        Vertex popped = stack.pop(); // pop the top of the stack
        if(!visited.contains(popped)){ //backtrack if the vertex is already visited
            visited.add(popped); //mark it as visited as it is not yet visited
            for(Vertex adjacent: popped.getAdjacents()){ //get the adjacents of the vertex as add them to the stack
                    stack.add(adjacent);
            }
        }
    }

    for(Vertex v1 : visited){
        System.out.println(v1.getId());
    }
}

Ответ 6

Код Python. Сложность времени равна O (V + E), где V и E - количество вершин и ребер соответственно. Сложность пространства - это O (V) из-за наихудшего случая, когда есть путь, который содержит каждую вершину без какого-либо обратного отслеживания (т.е. Путь поиска является линейной цепочкой ).

В стеке хранятся кортежи формы (vertex, vertex_edge_index), чтобы DFS можно было возобновить из определенной вершины на границе сразу после последнего ребра, обработанного из этой вершины (как и стек вызовов функции рекурсивного ДФС).

В примере кода используется полный орграф, где каждая вершина связана с каждой другой вершиной. Следовательно, нет необходимости хранить явный список ребер для каждого node, так как граф является списком ребер (граф G содержит каждую вершину).

numv = 1000
print('vertices =', numv)
G = [Vertex(i) for i in range(numv)]

def dfs(source):
  s = []
  visited = set()
  s.append((source,None))
  time = 1
  space = 0
  while s:
    time += 1
    current, index = s.pop()
    if index is None:
      visited.add(current)
      index = 0
    # vertex has all edges possible: G is a complete graph
    while index < len(G) and G[index] in visited:
      index += 1
    if index < len(G):
      s.append((current,index+1))
      s.append((G[index], None))
    space = max(space, len(s))
  print('time =', time, '\nspace =', space)

dfs(G[0])

Вывод:

time = 2000 
space = 1000

Обратите внимание, что время здесь измеряет операции V, а не E. Значение равно numv * 2, потому что каждая вершина рассматривается дважды, один раз при обнаружении и один раз при завершении.

Ответ 7

По сути, стек не может справиться с временем обнаружения и временем окончания, если мы хотим реализовать DFS со стеклом и хотим иметь дело с временем открытия и временем окончания, нам нужно будет прибегнуть к другому столу записывающего устройства, моему реализация показана ниже, проверьте правильность теста, ниже для случая 1, case-2 и case-3.

from collections import defaultdict

class Graph(object):

    adj_list = defaultdict(list)

    def __init__(self, V):
        self.V = V

    def add_edge(self,u,v):
        self.adj_list[u].append(v)

    def DFS(self):
        visited = []
        instack = []
        disc = []
        fini = []
        for t in range(self.V):
            visited.append(0)
            disc.append(0)
            fini.append(0)
            instack.append(0)

        time = 0
        for u_ in range(self.V):
            if (visited[u_] != 1):
                stack = []
                stack_recorder = []
                stack.append(u_)
                while stack:
                    u = stack.pop()
                    visited[u] = 1
                    time+=1
                    disc[u] = time
                    print(u)
                    stack_recorder.append(u)
                    flag = 0
                    for v in self.adj_list[u]:
                        if (visited[v] != 1):
                            flag = 1
                            if instack[v]==0:
                                stack.append(v)
                            instack[v]= 1



                    if flag == 0:
                        time+=1
                        temp = stack_recorder.pop()
                        fini[temp] = time
                while stack_recorder:
                    temp = stack_recorder.pop()
                    time+=1
                    fini[temp] = time
        print(disc)
        print(fini)

if __name__ == '__main__':

    V = 6
    G = Graph(V)

#==============================================================================
# #for case 1
#     G.add_edge(0,1)
#     G.add_edge(0,2)
#     G.add_edge(1,3)
#     G.add_edge(2,1)
#     G.add_edge(3,2) 
#==============================================================================

#==============================================================================
# #for case 2
#     G.add_edge(0,1)
#     G.add_edge(0,2)
#     G.add_edge(1,3)
#     G.add_edge(3,2)  
#==============================================================================

#for case 3
    G.add_edge(0,3)    
    G.add_edge(0,1)

    G.add_edge(1,4)
    G.add_edge(2,4)
    G.add_edge(2,5)
    G.add_edge(3,1)
    G.add_edge(4,3)
    G.add_edge(5,5)    


    G.DFS()   

Ответ 8

Я думаю, вам нужно использовать логический массив visited[n] для проверки того, посетил ли текущий node или не ранее.

Ответ 9

Рекурсивный алгоритм работает очень хорошо для DFS, поскольку мы пытаемся погрузиться настолько глубоко, насколько можем, т.е. как только мы найдем неисследованную вершину, мы сразу же исследуем его ПЕРВОГО не исследованного соседа. Вы должны BREAK из цикла for, как только вы найдете первого не исследованного соседа.

for each neighbor w of v
   if w is not explored
       mark w as explored
       push w onto the stack
       BREAK out of the for loop

Ответ 10

Я думаю, что это оптимизированная DFS, касающаяся пробела, если я ошибаюсь.

s = stack
s.push(initial node)
add initial node to visited
while s is not empty:
    v = s.peek()
    if for all E(v,u) there is one unvisited u:
        mark u as visited
        s.push(u)
    else 
        s.pop

Ответ 11

Использование Stack и реализация, выполняемые стеком вызовов в процессе рекурсии -

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

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

для ex -

См. примерный график здесь.

(0 (1 (2 (4 4) 2) (3 3) 1) 0) (6 (5 5) (7 7) 6)

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

(Здесь я использовал представление List Adjacency List и реализовал его как вектор списка (vector > AdjList) с помощью С++ STL)

void DFSUsingStack() {
    /// we keep a check of the vertices visited, the vector is set to false for all vertices initially.
    vector<bool> visited(AdjList.size(), false);

    stack<int> st;

    for(int i=0 ; i<AdjList.size() ; i++){
        if(visited[i] == true){
            continue;
        }
        st.push(i);
        cout << i << '\n';
        visited[i] = true;
        while(!st.empty()){
            int curr = st.top();
            for(list<int> :: iterator it = AdjList[curr].begin() ; it != AdjList[curr].end() ; it++){
                if(visited[*it] == false){
                    st.push(*it);
                    cout << (*it) << '\n';
                    visited[*it] = true;
                    break;
                }
            }
            /// We can move ahead from current only if a new vertex has been added on the top of the stack.
            if(st.top() != curr){
                continue;
            }
            st.pop();
        }
    }
}

Ответ 12

Следующий код Java будет полезен: -

private void DFS(int v,boolean[] visited){
    visited[v]=true;
    Stack<Integer> S = new Stack<Integer>();
    S.push(v);
    while(!S.isEmpty()){
        int v1=S.pop();     
        System.out.println(adjLists.get(v1).name);
        for(Neighbor nbr=adjLists.get(v1).adjList; nbr != null; nbr=nbr.next){
             if (!visited[nbr.VertexNum]){
                 visited[nbr.VertexNum]=true;
                 S.push(nbr.VertexNum);
             }
        }
    }
}
public void dfs() {
    boolean[] visited = new boolean[adjLists.size()];
    for (int v=0; v < visited.length; v++) {
        if (!visited[v])/*This condition is for Unconnected Vertices*/ {

            System.out.println("\nSTARTING AT " + adjLists.get(v).name);
            DFS(v, visited);
        }
    }
}

Ответ 13

Многие люди скажут, что нерекурсивная DFS - это просто BFS со стеком, а не с очередью. Это неточно, позвольте мне объяснить немного больше.

Рекурсивная DFS

Рекурсивная DFS использует стек вызовов для сохранения состояния, то есть вы не управляете отдельным стекем самостоятельно.

Однако для большого графика рекурсивная DFS (или любая рекурсивная функция) может привести к глубокой рекурсии, которая может привести к сбою вашей проблемы с переполнением стека (а не на этом веб-сайте реальная вещь).

Нерекурсивный DFS

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

Почему больше места?

Рассмотрим это:

// From non-recursive "DFS"
for (auto i&: adjacent) {
    if (!visited(i)) {
        stack.push(i);
    }
}

И сравните его с этим:

// From recursive DFS
for (auto i&: adjacent) {
    if (!visited(i)) {
        dfs(i);
    }
}

В первом фрагменте кода вы помещаете все соседние узлы в стек перед его повторением к следующей соседней вершине и с пространственной стоимостью. Если граф большой, он может иметь существенное значение.

Что делать?

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

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

Ленивый способ

В C/С++ ленивый подход заключается в компиляции вашей программы с большим размером стека и увеличении размера стека с помощью ulimit, но это действительно паршиво. В Java вы можете установить размер стека как параметр JVM.