Profundidad iterativa Primer recorrido del gráfico

El primer recorrido en profundidad (o búsqueda) de un gráfico es similar al primer recorrido en profundidad (DFS) de un árbol . El único inconveniente aquí es que, a diferencia de los árboles, los gráficos pueden contener ciclos, por lo que un Node puede visitarse dos veces. Para evitar procesar un Node más de una vez, use una array visitada booleana. 

Ejemplo:  

C++

// An Iterative C++ program to do DFS traversal from
// a given source vertex. DFS(int s) traverses vertices
// reachable from s.
#include<bits/stdc++.h>
using namespace std;
 
// This class represents a directed graph using adjacency
// list representation
class Graph
{
    int V;    // No. of vertices
    list<int> *adj;    // adjacency lists
public:
    Graph(int V);  // Constructor
    void addEdge(int v, int w); // to add an edge to graph
    void DFS(int s);  // prints all vertices in DFS manner
    // from a given source.
};
 
Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}
 
void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w); // Add w to v’s list.
}
 
// prints all not yet visited vertices reachable from s
void Graph::DFS(int s)
{
    // Initially mark all vertices as not visited
    vector<bool> visited(V, false);
 
    // Create a stack for DFS
    stack<int> stack;
 
    // Push the current source node.
    stack.push(s);
 
    while (!stack.empty())
    {
        // Pop a vertex from stack and print it
        int s = stack.top();
        stack.pop();
 
        // Stack may contain same vertex twice. So
        // we need to print the popped item only
        // if it is not visited.
        if (!visited[s])
        {
            cout << s << " ";
            visited[s] = true;
        }
 
        // Get all adjacent vertices of the popped vertex s
        // If a adjacent has not been visited, then push it
        // to the stack.
        for (auto i = adj[s].begin(); i != adj[s].end(); ++i)
            if (!visited[*i])
                stack.push(*i);
    }
}
 
// Driver program to test methods of graph class
int main()
{
    Graph g(5); // Total 5 vertices in graph
    g.addEdge(1, 0);
    g.addEdge(0, 2);
    g.addEdge(2, 1);
    g.addEdge(0, 3);
    g.addEdge(1, 4);
 
    cout << "Following is Depth First Traversal\n";
    g.DFS(0);
 
    return 0;
}

Java

//An Iterative Java program to do DFS traversal from
//a given source vertex. DFS(int s) traverses vertices
//reachable from s.
 
import java.util.*;
 
public class GFG
{
    // This class represents a directed graph using adjacency
    // list representation
    static class Graph
    {
        int V; //Number of Vertices
         
        LinkedList<Integer>[] adj; // adjacency lists
         
        //Constructor
        Graph(int V)
        {
            this.V = V;
            adj = new LinkedList[V];
             
            for (int i = 0; i < adj.length; i++)
                adj[i] = new LinkedList<Integer>();
             
        }
         
        //To add an edge to graph
        void addEdge(int v, int w)
        {
            adj[v].add(w); // Add w to v’s list.
        }
         
        // prints all not yet visited vertices reachable from s
        void DFS(int s)
        {
            // Initially mark all vertices as not visited
            Vector<Boolean> visited = new Vector<Boolean>(V);
            for (int i = 0; i < V; i++)
                visited.add(false);
     
            // Create a stack for DFS
            Stack<Integer> stack = new Stack<>();
             
            // Push the current source node
            stack.push(s);
             
            while(stack.empty() == false)
            {
                // Pop a vertex from stack and print it
                s = stack.peek();
                stack.pop();
                 
                // Stack may contain same vertex twice. So
                // we need to print the popped item only
                // if it is not visited.
                if(visited.get(s) == false)
                {
                    System.out.print(s + " ");
                    visited.set(s, true);
                }
                 
                // Get all adjacent vertices of the popped vertex s
                // If a adjacent has not been visited, then push it
                // to the stack.
                Iterator<Integer> itr = adj[s].iterator();
                 
                while (itr.hasNext())
                {
                    int v = itr.next();
                    if(!visited.get(v))
                        stack.push(v);
                }
                 
            }
        }
    }
     
