Используя указатели и ссылки, не могу понять, почему DFS повторяется бесконечно
Я пытаюсь реализовать простую DFS на ориентированном графе, используя домашние структуры данных (HashMap и LinkedList) для изучения C ++, но по какой-то причине метод DFS бесконечно повторяется.
Я думаю, что это бесконечно повторяющееся, потому что по какой-то причине узлы, хранящиеся в хэш-карте (графике), на самом деле не отмечаются как посещенные во время DFS. Я думал, что понял указатели и ссылки, но, видимо, я не понимаю. Буду признателен, если кто-нибудь поможет мне понять, что я делаю не так.
Вот бесконечно повторяющийся метод DFS:
template <class T>
bool Graph<T>::DFS(const T& v1, const T& v2) {
if(v1 == v2)
return true;
Graph<T>::Node * node = *(map->find(v1));
node->visited = true;
for(int i = 0; i < node->adjacent->size(); i++)
if(node->adjacent->get(i).visited == false)
return DFS(node->adjacent->get(i).data, v2);
return false;
}
Вот класс HashMap метод find ()
template <class K, class V>
V* HashMap<K, V>::find(const K& key) const {
int bucket = (int) hash_fn(key) % arrLength;
HashMap<K, V>::Node * temp = buckets[bucket];
while(temp != NULL && temp->key != key)
temp = temp->next;
if(temp == NULL)
return NULL;
else
return &(temp->value);
}
Вот класс Graph
template <class T>
class Graph {
struct Node {
T data;
bool visited;
LinkedList<Node> * adjacent;
Node() {
adjacent = nullptr;
visited = false;
}
Node(T data) {
this->data = data;
adjacent = new LinkedList<Node>();
visited = false;
}
};
public:
Graph();
~Graph();
void addEdge(const T& v1, const T& v2);
bool DFS(const T& v1, const T& v2);
private:
HashMap<T, Graph<T>::Node*> * map;
};
template <class T>
Graph<T>::Graph() {
map = new HashMap<T, Graph<T>::Node*>();
}
template <class T>
Graph<T>::~Graph() {
map->~Map<T, Graph<T>::Node*>();
}
template <class T> // directed graph
void Graph<T>::addEdge(const T& v1, const T& v2) { // add edge from v1 to v2
if(map->find(v1) == NULL)
map->insert(v1, new Graph<T>::Node(v1));
if(map->find(v2) == NULL)
map->insert(v2, new Graph<T>::Node(v2));
(*map->find(v1))->adjacent->append( **map->find(v2) ); // oh god
}
Вот метод Main, где я создаю и заполняю график, а затем вызываю метод DFS.
int main() {
Graph<int> * graph1 = new Graph<int>();
graph1->addEdge(1, 5);
graph1->addEdge(5, 9);
graph1->addEdge(9, 20);
graph1->DFS(1, 20);
return 0;
}
Заранее спасибо за любую помощь или понимание.
-Bob
Решение
Во всяком случае, использование указателей выглядит почти случайным и произвольным. У вас есть указатели, где они не имеют смысла: HashMap<T, Graph<T>::Node*>и отсутствие указателей там, где должно быть: LinkedList<Node> * adjacent,
Вы также используете динамическое размещение в местах, которые не имеют смысла, например adjacent член Nodeи ваша очистка либо не существует (Graph::Node не имеет деструктора, когда он должен быть один), или полностью сломан (Graph<T>::~Graph() приведет к гарантированной утечке памяти).
Кроме того, ничто никогда не очищает ваш visited флаг, поэтому будет работать только один вызов DFS.
Проще говоря, существует много проблем с вашим кодом, как с точки зрения дизайна, так и с точки зрения реализации.
Ваша конкретная проблема DFS, вероятно, происходит от использования LinkedList<Node> вместо LinkedList<Node*> для списка смежности, потому что это, вероятно, приводит к тому, что граф становится массивным DAG с подграфами, скопированными в список смежности, но трудно сказать, не зная, как LinkedList<> реализовано.
редактировать Я чувствую себя немного плохо, просто прямо говоря «это плохо для всех», вот как я правильно реализовал ваш код (используя stl вместо ваших пользовательских контейнеров):
#include <unordered_map>
#include <vector>
template<typename T>
class Graph {
struct Node {
T data;
bool visited;
std::vector<Node*> adjacent;
Node(T const& d) : data(d), visited(false) {}
};
public:
inline void addEdge(T const& v1, T const& v2);
inline bool DFS(T const& v1, T const& v2);
private:
inline bool DFS_recur(T const& v1, T const& v2);
std::unordered_map<T, Node> map;
};
template<typename T>
void Graph<T>::addEdge(T const& v1, T const& v2) {
auto v1_found = map.emplace(v1, v1).first;
auto v2_found = map.emplace(v2, v2).first;
v1_found->second.adjacent.emplace_back(&v2_found->second);
}
template<typename T>
bool Graph<T>::DFS(T const& v1, T const& v2) {
auto result = DFS_recur(v1, v2);
// Return to the invariant state.
for(auto & n : map) {
n.second.visited = false;
}
return result;
}
template<typename T>
bool Graph<T>::DFS_recur(T const& v1, T const& v2) {
if(v1 == v2) return true;
auto v1_found = map.find(v1);
// If v1 is not in the map, we'll be in trouble.
if(v1_found == map.end()) return false;
v1_found->second.visited = true;
for(auto const & neighbour : v1_found->second.adjacent) {
if(!neighbour->visited) {
return DFS_recur(neighbour->data, v2);
}
}
return false;
}
int main() {
Graph<int> graph1;
graph1.addEdge(1, 5);
graph1.addEdge(5, 9);
graph1.addEdge(9, 20);
graph1.DFS(1, 20);
return 0;
}
Обратите внимание, как все управление памятью обрабатывается через RAII, а не new или же delete в поле зрения.
Другие решения
Других решений пока нет …