Используя указатели и ссылки, не могу понять, почему DFS повторяется бесконечно

Question

Я пытаюсь реализовать простую 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

Answer 1

Во всяком случае, использование указателей выглядит почти случайным и произвольным. У вас есть указатели, где они не имеют смысла: HashMap<T, Graph<T>::Node*>и отсутствие указателей там, где должно быть: LinkedList<Node> * adjacent,

Вы также используете динамическое размещение в местах, которые не имеют смысла, например adjacent член Nodeи ваша очистка либо не существует (Graph::Node не имеет деструктора, когда он должен быть один), или полностью сломан (Graph<T>::~Graph() приведет к гарантированной утечке памяти).

Кроме того, ничто никогда не очищает ваш visited флаг, поэтому будет работать только один вызов DFS.

Проще говоря, существует много проблем с вашим кодом, как с точки зрения дизайна, так и с точки зрения реализации.

Ваша конкретная проблема DFS, вероятно, происходит от использования LinkedList<Node> вместо LinkedList<Node*> для списка смежности, потому что это, вероятно, приводит к тому, что граф становится массивным DAG с подграфами, скопированными в список смежности, но трудно сказать, не зная, как LinkedList<> реализовано.

Edit Я чувствую себя немного плохо, просто прямо говоря "это плохо для всех", вот как я правильно реализовал ваш код (используя 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 в поле зрения.