    // Driver program to test methods of graph class
    public static void main(String[] args)
    {
        // Total 5 vertices in graph
        Graph g = new Graph(5);
         
        g.addEdge(1, 0);
        g.addEdge(0, 2);
        g.addEdge(2, 1);
        g.addEdge(0, 3);
        g.addEdge(1, 4);
             
        System.out.println("Following is the Depth First Traversal");
        g.DFS(0);
    }
}

Python3

# An Iterative Python program to do DFS traversal from
# a given source vertex. DFS(int s) traverses vertices
# reachable from s.
 
# This class represents a directed graph using adjacency
# list representation
class Graph:
    def __init__(self,V): # Constructor
        self.V = V        # No. of vertices
        self.adj  = [[] for i in range(V)]  # adjacency lists
 
    def addEdge(self,v, w):     # to add an edge to graph
        self.adj[v].append(w)    # Add w to v’s list.
 
 
    # prints all not yet visited vertices reachable from s
    def DFS(self,s):            # prints all vertices in DFS manner from a given source.
                                # Initially mark all vertices as not visited
        visited = [False for i in range(self.V)]
 
        # Create a stack for DFS
        stack = []
 
        # Push the current source node.
        stack.append(s)
 
        while (len(stack)):
            # Pop a vertex from stack and print it
            s = stack[-1]
            stack.pop()
 
            # Stack may contain same vertex twice. So
            # we need to print the popped item only
            # if it is not visited.
            if (not visited[s]):
                print(s,end=' ')
                visited[s] = True
 
            # Get all adjacent vertices of the popped vertex s
            # If a adjacent has not been visited, then push it
            # to the stack.
            for node in self.adj[s]:
                if (not visited[node]):
                    stack.append(node)
 
 
 
# Driver program to test methods of graph class
 
g = Graph(5); # Total 5 vertices in graph
g.addEdge(1, 0);
g.addEdge(0, 2);
g.addEdge(2, 1);
g.addEdge(0, 3);
g.addEdge(1, 4);
 
print("Following is Depth First Traversal")
g.DFS(0)
 
# This code is contributed by ankush_953

C#

// An Iterative C# program to do DFS traversal from
// a given source vertex. DFS(int s) traverses vertices
// reachable from s.
using System;
using System.Collections.Generic;
 
class GFG
{
    // This class represents a directed graph using adjacency
    // list representation
    public class Graph
    {
        public int V; // Number of Vertices
         
        public LinkedList<int>[] adj; // adjacency lists
         
        // Constructor
        public Graph(int V)
        {
            this.V = V;
            adj = new LinkedList<int>[V];
             
            for (int i = 0; i < adj.Length; i++)
                adj[i] = new LinkedList<int>();
             
        }
         
        // To add an edge to graph
        public void addEdge(int v, int w)
        {
            adj[v].AddLast(w); // Add w to v’s list.
        }
         
        // prints all not yet visited vertices reachable from s
        public void DFS(int s)
        {
            // Initially mark all vertices as not visited
            Boolean []visited = new Boolean[V];
                 
            // Create a stack for DFS
            Stack<int> stack = new Stack<int>();
             
            // Push the current source node
            stack.Push(s);
             
            while(stack.Count > 0)
            {
                // Pop a vertex from stack and print it
                s = stack.Peek();
                stack.Pop();
                 
                // Stack may contain same vertex twice. So
                // we need to print the popped item only
                // if it is not visited.
                if(visited[s] == false)
                {
                    Console.Write(s + " ");
                    visited[s] = true;
                }
                 
                // Get all adjacent vertices of the popped vertex s
                // If a adjacent has not been visited, then push it
                // to the stack.
                foreach(int v in adj[s])
                {
                    if(!visited[v])
                        stack.Push(v);
                }
                 
            }
        }
    }
     
    // Driver code
    public static void Main(String []args)
    {
        // Total 5 vertices in graph
        Graph g = new Graph(5);
         
        g.addEdge(1, 0);
        g.addEdge(0, 2);
        g.addEdge(2, 1);
        g.addEdge(0, 3);
        g.addEdge(1, 4);
             
        Console.Write("Following is the Depth First Traversal\n");
        g.DFS(0);
    }
}
 
