جستجوی عمقی در هوش مصنوعی – توضیح الگوریتم به زبان ساده

1DFS(G,v)   ( v is the vertex where the search starts )    
2        Stack S := {};   ( start with an empty stack )    
3        for each vertex u, set visited[u] := false;    
4        push S, v;    
5        while (S is not empty) do    
6           u := pop S;    
7           if (not visited[u]) then    
8              visited[u] := true;    
9              for each unvisited neighbour w of uu    
10                 push S, w;    
11           end if    
12        end while    
13     END DFS()    

1// C++ program to print DFS traversal from
2// a given vertex in a  given graph
3#include <bits/stdc++.h>
4using namespace std;
5 
6// Graph class represents a directed graph
7// using adjacency list representation
8class Graph {
9public:
10    map<int, bool> visited;
11    map<int, list<int> > adj;
12 
13    // Function to add an edge to graph
14    void addEdge(int v, int w);
15 
16    // DFS traversal of the vertices
17    // reachable from v
18    void DFS(int v);
19};
20 
21void Graph::addEdge(int v, int w)
22{
23    // Add w to v’s list.
24    adj[v].push_back(w);
25}
26 
27void Graph::DFS(int v)
28{
29    // Mark the current node as visited and
30    // print it
31    visited[v] = true;
32    cout << v << " ";
33 
34    // Recur for all the vertices adjacent
35    // to this vertex
36    list<int>::iterator i;
37    for (i = adj[v].begin(); i != adj[v].end(); ++i)
38        if (!visited[*i])
39            DFS(*i);
40}
41 
42// Driver code
43int main()
44{
45    // Create a graph given in the above diagram
46    Graph g;
47    g.addEdge(0, 1);
48    g.addEdge(0, 2);
49    g.addEdge(1, 2);
50    g.addEdge(2, 0);
51    g.addEdge(2, 3);
52    g.addEdge(3, 3);
53 
54    cout << "Following is Depth First Traversal"
55            " (starting from vertex 2) \n";
56 
57    // Function call
58    g.DFS(2);
59 
60    return 0;
61}

1// Java program to print DFS traversal
2// from a given graph
3import java.io.*;
4import java.util.*;
5 
6// This class represents a
7// directed graph using adjacency
8// list representation
9class Graph {
10    private int V;
11 
12    // Array  of lists for
13    // Adjacency List Representation
14    private LinkedList<Integer> adj[];
15 
16    // Constructor
17    @SuppressWarnings("unchecked") Graph(int v)
18    {
19        V = v;
20        adj = new LinkedList[v];
21        for (int i = 0; i < v; ++i)
22            adj[i] = new LinkedList();
23    }
24 
25    // Function to add an edge into the graph
26    void addEdge(int v, int w)
27    {
28        // Add w to v's list.
29        adj[v].add(w);
30    }
31 
32    // A function used by DFS
33    void DFSUtil(int v, boolean visited[])
34    {
35        // Mark the current node as visited and print it
36        visited[v] = true;
37        System.out.print(v + " ");
38 
39        // Recur for all the vertices adjacent to this
40        // vertex
41        Iterator<Integer> i = adj[v].listIterator();
42        while (i.hasNext()) {
43            int n = i.next();
44            if (!visited[n])
45                DFSUtil(n, visited);
46        }
47    }
48 
49    // The function to do DFS traversal.
50    // It uses recursive DFSUtil()
51    void DFS(int v)
52    {
53        // Mark all the vertices as
54        // not visited(set as
55        // false by default in java)
56        boolean visited[] = new boolean[V];
57 
58        // Call the recursive helper
59        // function to print DFS
60        // traversal
61        DFSUtil(v, visited);
62    }
63 
64    // Driver Code
65    public static void main(String args[])
66    {
67        Graph g = new Graph(4);
68 
69        g.addEdge(0, 1);
70        g.addEdge(0, 2);
71        g.addEdge(1, 2);
72        g.addEdge(2, 0);
73        g.addEdge(2, 3);
74        g.addEdge(3, 3);
75 
76        System.out.println(
77            "Following is Depth First Traversal "
78            + "(starting from vertex 2)");
79 
80        // Function call
81        g.DFS(2);
82    }
83}

