depth first search graph

1###############
2#The Algorithm (In English):
3
4# 1) Pick any node. 
5# 2) If it is unvisited, mark it as visited and recur on all its 
6#    adjacent nodes. 
7# 3) Repeat until all the nodes are visited, or the node to be 
8#    searched is found.
9
10
11# The graph below (declared as a Python dictionary)
12# is from the linked website and is used for the sake of
13# testing the algorithm. Obviously, you will have your own
14# graph to iterate through.
15graph = {
16    'A' : ['B','C'],
17    'B' : ['D', 'E'],
18    'C' : ['F'],
19    'D' : [],
20    'E' : ['F'],
21    'F' : []
22}
23
24visited = set() # Set to keep track of visited nodes.
25
26
27##################
28# The Algorithm (In Code)
29
30def dfs(visited, graph, node):
31    if node not in visited:
32        print (node)
33        visited.add(node)
34        for neighbour in graph[node]:
35            dfs(visited, graph, neighbour)
36            
37# Driver Code to test in python yourself.
38# Note that when calling this, you need to
39# call the starting node. In this case it is 'A'.
40dfs(visited, graph, 'A')
41
42# NOTE: There are a few ways to do DFS, depending on what your
43# variables are and/or what you want returned. This specific
44# example is the most fleshed-out, yet still understandable,
45# explanation I could find.

1#include <bits/stdc++.h>
2using namespace std;
3 
4
5class Graph {
6    int V; 
7 
8 
9    list<int>* adj;
10 
11  
12    void DFSUtil(int v, bool visited[]);
13 
14public:
15    Graph(int V);
16 
17    void addEdge(int v, int w);
18 
19  
20    void DFS(int v);
21};
22 
23Graph::Graph(int V)
24{
25    this->V = V;
26    adj = new list<int>[V];
27}
28 
29void Graph::addEdge(int v, int w)
30{
31    adj[v].push_back(w); 
32}
33 
34void Graph::DFSUtil(int v, bool visited[])
35{
36   
37    visited[v] = true;
38    cout << v << " ";
39 
40   
41    list<int>::iterator i;
42    for (i = adj[v].begin(); i != adj[v].end(); ++i)
43        if (!visited[*i])
44            DFSUtil(*i, visited);
45}
46 
47
48void Graph::DFS(int v)
49{
50   
51    bool* visited = new bool[V];
52    for (int i = 0; i < V; i++)
53        visited[i] = false;
54 
55 
56    DFSUtil(v, visited);
57}
58 
59
60int main()
61{
62  
63    Graph g(4);
64    g.addEdge(0, 1);
65    g.addEdge(0, 2);
66    g.addEdge(1, 2);
67    g.addEdge(2, 0);
68    g.addEdge(2, 3);
69    g.addEdge(3, 3);
70 
71    cout << "Following is Depth First Traversal"
72            " (starting from vertex 2) \n";
73    g.DFS(2);
74 
75    return 0;
76}

1// performs a depth first search (DFS)
2// nodes are number from 1 to n, inclusive
3#include <bits/stdc++.h>
4using namespace std;
5
6
7vector<vector<int>> adj;  // adjacency list
8// visited[v] = true if v has been visited by dfs
9vector<bool> visited;
10
11bool all_edges_are_directed = true;
12
13void dfs(int v) {
14    // determines if dfs has been done on v
15    if(visited[v])
16        return;
17    visited[v] = true;
18
19    // write code here to do stuff with node v
20
21    // traverse nodes that are adjacent to v
22    for (int u: adj[v]){
23        dfs(u);
24    }
25}
26
27int main() {
28    int n;  // number of vertices
29    int m;  // number of edges
30    cin >> n >> m;
31    adj = vector<vector<int>>(n+1, vector<int>());
32    visited = vector<bool>(n+1, false);
33
34    for(int i = 0; i < m; ++i) {
35        // nodes a and b have an edge between them
36        int a, b;
37        cin >> a >> b;
38
39        if(all_edges_are_directed)
40            adj[a].push_back(b);
41        else {
42            adj[a].push_back(b);
43            adj[b].push_back(a);
44        }
45    }
46    
47    // do depth first search on all nodes
48    for(int i = 1; i <= n; ++i){
49        dfs(i);
50    }
51}

