retagged by
2,059 views

2 Answers

Best answer
8 votes
8 votes

Here is Depth First Traversal Algorithm

// Consoder Graph G(V.E)

Bool Visited[V] = {False};

DFT(V,E){
    for each vertex v, element of V do
        if(!(visited[v]))
            DFS(v);
}

DFS(v){
    visited[v] = True;
    for each vertex w adjacent to v do
        if(!(visited[w]))
            DFS(w);
}

Here is the Depth First Search Algorithm,

//Consider Graph G(V,E)

Bool visited[V] = {False};

DFS(v){        // Take V as startig vertex
    visited[v] = True;
    for each vertex w adjacent to v do
        if(!(visited[w]))
            DFS(w);
}

Now observe the difference. 

1) DFT is a a traversal which usually applied on the disconnected Graph. While DFS is an algorithm which is applied on the connected graph. 

2) DFS did not gurantee that it will visit each and every node while DFT do. 

3) DFT uses DFS. 

==> Both uses stack and Visited array, as you have asked. 

P.S. I have read this in DAA notes by ACE. Posted in Facebook Group. 

selected by
2 votes
2 votes

No both are same .

Depth first search is a way of traversing graphs or tree, which is closely related to preorder traversal of a tree. Preorder traversal simply visits each node before its children. It is most easy to program as a recursive routine:

You can check what is  Depth First Search .

Related questions

0 votes
0 votes
0 answers
1
saumya mishra asked Sep 25, 2017
279 views
What is the correct answer please provide with reason?
5 votes
5 votes
3 answers
3
Kapil asked Jan 24, 2017
3,355 views
It may be the case that "Kruskal's Algorithm may not maintain connectivity while Prim's algorithm always does that" ?Any example which favours this ?
4 votes
4 votes
2 answers
4
lowOnATP asked Jun 29, 2015
2,542 views
I mean if we run prim's algorithm on a weighted directed graph, will it give the same shortest path? And vice-versa?Also if we run dijkstra's algorithm on a graph with ne...