oop/Graphs/Graphs/GraphAlgo.cpp

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

using namespace std;

bool DFS::connected(GraphNode* begin, GraphNode* end) {
	visited.clear(); return connected(begin, end, 0);
}
bool DFS::connected(GraphNode* begin, GraphNode* 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(GraphNode* begin, GraphNode* end) {
	deque <GraphNode*> nodes;
	nodes.push_back(begin);
	set<GraphNode*> visited;
	while (!nodes.empty()) {
		GraphNode* 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;
}