"DFS" Code Answer's

DFS in c++

By VeNOM on Dec 08, 2020

#include <bits/stdc++.h>
using namespace std;
 

class Graph {
    int V; 
 
 
    list<int>* adj;
 
  
    void DFSUtil(int v, bool visited[]);
 
public:
    Graph(int V);
 
    void addEdge(int v, int w);
 
  
    void DFS(int v);
};
 
Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}
 
void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w); 
}
 
void Graph::DFSUtil(int v, bool visited[])
{
   
    visited[v] = true;
    cout << v << " ";
 
   
    list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
        if (!visited[*i])
            DFSUtil(*i, visited);
}
 

void Graph::DFS(int v)
{
   
    bool* visited = new bool[V];
    for (int i = 0; i < V; i++)
        visited[i] = false;
 
 
    DFSUtil(v, visited);
}
 

int main()
{
  
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);
 
    cout << "Following is Depth First Traversal"
            " (starting from vertex 2) \n";
    g.DFS(2);
 
    return 0;
}

Add Comment

dfs python

By actuallyitsnathaniel on Oct 05, 2020

###############
#The Algorithm (In English):

# 1) Pick any node. 
# 2) If it is unvisited, mark it as visited and recur on all its 
#    adjacent nodes. 
# 3) Repeat until all the nodes are visited, or the node to be 
#    searched is found.


# The graph below (declared as a Python dictionary)
# is from the linked website and is used for the sake of
# testing the algorithm. Obviously, you will have your own
# graph to iterate through.
graph = {
    'A' : ['B','C'],
    'B' : ['D', 'E'],
    'C' : ['F'],
    'D' : [],
    'E' : ['F'],
    'F' : []
}

visited = set() # Set to keep track of visited nodes.


##################
# The Algorithm (In Code)

def dfs(visited, graph, node):
    if node not in visited:
        print (node)
        visited.add(node)
        for neighbour in graph[node]:
            dfs(visited, graph, neighbour)
            
# Driver Code to test in python yourself.
# Note that when calling this, you need to
# call the starting node. In this case it is 'A'.
dfs(visited, graph, 'A')

# NOTE: There are a few ways to do DFS, depending on what your
# variables are and/or what you want returned. This specific
# example is the most fleshed-out, yet still understandable,
# explanation I could find.

Source: www.educative.io

Add Comment

DFS explained

By Annoying Alpaca on Mar 19, 2021

 def depth_first_search(graph):
    visited, stack = set(), [root]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)
    return visited

Source: brilliant.org

Add Comment

depth first search

By Ranger on Oct 11, 2020

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

Add Comment

DFS

By Itchy Impala on May 31, 2021

import java.io.*;
import java.util.*;
 

class Graph {
    private int V;                              //number of nodes
 
    private LinkedList<Integer> adj[];              //adjacency list
 
    public Graph(int v)
    {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
{
          adj[i] = new LinkedList();
    	}
 
    void addEdge(int v, int w)
    {
        adj[v].add(w);                              //adding an edge to the adjacency list (edges are bidirectional in this example)
    }
 

    void DFSUtil(int vertex, boolean nodes[])
    {

        nodes[vertex] = true;                         //mark the node as explored
        System.out.print(vertex + " ");
        int a = 0;
 
        for (int i = 0; i < adj[vertex].size(); i++)  //iterate through the linked list and then propagate to the next few nodes
            {
                a = adj[vertex].get(i);
                if (!nodes[a])                    //only propagate to next nodes which haven't been explored
                {
                    DFSUtil(a, nodes);
                }
            }  
    }

    void DFS(int v)
    {
        boolean already[] = new boolean[V];             //initialize a new boolean array to store the details of explored nodes
        DFSUtil(v, already);
    }
 
    public static void main(String args[])
    {
        Graph g = new Graph(6);
 
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 0);
        g.addEdge(1, 3);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 4);
        g.addEdge(3, 5);
        g.addEdge(4, 3);
        g.addEdge(5, 3);
 
        System.out.println(
            "Following is Depth First Traversal: ");
 
        g.DFS(0);
    }
}

Source: favtutor.com

Add Comment

DFS

By Annoyed Antelope on Apr 28, 2021

print("found ans")

Source: purdue.brightspace.com

Add Comment