answersLogoWhite

0

#include <iostream.h>

#include <conio.h>

class graph

{

private:int n;

int **a;

int *reach;

int *pos;

public:graph(int k=10);

void create();

void dfs();

void dfs(int v,int label);

int begin(int v);

int nextvert(int v);

};

void graph::graph(int k)

{

n=k;

a=new int *[n+1];

reach=new int[n+1];

pos=new int [n+1];

for(int i=1;i<=n;i++)

pos[i]=0;

for(int j=1;j<=n;j++)

a[j]=new int[n+1];

}

void graph::create()

{

for(int i=1;i<=n;i++)

{

cout<<"Enter the "<<i<<"th row of matrix a:

";

for(int j=1;j<=n;j++)

cin>>a[i][j];

}

for(int k=1;k<=n;k++)

reach[k]=0;

}

void graph::dfs()

{

int label=0;

for(int i=1;i<=n;i++)

if(!reach[i])

{

label++;

dfs(i,label);

}

cout<<"

The contents of the reach array is:

;

for(int j=1;j<=n;j++)

cout<<reach[j]<<" ";

}

void graph::dfs(int v,int label)

{

cout<<v<<" ";

reach[v]=label;

int u=begin(v);

while(u)

{

if(!reach[u])

dfs(u,label);

u=nextvert(v);

}

}

int graph::begin(int v)

{

if((v<1)&&(v>n))

cout<<"Bad input

";

else

for(int i=1;i<=n;i++)

if(a[v][i]==1)

{

pos[v]=i;

return i;

}

return 0;

}

int graph::nextvert(int v)

{

if((v<1)&&(v>n))

cout<<"Bad input

";

else

for(int i=pos[v]+1;i<=n;i++)

if(a[v][i]==1)

{

pos[v]=i;

return i;

}

return 0;

}

void main()

{

clrscr();

int x;

cout<<"Enter the no of vertices:

";

cin>>x;

graph g(x);

g.create();

cout<<"dfs is.....";

g.dfs();

getch();

}

User Avatar

Wiki User

12y ago

What else can I help you with?

Continue Learning about Engineering

Which of the following traversal is used for printing the keys of binary search tree in ascending order?

In order traversal is used.


In depth first traversal of a graph G with n vertices k edges are marked as tree edges the no of connected components in G is?

n-k-1


How do you print all data in a Binary Search Tree?

By using Depth First Search or Breadth First search Tree traversal algorithm we can print data in Binary search tree.


With the help of a program explain the depth first traversal of a tree?