// This code is contributed by Arnasb Kundu

Javascript

<script>
 
// An Iterative Javascript program to
// do DFS traversal from a given source
// vertex. DFS(int s) traverses vertices
// reachable from s.
 
// This class represents a directed graph
// using adjacency list representation
class Graph{
     
constructor(V)
{
    this.V = V;
    this.adj = new Array(V);
     
    for(let i = 0; i < this.adj.length; i++)
        this.adj[i] = [];
}
 
// To add an edge to graph
addEdge(v, w)
{
     
    // Add w to v’s list.
    this.adj[v].push(w);
}
 
// Prints all not yet visited
// vertices reachable from s
DFS(s)
{
     
    // Initially mark all vertices as not visited
    let visited = [];
    for(let i = 0; i < this.V; i++)
        visited.push(false);
 
    // Create a stack for DFS
    let stack = [];
      
    // Push the current source node
    stack.push(s);
      
    while(stack.length != 0)
    {
         
        // Pop a vertex from stack and print it
        s = stack.pop();
         
        // Stack may contain same vertex twice. So
        // we need to print the popped item only
        // if it is not visited.
        if (visited[s] == false)
        {
            document.write(s + " ");
            visited[s] = true;
        }
          
        // Get all adjacent vertices of the
        // popped vertex s. If a adjacent has
        // not been visited, then push it
        // to the stack.
        for(let node = 0;
                node < this.adj[s].length;
                node++)
        {
            if (!visited[this.adj[s][node]])
                stack.push(this.adj[s][node])
        }
    }
}
}
 
// Driver code
 
// Total 5 vertices in graph
let g = new Graph(5);
g.addEdge(1, 0);
g.addEdge(0, 2);
g.addEdge(2, 1);
g.addEdge(0, 3);
g.addEdge(1, 4);
 
document.write("Following is the Depth " +
               "First Traversal<br>");
g.DFS(0);
 
// This code is contributed by rag2127
 
</script>

C++

// An Iterative C++ program to do DFS traversal from
// a given source vertex. DFS(int s) traverses vertices
// reachable from s.
#include<bits/stdc++.h>
using namespace std;
 
// This class represents a directed graph using adjacency
// list representation
class Graph
{
    int V;    // No. of vertices
    list<int> *adj;    // adjacency lists
public:
    Graph(int V);  // Constructor
    void addEdge(int v, int w); // to add an edge to graph
    void DFS();  // prints all vertices in DFS manner
 
    // prints all not yet visited vertices reachable from s
    void DFSUtil(int s, vector<bool> &visited);
};
 
Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}
 
void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w); // Add w to v’s list.
}
 
// prints all not yet visited vertices reachable from s
void Graph::DFSUtil(int s, vector<bool> &visited)
{
    // Create a stack for DFS
    stack<int> stack;
 
    // Push the current source node.
    stack.push(s);
 
    while (!stack.empty())
    {
        // Pop a vertex from stack and print it
        int s = stack.top();
        stack.pop();
 
        // Stack may contain same vertex twice. So
        // we need to print the popped item only
        // if it is not visited.
        if (!visited[s])
        {
            cout << s << " ";
            visited[s] = true;
        }
 
        // Get all adjacent vertices of the popped vertex s
        // If a adjacent has not been visited, then push it
        // to the stack.
        for (auto i = adj[s].begin(); i != adj[s].end(); ++i)
            if (!visited[*i])
                stack.push(*i);
    }
}
 
// prints all vertices in DFS manner
void Graph::DFS()
{
    // Mark all the vertices as not visited
    vector<bool> visited(V, false);
 
    for (int i = 0; i < V; i++)
        if (!visited[i])
            DFSUtil(i, visited);
}
 
// Driver program to test methods of graph class
int main()
{
    Graph g(5);  // Total 5 vertices in graph
    g.addEdge(1, 0);
    g.addEdge(2, 1);
    g.addEdge(3, 4);
    g.addEdge(4, 0);
 
    cout << "Following is Depth First Traversal\n";
    g.DFS();
 
    return 0;
}

Java

//An Iterative Java program to do DFS traversal from
//a given source vertex. DFS() traverses vertices
//reachable from s.
 
