#include "graph.h"
#include <queue>

using namespace std;

bool DFS::connected(Node* begin, Node* end) {
	visited.clear(); return connected(begin, end, 0);
}
bool DFS::connected(Node* begin, Node* end, int depth) {
	if (begin == end) return true;
	visited.insert(begin);
	for (node_iterator it = begin->nb_begin();
		it != begin->nb_end(); it++) {
		if (visited.find(*it) == visited.end()) {
			if (connected(*it, end, depth + 1)) return true;
		}
	}
	return false;
}


bool BFS::connected(Node* begin, Node* end) {
	deque <Node*> nodes; 
	nodes.push_back(begin);
	set<Node*> visited;
	while (!nodes.empty()) {
		Node* next = nodes.front(); nodes.pop_front();
		if (end == next) return true;
		visited.insert(next);
		for (node_iterator it = next->nb_begin();
			it != next->nb_end(); it++)
			if (visited.find(*it) == visited.end())
				nodes.push_back(*it);
	}
	return false;
}