Answers for "depth first search"

python depth first search

# left to right, pre-order depth first tree search, iterative. O(n) time/space
def depthFirstSearch(root):
    st = [root]
    while st:
        current = st.pop()
        print(current)
        if current.right is not None: st.append(current.right) 
        if current.left is not None: st.append(current.left)

depth first search

// performs a depth first search (DFS)
// nodes are number from 1 to n, inclusive
#include <bits/stdc++.h>
using namespace std;


vector<vector<int>> adj;  // adjacency list
// visited[v] = true if v has been visited by dfs
vector<bool> visited;

bool all_edges_are_directed = true;

void dfs(int v) {
    // determines if dfs has been done on v
    if(visited[v])
        return;
    visited[v] = true;

    // write code here to do stuff with node v

    // traverse nodes that are adjacent to v
    for (int u: adj[v]){
        dfs(u);
    }
}

int main() {
    int n;  // number of vertices
    int m;  // number of edges
    cin >> n >> m;
    adj = vector<vector<int>>(n+1, vector<int>());
    visited = vector<bool>(n+1, false);

    for(int i = 0; i < m; ++i) {
        // nodes a and b have an edge between them
        int a, b;
        cin >> a >> b;

        if(all_edges_are_directed)
            adj[a].push_back(b);
        else {
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
    }
    
    // do depth first search on all nodes
    for(int i = 1; i <= n; ++i){
        dfs(i);
    }
}

depth first search graph

#include<bits/stdc++.h>
using namespace std;
void addedge(vector<int>adj[],int u,int v)
{
    adj[u].push_back(v);
    adj[v].push_back(u);
}
void dfs_u(int u,vector<int>adj[],vector<bool>& visited)
{
    visited[u]=true;
    cout<<u<<" ";
    int n=adj[u].size();
    for(int i=0;i<n;i++)
    {
        if(visited[adj[u][i]]==false)
        {
            dfs_u(adj[u][i],adj,visited);
        }
    }
}
void dfs(vector<int>adj[],int v)
{
    vector<bool> visited(v,false);
    for(int i=0;i<v;i++)
    {
        if(visited[i]==false)
        {
            dfs_u(i,adj,visited);
        }
    }
}
int main()
{
    int vertix;
    cout<<"Enter the number of vertex :"<<endl;
    cin>>vertix;
    int edges;
    cout<<"Enter the number of edges:"<<endl;
    cin>>edges;
    vector<int>graph_dfs[vertix];
    int a,b;
    cout<<"enter all the vertex pair that are connected:"<<endl;
    for(int i=0;i<edges;i++)
    {
        cin>>a>>b;
        addedge(graph_dfs,a,b);
    }
    cout<<"Depth first search view:"<<endl;
    dfs(graph_dfs,vertix);
}

depth first search stack

DFS-iterative (G, s):                                   //Where G is graph and s is source vertex
      let S be stack
      S.push( s )            //Inserting s in stack 
      mark s as visited.
      while ( S is not empty):
          //Pop a vertex from stack to visit next
          v  =  S.top( )
         S.pop( )
         //Push all the neighbours of v in stack that are not visited   
        for all neighbours w of v in Graph G:
            if w is not visited :
                     S.push( w )         
                    mark w as visited


    DFS-recursive(G, s):
        mark s as visited
        for all neighbours w of s in Graph G:
            if w is not visited:
                DFS-recursive(G, w)

depth first search

# HAVE USED ADJACENY LIST
class Graph:
    def __init__(self,lst=None):
        self.lst=dict()
        if lst is None:
            pass
        else:
            self.lst=lst
    def find_path(self,start,end):
        self.checklist={}
        for i in self.lst.keys():
            self.checklist[i]=False
        self.checklist[start]=True
        store,extra=(self.explore(start,end))
        if store==False:
            print('No Path Found')
        else:
            print(extra)
    def explore(self,start,end):
        while True:
            q=[]        
            #print(self.checklist,q)
            q.append(start)
            flag=False            
            for i in self.lst[start]:
                if i==end:
                    q.append(i)
                    return True,q
                if self.checklist[i]:
                    pass
                else:
                    flag=True
                    self.checklist[i]=True
                    q.append(i)
                    break   
            if flag:
                store,extra=self.explore(q[-1],end) 
                if store==False:
                    q.pop()
                    if len(q)==0:return False
                    return self.explore(q[-1],end)
                elif store==None:
                    pass
                elif store==True:
                    q.pop()
                    q.extend(extra)
                    return True,q
            else:
                return False,None
    def __str__(self):return str(self.lst)
if __name__=='__main__':
    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]}
    a=Graph(store)
    a.find_path(1,11) # No Path Found 
    a.find_path(1,6)# [1, 4, 5, 6]    
    a.find_path(3,10)   # [3, 2, 1, 4, 5, 6, 9, 10] 
    a.find_path(4,10)# [4, 5, 6, 9, 10]
    print(a) #