Construct A New Tree Using Depth-First-Search

Depth First Traversal (or Search) for a graph is similar to Depth First Traversal of a tree. The only catch here is, unlike trees, graphs may contain cycles (a node may be visited twice). To avoid processing a node more than once, use a boolean visited array.

Example:

Attention reader! Don't stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer Complete Interview Preparation Course .

In case you wish to attend live classes with experts, please refer DSA Live Classes for Working Professionals and Competitive Programming Live for Students.

Input: n = 4, e = 6
0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 2 -> 3, 3 -> 3
Output: DFS from vertex 1 : 1 2 0 3
Explanation:
DFS Diagram:

Input: n = 4, e = 6
2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3
Output: DFS from vertex 2 : 2 0 1 3
Explanation:
DFS Diagram:

Prerequisites:
See this post for all applications of Depth First Traversal.

Approach:
Depth-first search is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking. So the basic idea is to start from the root or any arbitrary node and mark the node and move to the adjacent unmarked node and continue this loop until there is no unmarked adjacent node. Then backtrack and check for other unmarked nodes and traverse them. Finally, print the nodes in the path.

Algorithm:
Create a recursive function that takes the index of the node and a visited array.

Mark the current node as visited and print the node.
Traverse all the adjacent and unmarked nodes and call the recursive function with the index of the adjacent node.

Implementation:
Below are implementations of simple Depth First Traversal. The C++ implementation uses an adjacency list representation of graphs. STL's list container is used to store lists of adjacent nodes.

C++

#include <bits/stdc++.h>

using namespace std;

class Graph {

public :

map< int , bool > visited;

map< int , list< int > > adj;

void addEdge( int v, int w);

void DFS( int v);

};

void Graph::addEdge( int v, int w)

{

adj[v].push_back(w);

}

void Graph::DFS( int v)

{

visited[v] = true ;

cout << v << " " ;

list< int >::iterator i;

for (i = adj[v].begin(); i != adj[v].end(); ++i)

if (!visited[*i])

DFS(*i);

}

int main()

{

Graph g;

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;

}

Java

import java.io.*;

import java.util.*;

class Graph {

private int V;

private LinkedList<Integer> adj[];

@SuppressWarnings ( "unchecked" ) 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);

}

void DFSUtil( int v, boolean visited[])

