Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- void Graph::IDS(int x, int required, int depth = 1)
- {
- if(x == required) return;
- cout << "Iterated Deepening Search for " << required << ", starting from vertex " << x << " : " << endl;
- IDS_util(x, required, depth);
- cout << endl;
- }
- void Graph::IDS_util(int x, int required, int depth)
- {
- stack s;
- bool *visited = new bool[n+1];
- int i, j, k;
- for(i = 0; i <= n; i++)
- visited[i] = false;
- cout << "Depth = " << depth << ": ";
- visited[x] = true;
- for (int c = 1; c <= n; c++){
- s.push(x);
- if(isConnected(x, c) && !visited[c])
- {
- for (j = 0; j < depth; j++){
- k = s.pop();
- if(k == required) return;
- cout << "[" << k <<"] ";
- for (i = n; i >= 0 ; --i)
- if (isConnected(k, i) && !visited[i]) {
- s.push(i);
- visited[i] = true;
- }
- }
- }
- }
- if(depth == n) return;
- cout << endl;
- IDS_util(x, required, depth+1);
- }
- 0,1,1,1,0,0,0,0,0
- 0,0,0,0,1,0,0,0,0
- 0,0,0,0,0,1,1,0,0
- 0,0,0,0,0,0,0,1,0
- 0,0,0,0,0,0,0,0,1
- 0,0,0,0,0,0,0,0,0
- 0,0,0,0,0,0,0,0,0
- 0,0,0,0,0,0,0,0,0
- 0,0,0,0,0,0,0,0,0
- [1]
- / |
- [2] [3] [4]
- / /
- [5] [6] [7] [8]
- /
- [9]
- Iterated Deepening Search for 7, starting from vertex 1 :
- Depth = 0:
- Depth = 1: [1]
- Depth = 2: [1] [2]
- Depth = 3: [1] [2] [5]
- Depth = 4: [1] [2] [5] [9]
- Depth = 5: [1] [2] [5] [9] [3]
- Depth = 6: [1] [2] [5] [9] [3] [6]
- Depth = 7: [1] [2] [5] [9] [3] [6]
- void Graph::IDS(int x, int required)
- {
- if(x == required) return;
- cout << "Iterated Deepening Search for " << required << ", starting from vertex " << x << " : " << endl;
- for (int d = 0 ; d <= n ; d++)
- if (IDS_util(x, required, d))
- return;
- cout << required << " was unable to be located via " << x << endl;
- }
- bool Graph::IDS_util(int x, int required, int depth){
- if(x == required) return true;
- stack s, x_child;
- bool *visited = new bool[n+1];
- int i,k, d, sub_k;
- for(i = 0; i <= n; i++) visited[i] = false;
- visited[x] = true;
- for (i = n; i >= 0 ; --i)
- if (isConnected(x, i))
- x_child.push(i);
- cout << '[' << x << "] ";
- while(!x_child.isEmpty()){
- k = x_child.pop();
- s.push(k);
- for(d = 0; d < depth; d++){
- sub_k = s.pop();
- if(sub_k == required) return true;
- cout << '[' << sub_k << "] ";
- for (i = 0; i <= n; i++){
- if (isConnected(sub_k, i) && !visited[i]) {
- if (i == required){
- cout << "nn" << required << " is a child of " << sub_k << endl;
- return true;
- }
- s.push(i);
- visited[i] = true;
- }
- }
- }
- }
- cout<<endl;
- delete [] visited;
- return false;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement