Esto no es una respuesta, sino un comentario extendido, que muestra la aplicación del algoritmo en la respuesta de @amit al gráfico en la versión actual de la pregunta, suponiendo que 1 es el nodo de inicio y sus vecinos se empujan en el orden 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}

Aplicando así el algoritmo que empuja a los vecinos de 1 en el orden 2, 4, 3 resulta en el orden de visita 1, 3, 2, 4. Independientemente del orden de empuje para los vecinos de 1, 2 y 3 serán adyacentes en el orden de visita porque lo que se visite primero empujará el otro, que aún no se ha visitado, así como 1 que se ha visitado.

La lógica DFS debería ser:

1) si el nodo actual no es visitado, visite el nodo y márquelo como visitado
2) para todos sus vecinos que no han sido visitados, empujarlos a la pila

Por ejemplo, definamos una clase GraphNode en Java:

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

Y aquí está el DFS sin recursión:

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);
            }
        }
    }
}

Podemos usar la misma lógica para hacer DFS recursivamente, clonar gráfico, etc.

La recursión es una forma de usar la pila de llamadas para almacenar el estado del recorrido del gráfico. Puede usar la pila explícitamente, por ejemplo, teniendo una variable local de tipo std::stack, entonces no necesitará la recursión para implementar el DFS, sino solo un bucle.

Bien. si todavía está buscando un código 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());
    }
}

Código Python. El tiempo es la complejidad O(V+E) donde V y E es el número de vértices y aristas, respectivamente. La complejidad del espacio es O (V ) debido al peor de los casos donde hay una ruta que contiene cada vértice sin ningún retroceso (es decir, la ruta de búsqueda es una cadena lineal ).

La pila almacena tuplas de la forma (vértice, vertex_edge_index) para que el DFS se pueda reanudar desde un vértice particular en el borde inmediatamente después de la última arista que se procesó desde ese vértice (al igual que la pila de llamadas a funciones de un DFS recursivo).

El código de ejemplo utiliza un dígrafo completo donde cada vértice está conectado a cada otro vértice. Por lo tanto, no es necesario almacenar una lista de bordes explícita para cada nodo, ya que el gráfico es una lista de bordes (el gráfico G contiene cada vértice).

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])

Salida:

time = 2000 
space = 1000

Tenga en cuenta que el tiempo aquí está midiendo V operaciones y no E. El valor es numv *2 porque cada vértice se considera dos veces, una en el descubrimiento y otra en el acabado.

Acutalmente, stack no es muy capaz de lidiar con el tiempo de descubrimiento y el tiempo de finalización, si queremos implementar DFS con stack, y queremos lidiar con el tiempo de descubrimiento y el tiempo de finalización, necesitaríamos recurrir a otra pila de grabadoras, mi implementación se muestra a continuación, tiene prueba correcta, a continuación es para el gráfico case-1, case-2 y 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()   

Creo que necesita usar una matriz booleana visited[n] para verificar si el nodo actual se visita o no antes.

Un algoritmo recursivo funciona muy bien para DFS, ya que tratamos de sumergirnos lo más profundamente posible, es decir. tan pronto como encontremos un vértice no explorado, vamos a explorar su PRIMER vecino no explorado de inmediato. Necesitas salir del bucle for tan pronto como encuentres al primer vecino no explorado.

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

Creo que este es un DFS optimizado con respecto al espacio-corrígeme si me equivoco.

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

Usando Stack e implementando como lo hace la pila de llamadas en el proceso de recursión -

La idea es empujar un vértice en la pila, y luego empujar su vértice adyacente a él que se almacena en una lista de adyacencia en el índice del vértice y luego continuar este proceso hasta que no podamos avanzar en el gráfico, ahora si no podemos avanzar en el gráfico, entonces eliminaremos el vértice que está actualmente en la parte superior de la pila, ya que no puede llevarnos a ningún vértice que sea sin visitar.

Ahora, usando stack nos encargamos del punto en que el vértice solo se elimina de la pila cuando todos los vértices que se pueden explorar desde el vértice actual se han visitado, lo que se estaba haciendo por el proceso de recursión automáticamente.

Para ex -

Vea el gráfico de ejemplo aquí.

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

El paréntesis anterior muestra el orden en que el vértice es añadido en la pila y eliminado de la pila, por lo que un paréntesis para un vértice se cierra solo cuando todos los vértices que se pueden visitar desde él se han hecho.

(Aquí he utilizado la representación de Lista de Adyacencia e implementado como un vector de lista (vector > AdjList) mediante el uso de C++ 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();
        }
    }
}

El siguiente código Java será útil: -

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);
        }
    }
}

Muchas personas dirán que DFS no recursivo es solo BFS con una pila en lugar de una cola. Eso no es exacto, déjame explicarte un poco más.

DFS recursivo

El DFS recursivo usa la pila de llamadas para mantener el estado, lo que significa que usted no administra una pila separada.

Sin embargo, para un gráfico grande, DFS recursivo (o cualquier función recursiva que sea) puede resultar en una recursión profunda, que puede bloquear su problema con un desbordamiento de pila (no este sitio web, el real thing ).

DFS no recursivo

DFS no es lo mismo que BFS. Tiene un uso de espacio diferente, pero si lo implementa igual que BFS, pero usa una pila en lugar de una cola, usará más espacio que DFS no recursivo.

¿Por qué más espacio?

Considere esto:

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

Y compáralo con esto:

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

En la primera pieza de código que está poniendo todos los nodos adyacentes en la pila antes de iterar al siguiente vértice adyacente y que tiene un costo de espacio. Si el gráfico es grande puede hacer una diferencia significativa.

¿Qué hacer entonces?

Si decide resolver el problema de espacio iterando sobre la lista de adyacencia nuevamente después de hacer estallar la pila, eso agregará un costo de complejidad de tiempo.

Una solución es agregar elementos a la pila uno por uno, a medida que los visita. Para lograr esto, puede guardar un iterador en la pila para reanudar la iteración después de estallar.

Lazy way

En C / C++, un perezoso el enfoque es compilar su programa con un tamaño de pila más grande y aumentar el tamaño de pila a través de ulimit, pero eso es realmente pésimo. En Java puede establecer el tamaño de pila como un parámetro JVM.