c ++ profondità grafo orientato prima ricerca

Question

Sto tentando di scrivere un metodo di DFS metodo per un grafo orientato. In questo momento io sono in esecuzione in un errore di segmentazione, e sono davvero sicuri di dove si trova. Da quello che ho capito di grafi orientati Credo che la mia logica è giusto ... ma una nuova serie di occhi sarebbe un bel aiuto.

Questa è la mia funzione:

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

definizione di classe:

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

grazie!

Answer 1

Ci sono alcune cose che si potrebbe prendere in considerazione. Il primo è che le variabili statiche a livello di funzione non sono di solito una buona idea, probabilmente si può ridisegnare e rendere tali variabili sia regolari (al costo di accantonamenti aggiuntivi) o membri di istanza e mantenerli in vita.

La funzione presuppone che la matrice di adiacenza è quadrata, ma il codice di inizializzazione non viene mostrato, quindi dovrebbe essere controllato. L'assunzione può essere rimosso facendo il adj_matrix[v].size() interna condizione di loop (dato un v nodo) oppure se è un invariante, aggiungere un'asserzione prima di tale ciclo interno: assert( adj_matrix[v].size() == adj_matrix.size() && "adj_matrix is not square!" ); --il stesso vale per il size membro e la dimensione del adj_matrix è di per sé.

L'intero algoritmo sembra più complessa di quanto dovrebbe, un DFS partendo nodo v ha la forma generale di:

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

Il vostro algoritmo sembra essere (in modo non corretto tra l'altro) transversing il grafico nella direzione opposta. Si imposta il nodo dato come visited, e quindi provare a individuare qualsiasi nodo che è il punto di partenza di un bordo a quel nodo. Cioè, invece di nodi seguenti raggiungibile da v, si sta cercando di ottenere i nodi per i quali v è raggiungibile. Se questo è il caso (vale a dire se l'obiettivo è la stampa di tutti i percorsi che convergono nella v) allora si deve essere attenti a non colpire lo stesso bordo due volte o si finirà in un ciclo infinito -> StackOverflow.

Per vedere che si finirà con stackoverlow, considerare questo esempio. Nodo di partenza è 1. Si crea il vettore visited e la posizione marchio 1 come visitato. Si scopre che c'è un bordo (0,1) nella struttura, e che inneschi il caso: adj_matrix[0][1] != 0 && visited[1], quindi si entra in modo ricorsivo con nodo di partenza essendo 1 di nuovo. Questa volta non si costruisce i dati ausiliari, ma un'osservazione visited[1], entrare nel ciclo, trovare lo stesso bordo e chiamare ricorsivamente ...

Answer 2

si sta eliminando visited prima della fine del programma. Tornando al vertice di partenza non significa che finito. Ad esempio, per il grafico di V = {1,2,3}, E = {(1,2), (2,1), (1,3)}.

Inoltre, avviso si utilizza v come parametro di input e anche come variabile per-loop.

Answer 3

Vedo un paio di problemi:

La seguente riga

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

deve essere modificato in

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

(Si desidera recurse solo sui vertici che hanno non già stata visitata.)

Inoltre, si sta creando un nuovo v variabile nel ciclo for che nasconde il parametro v:. Che è C ++ legale, ma è quasi sempre una pessima idea