C++

Forum

 
Depth First & Breadth First Search Program

scocuzza (11)
This is what i have so far, i have the areas commented where I need help
im not sure how to have to user input numbers into a tree and to have it print out the steps it takes to reach the goal
Header File

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
#include <iostream>
#include <stack>
using namespace std;

bool recursive_depth(int);
bool is_goal(int);
void input_tree();
void print_tree(); 

int goal;
int root_node;
int const NUM_SUCC = 4;

int tree[NUM_SUCC][4]; 

stack<int> mystack; 



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
 
#include "search.h"

void main()
{
	int state;
	//input your tree and goal state, start state
	//call recursive  
	input_tree(); 
	recursive_depth(state);
	print_tree(); 
	
}

 bool is_goal(int state)
 {
	 state = root_node; 
	 if (state == goal)  {
		 return true; 
	 }else{
		 return false;
	}
 }

bool recursive_depth(int state)
{
	cout<<state<<" " << endl;
	if (is_goal(state)) {
		cout<<"goal found\n" << endl;
		return true;
	}
	else{

		if(!mystack.empty()){
			int temp = mystack.top();
			mystack.pop();
			
		}
		for(int i = (NUM_SUCC-1); i>=0; i--)
	 {
		 if (tree[state][i]!=0)
		 {
			 mystack.push(i);
		 }
		}
	}
	while (!mystack.empty())
	{
//i dont know what to put in this function the below code isnt right
		mystack.pop(); 
		state++; 
		recursive_depth(state);  
	}
	return false;
}

	void print_tree() { 
//im not sure how to print the tree

	}

	void input_tree() {
	{
	cout << "Input the root_node (start as 0)" << endl; 
	cin >> root_node;   
	cout << "Input the goal state " << endl; 
	cin >> goal;
	//i ask for goal and root node but i have no idea how to have the user input the tree

	
	}
scocuzza (11)
bump
Smac89 (1727)
Not sure why you need a separate function just to compare 2 numbers, when simply doing if (a == b) { ... } will suffice.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
//i ask for goal and root node but i have no idea how to have the user input the tree

for (int row = 0; row < NUM_SUCC; row++) {
    for (int col = 0; col < NUM_SUCC; col++) {
        cin >> tree[row][col];
    }
}



//im not sure how to print the tree

for (int row = 0; row < NUM_SUCC; row++) {
    for (int col = 0; col < NUM_SUCC; col++) {
        cout << tree[row][col] << ' ';
    }
    cout << endl;
}



As for the rest of your code, I'm not sure what you are trying to accomplish. Is this a game tree you are building? If so, what algorithm are you trying to implement? I am guessing something like A*? But I'm not sure
scocuzza (11)
the goals of my program are

implement depth first search using recursion


1)write a function called bool is_goal() which takes a state and determines whether the state is a goal or not. The function should return true if the state is a goal, and false otherwise

2) represent the binary tree using a two dimensional array

3) write a function for inputting the array representation and another for printing

4) use a stack to implement the recursive depth-first function

5) have the program output the states in order they are visited until the goal state is reached
Last edited on
Smac89 (1727)
Again, what is the purpose of this? All these steps you have mentioned can be written without a goal in mind. What is your program supposed to do?

Assuming this is a game tree you are trying to build, the last step can be implemented by placing a parent pointer in each node. When the goal node is found, you can trace back to the parent by visiting the current node's parent and so forth.
Topic archived. No new replies allowed.