Depth First Search

Write a program to implement a depth-first search.

Example 1:

Input: n=6,edges={{1,2},{1,3},{2,4},{4,5},{4,6}}
Output: 1 2 4 5 6 3

Approach:

Java

import java.util.ArrayList;

public class DepthFirstSearch {

    // visited list
    public static ArrayList<Integer> visited = new ArrayList<>();
    // traversal list
    public static ArrayList<Integer> ans = new ArrayList<>();

    public static void main(String[] args) {
        // Adjacency Lists
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        int v = 7;
        for (int i = 0; i < v; i++)
            adj.add(new ArrayList<>());

        addEdge(adj, 1, 2);
        addEdge(adj, 1, 3);
        addEdge(adj, 2, 4);
        addEdge(adj, 4, 5);
        addEdge(adj, 4, 6);
        int source = 1;
// dfs calling
        DFSTraversal(adj, source);
        // print traversal list
        ans.forEach(i -> System.out.print(i + " "));
    }

    private static void DFSTraversal(ArrayList<ArrayList<Integer>> g, Integer start) {
        // set element as visited
        visited.add(start);
        // add element in traversal list
        ans.add(start);

        for (int i : g.get(start)) {
            // if not visited then call dfs
            if (visited.indexOf(i) == -1) {
                DFSTraversal(g, i);
            }

        }
    }

    private static void addEdge(ArrayList<ArrayList<Integer>> g, int i, int j) {
        // undirected graph
        g.get(i).add(j);
        g.get(j).add(i);
    }
}
//Time Complexity: O(n+m)
//where n=no of nodes,m=no of edges

C++

#include <bits/stdc++.h>
using namespace std;
//adjacency list
vector<int> adj[1001];
//visited array to hold
//which node is visit and which
//is not
bool visited[100001];
//function to add the edge
//into the adjacency list
void addEdge(int u,int v)
{
    //undirected graph
    adj[u].push_back(v);
    adj[v].push_back(u);
}
//function to find DFS traversal of
//a graph
void dfsTraversal(int node)
{
    //mark the current node as
    //visited
    visited[node]=1;
    //print the current node
    cout<<node<<" ";
    //iterate through adjacency list
    //of the current node
    for(int child:adj[node])
     {
         //if node visited then call the 
         //dfs for it
         if(visited[child]==0)
           {
               dfsTraversal(child);
           }
     }
}
int main()
{
     int node=6;
     int edges=5;
     addEdge(1,2);
     addEdge(1,3);
     addEdge(2,4);
     addEdge(4,5);
     addEdge(4,6);
     int source=1;
     cout<<"DFS Traversal is ";
     dfsTraversal(source);
     return 0;
}
//Time Complexity: O(n+m)
//where n=no of nodes,m=no of edges