Поиск глубины ориентированного графа c ++ при первом поиске - PullRequest
Новая
       31

Поиск глубины ориентированного графа c ++ при первом поиске

1 голос
/ 02 декабря 2010

Я пытаюсь написать метод 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
};

спасибо!

Ответы [ 3 ]

3 голосов
/ 02 декабря 2010

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

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

2 голосов
/ 02 декабря 2010

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

Функция предполагаетчто матрица смежности является квадратной, но код инициализации не отображается, поэтому ее следует проверить.Предположение может быть удалено путем выполнения условия внутреннего цикла 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], вводите цикл, находите то же ребро и вызываете рекурсивно ...

2 голосов
/ 02 декабря 2010

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

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

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

должна быть изменена на 

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

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

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

...