1#include<bits/stdc++.h>
2using namespace std;
3void addedge(vector<int>adj[],int u,int v)
4{
5    adj[u].push_back(v);
6    adj[v].push_back(u);
7}
8void dfs_u(int u,vector<int>adj[],vector<bool>& visited)
9{
10    visited[u]=true;
11    cout<<u<<" ";
12    int n=adj[u].size();
13    for(int i=0;i<n;i++)
14    {
15        if(visited[adj[u][i]]==false)
16        {
17            dfs_u(adj[u][i],adj,visited);
18        }
19    }
20}
21void dfs(vector<int>adj[],int v)
22{
23    vector<bool> visited(v,false);
24    for(int i=0;i<v;i++)
25    {
26        if(visited[i]==false)
27        {
28            dfs_u(i,adj,visited);
29        }
30    }
31}
32int main()
33{
34    int vertix;
35    cout<<"Enter the number of vertex :"<<endl;
36    cin>>vertix;
37    int edges;
38    cout<<"Enter the number of edges:"<<endl;
39    cin>>edges;
40    vector<int>graph_dfs[vertix];
41    int a,b;
42    cout<<"enter all the vertex pair that are connected:"<<endl;
43    for(int i=0;i<edges;i++)
44    {
45        cin>>a>>b;
46        addedge(graph_dfs,a,b);
47    }
48    cout<<"Depth first search view:"<<endl;
49    dfs(graph_dfs,vertix);
50}
51

1    DFS-iterative (G, s):                                   //Where G is graph and s is source vertex
2      let S be stack
3      S.push( s )            //Inserting s in stack 
4      mark s as visited.
5      while ( S is not empty):
6          //Pop a vertex from stack to visit next
7          v  =  S.top( )
8         S.pop( )
9         //Push all the neighbours of v in stack that are not visited   
10        for all neighbours w of v in Graph G:
11            if w is not visited :
12                     S.push( w )         
13                    mark w as visited
14
15
16    DFS-recursive(G, s):
17        mark s as visited
18        for all neighbours w of s in Graph G:
19            if w is not visited:
20                DFS-recursive(G, w)

1# HAVE USED ADJACENY LIST
2class Graph:
3    def __init__(self,lst=None):
4        self.lst=dict()
5        if lst is None:
6            pass
7        else:
8            self.lst=lst
9    def find_path(self,start,end):
10        self.checklist={}
11        for i in self.lst.keys():
12            self.checklist[i]=False
13        self.checklist[start]=True
14        store,extra=(self.explore(start,end))
15        if store==False:
16            print('No Path Found')
17        else:
18            print(extra)
19    def explore(self,start,end):
20        while True:
21            q=[]        
22            #print(self.checklist,q)
23            q.append(start)
24            flag=False            
25            for i in self.lst[start]:
26                if i==end:
27                    q.append(i)
28                    return True,q
29                if self.checklist[i]:
30                    pass
31                else:
32                    flag=True
33                    self.checklist[i]=True
34                    q.append(i)
35                    break   
36            if flag:
37                store,extra=self.explore(q[-1],end) 
38                if store==False:
39                    q.pop()
40                    if len(q)==0:return False
41                    return self.explore(q[-1],end)
42                elif store==None:
43                    pass
44                elif store==True:
45                    q.pop()
46                    q.extend(extra)
47                    return True,q
48            else:
49                return False,None
50    def __str__(self):return str(self.lst)
51if __name__=='__main__':
52    store={1: [2, 3, 4], 2: [3, 1], 3: [2, 1], 4: [5, 8, 1], 5: [4, 6, 7], 6: [5, 7, 9, 8], 7: [5, 6], 8: [4, 6, 9], 9: [6, 8, 10], 10: [9],11:[12,13]}
53    a=Graph(store)
54    a.find_path(1,11) # No Path Found 
55    a.find_path(1,6)# [1, 4, 5, 6]    
56    a.find_path(3,10)   # [3, 2, 1, 4, 5, 6, 9, 10] 
57    a.find_path(4,10)# [4, 5, 6, 9, 10]
58    print(a) #