{

visited[v] = true ;

System.out.print(v + " " );

Iterator<Integer> i = adj[v].listIterator();

while (i.hasNext()) {

int n = i.next();

if (!visited[n])

DFSUtil(n, visited);

}

void DFS( int v)

{

boolean visited[] = new boolean [V];

DFSUtil(v, visited);

}

public static void main(String args[])

{

Graph g = new Graph( 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 );

System.out.println(

"Following is Depth First Traversal "

+ "(starting from vertex 2)" );

g.DFS( 2 );

}

Python3

from collections import defaultdict

class Graph:

def __init__( self ):

self .graph = defaultdict( list )

def addEdge( self , u, v):

self .graph[u].append(v)

def DFSUtil( self , v, visited):

visited.add(v)

print (v, end = ' ' )

for neighbour in self .graph[v]:

if neighbour not in visited:

self .DFSUtil(neighbour, visited)

def DFS( self , v):

visited = set ()

self .DFSUtil(v, visited)

g = Graph()

g.addEdge( 0 , 1 )

g.addEdge( 0 , 2 )

g.addEdge( 1 , 2 )

g.addEdge( 2 , 0 )

g.addEdge( 2 , 3 )

g.addEdge( 3 , 3 )

print ( "Following is DFS from (starting from vertex 2)" )

g.DFS( 2 )

C#

using System;

using System.Collections.Generic;

class Graph {

private int V;

private List< int >[] adj;

Graph( int v)

{

V = v;

adj = new List< int >[ v ];

for ( int i = 0; i < v; ++i)

adj[i] = new List< int >();

}

void AddEdge( int v, int w)

{

adj[v].Add(w);

}

void DFSUtil( int v, bool [] visited)

{

visited[v] = true ;

Console.Write(v + " " );

List< int > vList = adj[v];

foreach ( var n in vList)

{

if (!visited[n])

DFSUtil(n, visited);

}

void DFS( int v)

{

bool [] visited = new bool [V];

DFSUtil(v, visited);

}

public static void Main(String[] args)

{

Graph g = new Graph(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);

Console.WriteLine(

"Following is Depth First Traversal "

+ "(starting from vertex 2)" );

g.DFS(2);

Console.ReadKey();

}

Javascript

<script>

class Graph

{

constructor(v)

{

this .V = v;

this .adj = new Array(v);

for (let i = 0; i < v; i++)

this .adj[i] = [];

}

addEdge(v, w)

{

this .adj[v].push(w);

}

DFSUtil(v, visited)

{

visited[v] = true ;

document.write(v + " " );

for (let i of this .adj[v].values())

{

let n = i

if (!visited[n])

this .DFSUtil(n, visited);

}

DFS(v)

{

let visited = new Array( this .V);

for (let i = 0; i < this .V; i++)

visited[i] = false ;

this .DFSUtil(v, visited);

}

g = new Graph(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);

document.write( "Following is Depth First Traversal " +

"(starting from vertex 2)<br>" );

g.DFS(2);

</script>

Output:

Following is Depth First Traversal (starting from vertex 2) 2 0 1 3

Complexity Analysis:

Time complexity: O(V + E), where V is the number of vertices and E is the number of edges in the graph.
Space Complexity: O(V), since an extra visited array of size V is required.

Handling A Disconnected Graph:

Solution:
This will happen by handling a corner case.
The above code traverses only the vertices reachable from a given source vertex. All the vertices may not be reachable from a given vertex, as in a Disconnected graph. To do a complete DFS traversal of such graphs, run DFS from all unvisited nodes after a DFS.
The recursive function remains the same.
Algorithm:
1. Create a recursive function that takes the index of the node and a visited array.
2. Mark the current node as visited and print the node.
3. Traverse all the adjacent and unmarked nodes and call the recursive function with the index of the adjacent node.
4. Run a loop from 0 to the number of vertices and check if the node is unvisited in the previous DFS, call the recursive function with the current node.

Implementation:

C++

#include <bits/stdc++.h>

using namespace std;

class Graph {

void DFSUtil( int v);

public :

map< int , bool > visited;

map< int , list< int > > adj;

void addEdge( int v, int w);

void DFS();

};

void Graph::addEdge( int v, int w)

{

adj[v].push_back(w);

}

void Graph::DFSUtil( int v)

{

visited[v] = true ;

cout << v << " " ;

list< int >::iterator i;

for (i = adj[v].begin(); i != adj[v].end(); ++i)

if (!visited[*i])

DFSUtil(*i);

}

void Graph::DFS()

{

for ( auto i : adj)

if (visited[i.first] == false )

DFSUtil(i.first);

}

int main()

{

Graph g;

g.addEdge(0, 1);

g.addEdge(0, 9);

g.addEdge(1, 2);

g.addEdge(2, 0);

g.addEdge(2, 3);

g.addEdge(9, 3);

cout << "Following is Depth First Traversal \n" ;

g.DFS();

return 0;

}

Java

import java.io.*;

import java.util.*;

class Graph {

private int V;

private LinkedList<Integer> adj[];

@SuppressWarnings ( "unchecked" ) 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);

}

void DFSUtil( int v, boolean visited[])

{

visited[v] = true ;

System.out.print(v + " " );

Iterator<Integer> i = adj[v].listIterator();

while (i.hasNext()) {

int n = i.next();

if (!visited[n])

DFSUtil(n, visited);

}

void DFS()

{

boolean visited[] = new boolean [V];

for ( int i = 0 ; i < V; ++i)

if (visited[i] == false )

DFSUtil(i, visited);

}

public static void main(String args[])

{

Graph g = new Graph( 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 );

System.out.println(

"Following is Depth First Traversal" );

g.DFS();

}

Python

from collections import defaultdict

class Graph:

def __init__( self ):

self .graph = defaultdict( list )

def addEdge( self , u, v):

self .graph[u].append(v)

def DFSUtil( self , v, visited):

visited.add(v)

print (v)

for neighbour in self .graph[v]:

if neighbour not in visited:

self .DFSUtil(neighbour, visited)

def DFS( self ):

visited = set ()

for vertex in self .graph:

if vertex not in visited:

self .DFSUtil(vertex, visited)

g = Graph()

g.addEdge( 0 , 1 )

g.addEdge( 0 , 2 )

g.addEdge( 1 , 2 )

g.addEdge( 2 , 0 )

g.addEdge( 2 , 3 )

g.addEdge( 3 , 3 )

g.DFS()

C#

using System;

using System.Collections.Generic;

public class Graph {

private int V;

private List< int >[] adj;

Graph( int v)

{

V = v;

adj = new List< int >[ v ];

for ( int i = 0; i < v; ++i)

adj[i] = new List< int >();

}

void addEdge( int v, int w)

{

adj[v].Add(w);

}

void DFSUtil( int v, bool [] visited)

{

visited[v] = true ;

Console.Write(v + " " );

foreach ( int i in adj[v])

{

int n = i;

if (!visited[n])

DFSUtil(n, visited);

}

void DFS()

{

bool [] visited = new bool [V];

for ( int i = 0; i < V; ++i)

if (visited[i] == false )

DFSUtil(i, visited);

}

public static void Main(String[] args)

{

Graph g = new Graph(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);

Console.WriteLine(

"Following is Depth First Traversal" );

g.DFS();

}

Javascript

<script>

class Graph

{

constructor(v) {

this .V = v;

this .adj = new Array(v).fill([]);

}

AddEdge(v, w) {

this .adj[v].push(w);

}

DFSUtil(v, visited)

{

visited[v] = true ;

document.write(v + " " );

for (const n of this .adj[v]) {

if (!visited[n]) this .DFSUtil(n, visited);

}

DFS()

{

var visited = new Array( this .V).fill( false );

for ( var i = 0; i < this .V; ++i)

if (visited[i] == false ) this .DFSUtil(i, visited);

}

var g = new Graph(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);

document.write( "Following is Depth First Traversal<br>" );

g.DFS();

</script>

Output:

Following is Depth First Traversal 0 1 2 3 9

Complexity Analysis:

Time complexity: O(V + E), where V is the number of vertices and E is the number of edges in the graph.
Space Complexity: O(V), since an extra visited array of size V is required.

https://youtu.be/Y40bRyPQQr0

Applications of DFS.
Breadth-First Traversal for a Graph
Recent Articles on DFS

Would you please write comments if you find anything incorrect or share more information about the topic discussed above?

Posted by: jameswharodsae.blogspot.com

Source: https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/

Construct A New Tree Using Depth-First-Search

C++

Java

Python3

C#

Javascript

C++

Java

Python

C#

Javascript

Posting Komentar

0 Komentar

JSON Variables

Popular Posts

Random Posts