import java.util.*;
 
public class GFG
{
    // This class represents a directed graph using adjacency
    // list representation
    static class Graph
    {
        int V; //Number of Vertices
         
        LinkedList<Integer>[] adj; // adjacency lists
         
        //Constructor
        Graph(int V)
        {
            this.V = V;
            adj = new LinkedList[V];
             
            for (int i = 0; i < adj.length; i++)
                adj[i] = new LinkedList<Integer>();
             
        }
         
        //To add an edge to graph
        void addEdge(int v, int w)
        {
            adj[v].add(w); // Add w to v’s list.
        }
         
        // prints all not yet visited vertices reachable from s
        void DFSUtil(int s, Vector<Boolean> visited)
        {
            // Create a stack for DFS
            Stack<Integer> stack = new Stack<>();
              
            // Push the current source node
            stack.push(s);
              
            while(stack.empty() == false)
            {
                // Pop a vertex from stack and print it
                s = stack.peek();
                stack.pop();
                  
                // Stack may contain same vertex twice. So
                // we need to print the popped item only
                // if it is not visited.
                if(visited.get(s) == false)
                {
                    System.out.print(s + " ");
                    visited.set(s, true);
                }
                  
                // Get all adjacent vertices of the popped vertex s
                // If a adjacent has not been visited, then push it
                // to the stack.
                Iterator<Integer> itr = adj[s].iterator();
                  
                while (itr.hasNext())
                {
                    int v = itr.next();
                    if(!visited.get(v))
                        stack.push(v);
                }
                  
            }
        }
         
        // prints all vertices in DFS manner
        void DFS()
        {
            Vector<Boolean> visited = new Vector<Boolean>(V);
            // Mark all the vertices as not visited
            for (int i = 0; i < V; i++)
                visited.add(false);
     
            for (int i = 0; i < V; i++)
                if (!visited.get(i))
                    DFSUtil(i, visited);
        }   
    }
     
    // Driver program to test methods of graph class
    public static void main(String[] args)
    {
        Graph g = new Graph(5);
        g.addEdge(1, 0);
        g.addEdge(2, 1);
        g.addEdge(3, 4);
        g.addEdge(4, 0);
          
        System.out.println("Following is Depth First Traversal");
        g.DFS();
    }
}

Python3

# An Iterative Python3 program to do DFS
# traversal from a given source vertex.
# DFS(s) traverses vertices reachable from s.
class Graph:
    def __init__(self, V):
        self.V = V
        self.adj = [[] for i in range(V)]
     
    def addEdge(self, v, w):
        self.adj[v].append(w) # Add w to v’s list.
     
    # prints all not yet visited vertices
    # reachable from s
    def DFSUtil(self, s, visited):
         
        # Create a stack for DFS
        stack = []
     
        # Push the current source node.
        stack.append(s)
     
        while (len(stack) != 0):
             
            # Pop a vertex from stack and print it
            s = stack.pop()
     
            # Stack may contain same vertex twice.
            # So we need to print the popped item only
            # if it is not visited.
            if (not visited[s]):
                print(s, end = " ")
                visited[s] = True
     
            # Get all adjacent vertices of the
            # popped vertex s. If a adjacent has not 
            # been visited, then push it to the stack.
            i = 0
            while i < len(self.adj[s]):
                if (not visited[self.adj[s][i]]):
                    stack.append(self.adj[s][i])
                i += 1
     
    # prints all vertices in DFS manner
    def DFS(self):
         
        # Mark all the vertices as not visited
        visited = [False] * self.V
        for i in range(self.V):
            if (not visited[i]):
                self.DFSUtil(i, visited)
 
# Driver Code
if __name__ == '__main__':
 
    g = Graph(5) # Total 5 vertices in graph
    g.addEdge(1, 0)
    g.addEdge(2, 1)
    g.addEdge(3, 4)
    g.addEdge(4, 0)
 
    print("Following is Depth First Traversal")
    g.DFS()
 
# This code is contributed by PranchalK

C#

// An Iterative C# program to do DFS traversal from
// a given source vertex. DFS() traverses vertices
// reachable from s.
using System;
using System.Collections.Generic;
 