1# Python3 program to print DFS traversal
2# from a given  graph
3from collections import defaultdict
4 
5 
6# This class represents a directed graph using
7# adjacency list representation
8class Graph:
9 
10    # Constructor
11    def __init__(self):
12 
13        # Default dictionary to store graph
14        self.graph = defaultdict(list)
15 
16     
17    # Function to add an edge to graph
18    def addEdge(self, u, v):
19        self.graph[u].append(v)
20 
21     
22    # A function used by DFS
23    def DFSUtil(self, v, visited):
24 
25        # Mark the current node as visited
26        # and print it
27        visited.add(v)
28        print(v, end=' ')
29 
30        # Recur for all the vertices
31        # adjacent to this vertex
32        for neighbour in self.graph[v]:
33            if neighbour not in visited:
34                self.DFSUtil(neighbour, visited)
35 
36     
37    # The function to do DFS traversal. It uses
38    # recursive DFSUtil()
39    def DFS(self, v):
40 
41        # Create a set to store visited vertices
42        visited = set()
43 
44        # Call the recursive helper function
45        # to print DFS traversal
46        self.DFSUtil(v, visited)
47 
48 
49# Driver's code
50if __name__ == "__main__":
51    g = Graph()
52    g.addEdge(0, 1)
53    g.addEdge(0, 2)
54    g.addEdge(1, 2)
55    g.addEdge(2, 0)
56    g.addEdge(2, 3)
57    g.addEdge(3, 3)
58 
59    print("Following is Depth First Traversal (starting from vertex 2)")
60     
61    # Function call
62    g.DFS(2)

1// C# program to print DFS traversal
2// from a given graph
3using System;
4using System.Collections.Generic;
5 
6// This class represents a directed graph
7// using adjacency list representation
8class Graph {
9    private int V;
10 
11    // Array of lists for
12    // Adjacency List Representation
13    private List<int>[] adj;
14 
15    // Constructor
16    Graph(int v)
17    {
18        V = v;
19        adj = new List<int>[ v ];
20        for (int i = 0; i < v; ++i)
21            adj[i] = new List<int>();
22    }
23 
24    // Function to Add an edge into the graph
25    void AddEdge(int v, int w)
26    {
27        // Add w to v's list.
28        adj[v].Add(w);
29    }
30 
31    // A function used by DFS
32    void DFSUtil(int v, bool[] visited)
33    {
34        // Mark the current node as visited
35        // and print it
36        visited[v] = true;
37        Console.Write(v + " ");
38 
39        // Recur for all the vertices
40        // adjacent to this vertex
41        List<int> vList = adj[v];
42        foreach(var n in vList)
43        {
44            if (!visited[n])
45                DFSUtil(n, visited);
46        }
47    }
48 
49    // The function to do DFS traversal.
50    // It uses recursive DFSUtil()
51    void DFS(int v)
52    {
53        // Mark all the vertices as not visited
54        // (set as false by default in c#)
55        bool[] visited = new bool[V];
56 
57        // Call the recursive helper function
58        // to print DFS traversal
59        DFSUtil(v, visited);
60    }
61 
62    // Driver Code
63    public static void Main(String[] args)
64    {
65        Graph g = new Graph(4);
66 
67        g.AddEdge(0, 1);
68        g.AddEdge(0, 2);
69        g.AddEdge(1, 2);
70        g.AddEdge(2, 0);
71        g.AddEdge(2, 3);
72        g.AddEdge(3, 3);
73 
74        Console.WriteLine(
75            "Following is Depth First Traversal "
76            + "(starting from vertex 2)");
77 
78        // Function call
79        g.DFS(2);
80        Console.ReadKey();
81    }
82}

1// Javascript program to print DFS
2// traversal from a given 
3// graph
4 
5// This class represents a
6// directed graph using adjacency
7// list representation
8class Graph
9{
10     
11    // Constructor
12    constructor(v)
13    {
14        this.V = v;
15        this.adj = new Array(v);
16        for(let i = 0; i < v; i++)
17            this.adj[i] = [];
18    }
19     
20    // Function to add an edge into the graph
21    addEdge(v, w)
22    {
23         
24        // Add w to v's list.
25        this.adj[v].push(w); 
26    }
27     
28    // A function used by DFS
29    DFSUtil(v, visited)
30    {
31         
32        // Mark the current node as visited and print it
33        visited[v] = true;
34        console.log(v + " ");
35  
36        // Recur for all the vertices adjacent to this
37        // vertex
38        for(let i of this.adj[v].values())
39        {
40            let n = i
41            if (!visited[n])
42                this.DFSUtil(n, visited);
43        }
44    }
45     
46    // The function to do DFS traversal.
47    // It uses recursive
48    // DFSUtil()
49    DFS(v)
50    {
51         
52        // Mark all the vertices as
53        // not visited(set as
54        // false by default in java)
55        let visited = new Array(this.V);
56        for(let i = 0; i < this.V; i++)
57            visited[i] = false;
58  
59        // Call the recursive helper
60        // function to print DFS
61        // traversal
62        this.DFSUtil(v, visited);
63    }
64}
65 
66// Driver Code
67g = new Graph(4);
68  
69g.addEdge(0, 1);
70g.addEdge(0, 2);
71g.addEdge(1, 2);
72g.addEdge(2, 0);
73g.addEdge(2, 3);
74g.addEdge(3, 3);
75 
76console.log("Following is Depth First Traversal " + 
77               "(starting from vertex 2)");
78 
79g.DFS(2);