C ++ Направленный Глубина Глубина Графа

Question

Я пытаюсь написать метод DFS метод для направленного графика. Сейчас я бегу в неисправность сегментации, и я действительно не уверен, что это так. От того, что я понимаю из направленных графиков, я считаю, что моя логика прав ... Но свежий набор глаз будет очень хорошей помощи.

Вот моя функция:

void wdigraph::depth_first (int v) const {

static int fVertex = -1;
static bool* visited = NULL;

if( fVertex == -1 ) {
   fVertex = v;
   visited = new bool[size];
   for( int x = 0; x < size; x++ ) {
      visited[x] = false;
   }
}

cout << label[v];
visited[v] = true;

for (int v = 0; v < adj_matrix.size(); v++) {
   for( int x = 0; x < adj_matrix.size(); x++) {
     if( adj_matrix[v][x] != 0 && visited[x] != false ) {
        cout << " -> ";
        depth_first(x);
     }
     if ( v == fVertex ) {
        fVertex = -1;
        delete [] visited;
        visited = NULL;
     }
   }
}
}

Определение класса:

class wdigraph {
public:
wdigraph(int =NO_NODES);          // default constructor
~wdigraph() {};                   // destructor
int get_size() { return size; }   // returns size of digraph

void depth_first(int) const;// traverses graph using depth-first search
void print_graph() const;   // prints adjacency matrix of digraph

private:
int size;                         // size of digraph
vector<char> label;               // node labels
vector< vector<int> > adj_matrix; // adjacency matrix
};

Спасибо!

Answer 1

Есть несколько вещей, которые вы можете рассмотреть. Во-первых, эта функция Уровень статических переменных обычно не является хорошей идеей, вы, вероятно, можете переписать и делать те и регулярные переменные (по стоимости дополнительных распределений) или членов экземпляра и сохраняют их в живых.

Функция предполагает, что матрица смежности является квадратным, но код инициализации не отображается, поэтому его следует проверить. Предположение можно удалить, сделав состояние внутреннего цикла adj_matrix[v].size() (Учитывая узел v) Или, если это инвариант, добавьте заявку до этого внутреннего цикла: assert( adj_matrix[v].size() == adj_matrix.size() && "adj_matrix is not square!" ); - То же самое касается члена size и размер adj_matrix сам.

Весь алгоритм кажется более сложным, чем он должен, DFS, начиная с узла V, имеет общую форму:

dfs( v )
   set visited[ v ]
   operate on node (print node label...)
   for each node reachable from v:
      if not visited[ node ]:
         dfs( node )

Ваш алгоритм, по-видимому, (неправильно, кстати), трансформируя график в противоположном направлении. Вы устанавливаете данный узел как visited, а затем попытайтесь найти любой узел, который является начальной точкой края к этому узлу. То есть вместо следующих узлов Доступно от v, вы пытаетесь получить узлы, для которых v Доступно. Если это так (то есть, если цель печатает все пути, которые сходятся в v) Тогда вы должны быть осторожны, чтобы не ударить одни и те же края дважды или в конечном итоге в бесконечной петле -> StackoverFlow.

Чтобы увидеть, что вы закончите с Stackoverlow, рассмотрите этот пример. Начальный узел 1. Отказ Вы создаете visited Вектор и пометка 1 как посещаемое. Вы обнаружите, что в дереве есть край (0,1), а что триггеры IF: adj_matrix[0][1] != 0 && visited[1], чтобы вы входите рекурсивно с наступлением узла 1 очередной раз. На этот раз вы не строим вспомогательные данные, но замечание visited[1], Введите петлю, найдите один и тот же край и позвоните рекурсивно ...

Answer 2

Вы удалеете visited до конца программы. Возвращаясь к начальной вершине не означает, что вы закончите. Например, для графа V = {1,2,3}, E = {(1,2), (2,1), (1,3)}.

Кроме того, обратите внимание, вы используете v как входной параметр, а также в качестве переменной для петли.

Answer 3

Я вижу пару проблем:

Следующая строка

 if( adj_matrix[v][x] != 0 && visited[x] != false ) {

следует изменить на

 if( adj_matrix[v][x] != 0 && visited[x] == false ) {

(Вы хотите вернуться только на вершины, которые имеют нет были посещены уже.)

Кроме того, вы создаете новую переменную v в for петля, которая скрывает параметр v: Это законно C ++, но это почти всегда ужасная идея.