Refer to the following code and example output below. #include&lt;iostream&gt; #include&lt;time.h&gt; #include&lt;queue&gt; #include&lt;stack&gt; class tree { private: struct node { static unsigned s_id; // static id unsigned id; // instance id unsigned data; // instance data unsigned depth; // depth of node node* left; // pointer to left node (may be NULL) node* right; // pointer to right node (may be NULL) node (unsigned num, unsigned depth): data (num), left (NULL), right (NULL), id (s_id++), depth (depth) {} ~node () { delete (left); delete (right); } void insert (unsigned num) { if (num &lt; data) { if (!left) left = new node (num, depth+1); else left-&gt;insert (num); } else { if (!right) right = new node (num, depth+1); else right-&gt;insert (num); } } void print () { std::cout&lt;&lt;"ID: "&lt;&lt;id&lt;&lt;" Depth: "&lt;&lt;depth&lt;&lt;" Data: "&lt;&lt;data&lt;&lt;std::endl; } void print_sorted () { if (left) left-&gt;print_sorted (); print(); if (right) right-&gt;print_sorted (); } }; node* m_root; public: tree (): m_root (NULL) {} ~tree (){ delete (m_root); } void insert (unsigned num) { if (!m_root) m_root = new node (num, 0); else m_root-&gt;insert (num); } void print_sorted () { std::cout&lt;&lt;"Sorted-order traversal\n"&lt;&lt;std::endl; if (m_root) { m_root-&gt;print_sorted (); std::cout&lt;&lt;std::endl; } } void print_breadth_first () { std::cout&lt;&lt;"Breadth-first traversal\n"&lt;&lt;std::endl; std::queue&lt;node*&gt; q; if (m_root) { // enque the root q.push (m_root); // repeat while the queue is not empty while (!q.empty ()) { // dequeue the first node node* n = q.front (); q.pop (); // report the node n-&gt;print (); // enqueue left and right nodes if (n-&gt;left) q.push (n-&gt;left); if (n-&gt;right) q.push (n-&gt;right); } std::cout&lt;&lt;std::endl; } else std::cout&lt;&lt;"The tree is empty!\n"&lt;&lt;std::endl; } void print_depth_first () { std::cout&lt;&lt;"Depth-first traversal\n"&lt;&lt;std::endl; std::stack&lt;node*&gt; s; if (m_root) { // stack the root s.push (m_root); // repeat while the stack is not empty while (!s.empty()) { // unstack the top node node* n = s.top (); s.pop (); // report the node n-&gt;print (); // stack left and right nodes if (n-&gt;right) s.push (n-&gt;right); if (n-&gt;left) s.push (n-&gt;left); } std::cout&lt;&lt;std::endl; } else std::cout&lt;&lt;"The tree is empty!\n"&lt;&lt;std::endl; } }; // initialise static data unsigned tree::node::s_id = 0; int main() { srand((unsigned) time(NULL)); // create tree with 10 random numbers tree t; for(unsigned i=0; i&lt;10; ++i) t.insert (rand ()); t.print_sorted (); t.print_breadth_first (); t.print_depth_first (); } Example output: Sorted-order traversal ID: 6 Depth: 2 Data: 334 ID: 4 Depth: 1 Data: 2335 ID: 0 Depth: 0 Data: 12490 ID: 5 Depth: 4 Data: 15590 ID: 9 Depth: 5 Data: 18484 ID: 3 Depth: 3 Data: 23160 ID: 2 Depth: 2 Data: 23786 ID: 8 Depth: 3 Data: 24171 ID: 1 Depth: 1 Data: 24598 ID: 7 Depth: 2 Data: 30731 Breadth-first traversal ID: 0 Depth: 0 Data: 12490 ID: 4 Depth: 1 Data: 2335 ID: 1 Depth: 1 Data: 24598 ID: 6 Depth: 2 Data: 334 ID: 2 Depth: 2 Data: 23786 ID: 7 Depth: 2 Data: 30731 ID: 3 Depth: 3 Data: 23160 ID: 8 Depth: 3 Data: 24171 ID: 5 Depth: 4 Data: 15590 ID: 9 Depth: 5 Data: 18484 Depth-first traversal ID: 0 Depth: 0 Data: 12490 ID: 4 Depth: 1 Data: 2335 ID: 6 Depth: 2 Data: 334 ID: 1 Depth: 1 Data: 24598 ID: 2 Depth: 2 Data: 23786 ID: 3 Depth: 3 Data: 23160 ID: 5 Depth: 4 Data: 15590 ID: 9 Depth: 5 Data: 18484 ID: 8 Depth: 3 Data: 24171 ID: 7 Depth: 2 Data: 30731 Each node reports its ID, depth and data. The ID tells us the sequence the nodes were created, where the node with ID 0 is always the root. The depth tells us the level within the tree where the node exists, such that the root is on level 0. With this information it is possible to draw a graph of the tree and thus better understand the order in which nodes are processed. The first listing shows the nodes in ascending order by data. With binary search trees this is the normal method of traversal. The second listing shows a breadth-first traversal, where each level is processed in turn, from left to right. The final listing shows a depth-first traversal where we follow left nodes before right nodes. You will notice that the implementation of breadth-first and depth-first are fairly similar, the only real difference being that breadth-first employs a queue while depth-first employs a stack. The nature of a stack also means we must push right nodes before left nodes to ensure left nodes are processed before right nodes. At first glance there doesn't appear to be much merit in either breadth-first or depth-first traversal. However, the example merely serves to show the difference between all the methods of traversal. When considering more complex graphs or maps, it may be advantageous to search through all the vertices that form an edge with a particular vertex (breadth-first) or to examine all the edges between one vertex and another vertex, where several routes might be available (depth-first). Both depth-first and breadth-first have practical applications in network routing and satellite navigation, where maps and charts must be graphed and traversed in a more logical manner than would otherwise be possible with sorted-order traversal.