class GFG
{
    // This class represents a directed graph using adjacency
    // list representation
    class Graph
    {
        public int V; // Number of Vertices
         
        public List<int>[] adj; // adjacency lists
         
        // Constructor
        public Graph(int V)
        {
            this.V = V;
            adj = new List<int>[V];
             
            for (int i = 0; i < adj.Length; i++)
                adj[i] = new List<int>();
             
        }
         
        // To add an edge to graph
        public void addEdge(int v, int w)
        {
            adj[v].Add(w); // Add w to v’s list.
        }
         
        // prints all not yet visited vertices reachable from s
        public void DFSUtil(int s, List<Boolean> visited)
        {
            // Create a stack for DFS
            Stack<int> stack = new Stack<int>();
             
            // Push the current source node
            stack.Push(s);
             
            while(stack.Count != 0)
            {
                // Pop a vertex from stack and print it
                s = stack.Peek();
                stack.Pop();
                 
                // Stack may contain same vertex twice. So
                // we need to print the popped item only
                // if it is not visited.
                if(visited[s] == false)
                {
                    Console.Write(s + " ");
                    visited[s] = true;
                }
                 
                // Get all adjacent vertices of the popped vertex s
                // If a adjacent has not been visited, then push it
                // to the stack.
                foreach(int itr in adj[s])
                {
                    int v = itr;
                    if(!visited[v])
                        stack.Push(v);
                }
                 
            }
        }
         
        // prints all vertices in DFS manner
        public void DFS()
        {
            List<Boolean> visited = new List<Boolean>(V);
             
            // Mark all the vertices as not visited
            for (int i = 0; i < V; i++)
                visited.Add(false);
     
            for (int i = 0; i < V; i++)
                if (!visited[i])
                    DFSUtil(i, visited);
        }
    }
     
    // Driver code
    public static void Main(String[] args)
    {
        Graph g = new Graph(5);
        g.addEdge(1, 0);
        g.addEdge(2, 1);
        g.addEdge(3, 4);
        g.addEdge(4, 0);
         
        Console.WriteLine("Following is Depth First Traversal");
        g.DFS();
    }
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
//An Iterative Javascript program to do DFS traversal from
//a given source vertex. DFS() traverses vertices
//reachable from s.
 
// This class represents a directed graph using adjacency
    // list representation
class Graph
{
     //Constructor
    constructor(V)
    {
        this.V=V;
        this.adj = new Array(V);
        for (let i = 0; i < this.adj.length; i++)
                this.adj[i] = [];
    }
     
    //To add an edge to graph
    addEdge(v,w)
    {
        this.adj[v].push(w); // Add w to v’s list.
    }
     
     // prints all not yet visited vertices reachable from s
    DFSUtil(s,visited)
    {
        // Create a stack for DFS
            let stack = [];
               
            // Push the current source node
            stack.push(s);
               
            while(stack.length != 0)
            {
                // Pop a vertex from stack and print it
                s = stack.pop();
                 
                   
                // Stack may contain same vertex twice. So
                // we need to print the popped item only
                // if it is not visited.
                if(visited[s] == false)
                {
                    document.write(s + " ");
                    visited[s] = true;
                }
                   
                // Get all adjacent vertices of the popped vertex s
                // If a adjacent has not been visited, then push it
                // to the stack.
                 
                   
                for (let itr=0;itr<this.adj[s].length;itr++)
                {
                    let v = this.adj[s][itr];
                    if(!visited[v])
                        stack.push(v);
                }
                   
            }
    }
     
    // prints all vertices in DFS manner
    DFS()
    {
        let visited = []
            // Mark all the vertices as not visited
            for (let i = 0; i < this.V; i++)
                visited.push(false);
      
            for (let i = 0; i < this.V; i++)
                if (!visited[i])
                    this.DFSUtil(i, visited);
            
    }
     
}
 
// Driver program to test methods of graph class
let g = new Graph(5);
g.addEdge(1, 0);
g.addEdge(2, 1);
g.addEdge(3, 4);
g.addEdge(4, 0);
 
document.write("Following is Depth First Traversal<br>");
g.DFS();
 
 
 
// This code is contributed by avanitrachhadiya2155
</script>

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *