Answers for "Implementation of Depth First Search"

dfs python

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

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);
}