What is the advantages of depth first search?

advantages of depth first search?

Related Questions

Which of the following traversal is used for printing the keys of binary search tree in ascending order?

In order traversal is used.


What is the difference between height and depth of a tree?

height and depth of a tree is equal... but height and depth of a node is not equal because... the height is calculated by traversing from leaf to the given node depth is calculated from traversal from root to the given node.....


In depth first traversal of a graph G with n vertices k edges are marked as tree edges the no of connected components in G is?

n-k-1


What do you do in a PhD program?

In a PhD program, you conduct in-depth research on a specific topic, write a dissertation based on your findings, and defend your work in front of a panel of experts to earn a doctoral degree.


Which would not be a reason to implement Defense in Depth?

Security dollars are invested in a single solution


What would be a reason to implement defence in depth?

A concerted attack by land sea and air.


How do you print all data in a Binary Search Tree?

By using Depth First Search or Breadth First search Tree traversal algorithm we can print data in Binary search tree.


With the help of a program explain the depth first traversal of a tree?

Refer to the following code and example output below. #include&lt;iostream&gt; #include&lt;time.h&gt; #include&lt;queue&gt; #include&lt;stack&gt; class tree { private: struct node { static unsigned s_id; // static id unsigned id; // instance id unsigned data; // instance data unsigned depth; // depth of node node* left; // pointer to left node (may be NULL) node* right; // pointer to right node (may be NULL) node (unsigned num, unsigned depth): data (num), left (NULL), right (NULL), id (s_id++), depth (depth) {} ~node () { delete (left); delete (right); } void insert (unsigned num) { if (num &lt; data) { if (!left) left = new node (num, depth+1); else left-&gt;insert (num); } else { if (!right) right = new node (num, depth+1); else right-&gt;insert (num); } } void print () { std::cout&lt;&lt;"ID: "&lt;&lt;id&lt;&lt;" Depth: "&lt;&lt;depth&lt;&lt;" Data: "&lt;&lt;data&lt;&lt;std::endl; } void print_sorted () { if (left) left-&gt;print_sorted (); print(); if (right) right-&gt;print_sorted (); } }; node* m_root; public: tree (): m_root (NULL) {} ~tree (){ delete (m_root); } void insert (unsigned num) { if (!m_root) m_root = new node (num, 0); else m_root-&gt;insert (num); } void print_sorted () { std::cout&lt;&lt;"Sorted-order traversal\n"&lt;&lt;std::endl; if (m_root) { m_root-&gt;print_sorted (); std::cout&lt;&lt;std::endl; } } void print_breadth_first () { std::cout&lt;&lt;"Breadth-first traversal\n"&lt;&lt;std::endl; std::queue&lt;node*&gt; q; if (m_root) { // enque the root q.push (m_root); // repeat while the queue is not empty while (!q.empty ()) { // dequeue the first node node* n = q.front (); q.pop (); // report the node n-&gt;print (); // enqueue left and right nodes if (n-&gt;left) q.push (n-&gt;left); if (n-&gt;right) q.push (n-&gt;right); } std::cout&lt;&lt;std::endl; } else std::cout&lt;&lt;"The tree is empty!\n"&lt;&lt;std::endl; } void print_depth_first () { std::cout&lt;&lt;"Depth-first traversal\n"&lt;&lt;std::endl; std::stack&lt;node*&gt; s; if (m_root) { // stack the root s.push (m_root); // repeat while the stack is not empty while (!s.empty()) { // unstack the top node node* n = s.top (); s.pop (); // report the node n-&gt;print (); // stack left and right nodes if (n-&gt;right) s.push (n-&gt;right); if (n-&gt;left) s.push (n-&gt;left); } std::cout&lt;&lt;std::endl; } else std::cout&lt;&lt;"The tree is empty!\n"&lt;&lt;std::endl; } }; // initialise static data unsigned tree::node::s_id = 0; int main() { srand((unsigned) time(NULL)); // create tree with 10 random numbers tree t; for(unsigned i=0; i&lt;10; ++i) t.insert (rand ()); t.print_sorted (); t.print_breadth_first (); t.print_depth_first (); } Example output: Sorted-order traversal ID: 6 Depth: 2 Data: 334 ID: 4 Depth: 1 Data: 2335 ID: 0 Depth: 0 Data: 12490 ID: 5 Depth: 4 Data: 15590 ID: 9 Depth: 5 Data: 18484 ID: 3 Depth: 3 Data: 23160 ID: 2 Depth: 2 Data: 23786 ID: 8 Depth: 3 Data: 24171 ID: 1 Depth: 1 Data: 24598 ID: 7 Depth: 2 Data: 30731 Breadth-first traversal ID: 0 Depth: 0 Data: 12490 ID: 4 Depth: 1 Data: 2335 ID: 1 Depth: 1 Data: 24598 ID: 6 Depth: 2 Data: 334 ID: 2 Depth: 2 Data: 23786 ID: 7 Depth: 2 Data: 30731 ID: 3 Depth: 3 Data: 23160 ID: 8 Depth: 3 Data: 24171 ID: 5 Depth: 4 Data: 15590 ID: 9 Depth: 5 Data: 18484 Depth-first traversal ID: 0 Depth: 0 Data: 12490 ID: 4 Depth: 1 Data: 2335 ID: 6 Depth: 2 Data: 334 ID: 1 Depth: 1 Data: 24598 ID: 2 Depth: 2 Data: 23786 ID: 3 Depth: 3 Data: 23160 ID: 5 Depth: 4 Data: 15590 ID: 9 Depth: 5 Data: 18484 ID: 8 Depth: 3 Data: 24171 ID: 7 Depth: 2 Data: 30731 Each node reports its ID, depth and data. The ID tells us the sequence the nodes were created, where the node with ID 0 is always the root. The depth tells us the level within the tree where the node exists, such that the root is on level 0. With this information it is possible to draw a graph of the tree and thus better understand the order in which nodes are processed. The first listing shows the nodes in ascending order by data. With binary search trees this is the normal method of traversal. The second listing shows a breadth-first traversal, where each level is processed in turn, from left to right. The final listing shows a depth-first traversal where we follow left nodes before right nodes. You will notice that the implementation of breadth-first and depth-first are fairly similar, the only real difference being that breadth-first employs a queue while depth-first employs a stack. The nature of a stack also means we must push right nodes before left nodes to ensure left nodes are processed before right nodes. At first glance there doesn't appear to be much merit in either breadth-first or depth-first traversal. However, the example merely serves to show the difference between all the methods of traversal. When considering more complex graphs or maps, it may be advantageous to search through all the vertices that form an edge with a particular vertex (breadth-first) or to examine all the edges between one vertex and another vertex, where several routes might be available (depth-first). Both depth-first and breadth-first have practical applications in network routing and satellite navigation, where maps and charts must be graphed and traversed in a more logical manner than would otherwise be possible with sorted-order traversal.


What is hard-disk queue depth?

The queue depth is the amount of outstanding read and/or write requests waiting to access the hard drive. hard-disk queue depth is the time it take a Hard drive in a piece of a electronic device (ex; A Desktop compter) to process a program without freezing or locking up.


What is hard disk queue depth?

The queue depth is the amount of outstanding read and/or write requests waiting to access the hard drive. hard-disk queue depth is the time it take a Hard drive in a piece of a electronic device (ex; A Desktop compter) to process a program without freezing or locking up.


Write a program in C programming language to list the nodes of a binary tree in the following way List the root then nodes at depth 1 followed by nodes at depth 2 and so on?

tell me , how we create a username &amp; password for many users in c language.


What is the difference between backtracking and depth-first search (DFS) in terms of their approach to problem-solving?

Backtracking is a general algorithmic technique that involves systematically trying all possible solutions to find the correct one, while depth-first search (DFS) is a specific graph traversal algorithm that explores as far as possible along each branch before backtracking. In essence, backtracking is a broader concept that can be used in various problem-solving scenarios, while DFS is a specific application of backtracking in graph traversal.