c ++ profundidad grafo dirigido primera búsqueda

Question

Estoy intentando escribir un método DFS método para un grafo dirigido. En este momento estoy corriendo en un fallo de segmentación, y yo soy muy inseguro en cuanto a donde está. Por lo que entiendo de gráficos dirigidos Creo que mi lógica es correcto ... pero un nuevo juego de los ojos sería una muy buena ayuda.

Esta es mi función:

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;
     }
   }
}
}

definición de clase:

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
};

Gracias!

Answer 1

Hay algunas cosas que usted puede tener en cuenta. La primera es que las variables estáticas de nivel de función no son por lo general una buena idea, es probable que pueda rediseñar y hacer que esas variables, ya sea regulares (a costa de las asignaciones adicionales) o miembros de instancias y mantenerlos vivos.

La función asume que la matriz de adyacencia es cuadrada, pero no se muestra el código de inicialización, por lo que se debe comprobar. La suposición se puede quitar haciendo que el adj_matrix[v].size() condición de bucle interior (dado un v nodo) o bien si es un invariante, añadir una aserción antes de que bucle interno: assert( adj_matrix[v].size() == adj_matrix.size() && "adj_matrix is not square!" ); --el mismo ocurre con el size miembro y el tamaño de la adj_matrix si mismo.

Todo el algoritmo parece más complejo de lo que debería, un DFS de partida en el nodo v tiene la forma general de:

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

Su algoritmo parece ser (incorrectamente por cierto) transversing el gráfico en la dirección opuesta. Se establece el nodo dado como visited y, a continuación, intenta localizar cualquier nodo que es el punto de inicio de un borde a ese nodo. Es decir, en lugar de seguir los nodos alcanzable de v, que está tratando de obtener nodos para los que v es alcanzable. Si ese es el caso (es decir, si el objetivo es la impresión de todos los caminos que convergen en v), entonces hay que tener cuidado de no golpear el mismo borde dos veces o que va a terminar en un bucle infinito -> stackoverflow.

Para ver que el resultado final será con stackoverlow, considere este ejemplo. El nodo de inicio es 1. Se crea el vector visited y la posición 1 marca como visitado. Usted encontrará que hay un borde (0,1) en el árbol, y que desencadena el caso: adj_matrix[0][1] != 0 && visited[1], por lo que se introduce de forma recursiva con el nodo de inicio 1 siendo de nuevo. Esta vez no construye los datos auxiliares, pero visited[1] observación, entrar en la serie, encuentra el mismo borde y llama de forma recursiva ...

Answer 2

va a eliminar visited antes del final del programa. Volviendo al vértice inicial no significa que usted terminado. Por ejemplo, para la gráfica de V = {1,2,3}, E = {(1,2), (2,1), (1,3)}.

Además, el aviso que está utilizando v como parámetro de entrada y también como la variable de bucle.

Answer 3

Veo un par de problemas:

La siguiente línea

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

debe ser cambiado a

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

(¿Quieres recursiva sólo en vértices que han no fue visitado ya.)

Además, se está creando una nueva variable v en el bucle for que esconde el parámetro v:. Que es legal C ++, pero es casi siempre una mala idea