#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();
}
In order traversal is used.
n-k-1
By using Depth First Search or Breadth First search Tree traversal algorithm we can print data in Binary search tree.
Refer to the following code and example output below. #include<iostream> #include<time.h> #include<queue> #include<stack> 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 < data) { if (!left) left = new node (num, depth+1); else left->insert (num); } else { if (!right) right = new node (num, depth+1); else right->insert (num); } } void print () { std::cout<<"ID: "<<id<<" Depth: "<<depth<<" Data: "<<data<<std::endl; } void print_sorted () { if (left) left->print_sorted (); print(); if (right) right->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->insert (num); } void print_sorted () { std::cout<<"Sorted-order traversal\n"<<std::endl; if (m_root) { m_root->print_sorted (); std::cout<<std::endl; } } void print_breadth_first () { std::cout<<"Breadth-first traversal\n"<<std::endl; std::queue<node*> 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->print (); // enqueue left and right nodes if (n->left) q.push (n->left); if (n->right) q.push (n->right); } std::cout<<std::endl; } else std::cout<<"The tree is empty!\n"<<std::endl; } void print_depth_first () { std::cout<<"Depth-first traversal\n"<<std::endl; std::stack<node*> 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->print (); // stack left and right nodes if (n->right) s.push (n->right); if (n->left) s.push (n->left); } std::cout<<std::endl; } else std::cout<<"The tree is empty!\n"<<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<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.
advantages of depth first search?
In order traversal is used.
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.....
n-k-1
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.
Security dollars are invested in a single solution
A concerted attack by land sea and air.
By using Depth First Search or Breadth First search Tree traversal algorithm we can print data in Binary search tree.
Refer to the following code and example output below. #include<iostream> #include<time.h> #include<queue> #include<stack> 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 < data) { if (!left) left = new node (num, depth+1); else left->insert (num); } else { if (!right) right = new node (num, depth+1); else right->insert (num); } } void print () { std::cout<<"ID: "<<id<<" Depth: "<<depth<<" Data: "<<data<<std::endl; } void print_sorted () { if (left) left->print_sorted (); print(); if (right) right->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->insert (num); } void print_sorted () { std::cout<<"Sorted-order traversal\n"<<std::endl; if (m_root) { m_root->print_sorted (); std::cout<<std::endl; } } void print_breadth_first () { std::cout<<"Breadth-first traversal\n"<<std::endl; std::queue<node*> 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->print (); // enqueue left and right nodes if (n->left) q.push (n->left); if (n->right) q.push (n->right); } std::cout<<std::endl; } else std::cout<<"The tree is empty!\n"<<std::endl; } void print_depth_first () { std::cout<<"Depth-first traversal\n"<<std::endl; std::stack<node*> 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->print (); // stack left and right nodes if (n->right) s.push (n->right); if (n->left) s.push (n->left); } std::cout<<std::endl; } else std::cout<<"The tree is empty!\n"<<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<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.
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.
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.
tell me , how we create a username & password for many users in c language.
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.