Можно ли улучшить эту реализацию C ++ поиска в глубину?

Я получил реализацию DFS на C ++ от здесь и внес в него небольшие изменения. Измененный код выглядит следующим образом:

#include "stdafx.h"
#include <iostream>
#include<map>
#include<list>

class Graph {
    void DFSUtil(int v);
public:
    std::map<int, bool> visited;
    std::map<int, std::list<int>> adj;
    void addEdge(int v, int w);
    void DFS();
};

void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w); 
}

void Graph::DFSUtil(int v)
{
    visited[v] = true;
    std::cout << v << " ";

    std::list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
        if (!visited[*i])
            DFSUtil(*i);
}


void Graph::DFS()
{
    for (auto i : adj)
        if (visited[i.first] == false)
            DFSUtil(i.first);
}

int main()
{
    Graph g;
    g.addEdge(0, 1);
    g.addEdge(0, 9);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(9, 3);

    std::cout << "Depth First Traversal resultn";
    g.DFS();

    std::cin.get();

    return 0;
}

Какие дальнейшие улучшения я могу внести в этот код?

Какие дальнейшие улучшения я могу внести в этот код?

Код довольно плохой — на сайте, с которого вы его читаете, обычно много плохих / любительских статей.

1. Класс графа:

   std::map<int, bool> visited;
   std::map<int, std::list<int>> adj;
   

Это крайне плохая и неэффективная реализация графа. std::map создает новое выделение памяти для каждого элемента. Таким образом, вы делаете это дважды как для логического, так и для списка. Также std::list также выделяет часть памяти для каждого элемента.

Чрезмерное использование выделения памяти означает как проблемы фрагментации памяти, так и проблемы с производительностью из-за большого количества неуправляемого доступа к ОЗУ и косвенных обращений. Загрузка памяти в настоящее время является одной из самых медленных операций на современных процессорах. Но компиляторы, как правило, довольно хорошо оптимизируют его, если память непрерывна, что в данном случае далеко от истины.

Чтобы упростить структуру, лучше использовать std::vector<Node> где Node содержит информацию о вершине + std::vector<size_t> соседей. В общем, я не верю, что есть идеальное решение для представления графов — вместо этого существует множество способов представления, и каждый из них подходит или более приспособлен к определенным типам графиков. Например, решения, которые подходят для разреженных графов, безусловно, очень плохо подходят для плотных графов. Также можно сделать некоторые дополнительные оптимизации, предполагая, что график исправлен. Вопрос сложный, и я не могу дать ответ, не зная о сценарии использования.

2. DFS() реализация тоже довольно плохая. Он полагается на рекурсию, и я уверяю вас, что для достаточно больших связанных графов с ним будет взорван стек, что приведет к UB.

Правильная реализация DFS / BFS хранит посещаемые состояния в std::stack или же std::queue или что-то подобное, в то время как процедура посещения выполняется в одном цикле, а не в рекурсии.

Кроме того, я полагаю, вам нужен какой-то вывод или действие, выполняемое над вершинами из DFS, не так ли?

std::map<int, bool> visited;

Это бесполезно как переменная-член.

• Это ничего не значит до или после того, как вы позвоните DFS, поэтому большую часть времени это пустая трата места
• Для данного Graph, что означает, что вы не можете позвонить DFS дважды одновременно
• Он сохраняет свое состояние после вызова DFS в первый раз, а это значит, ты даже не можешь позвонить DFS два раза подряд.

Эта переменная должна быть локальной для DFS, создается заново при каждом вызове и передается в DFSUtil по ссылке, если вообще (использование стека и цикла, как упоминалось в обзоре ALX23z, вообще не требует вспомогательного метода).