c ++ profondeur de graphe orienté première recherche

Question

Je tente d'écrire une méthode méthode DFS pour un graphe orienté. En ce moment je suis en cours d'exécution d'un défaut de segmentation, et je suis vraiment pas sûr de l'endroit où il est. D'après ce que je comprends des digraphes Je crois que ma logique est juste ... mais une nouvelle série d'yeux serait une aide très agréable.

Voici ma fonction:

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

définition de 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
};

merci!

Answer 1

Il y a quelques choses que vous pourriez envisager. La première est que le niveau de la fonction des variables statiques ne sont généralement pas une bonne idée, vous pouvez probablement repenser et faire ces variables soit régulières (au coût des allocations supplémentaires) ou des membres de l'instance et de les maintenir en vie.

La fonction suppose que la matrice de contiguïté est carrée, mais le code d'initialisation ne soit pas représenté, il doit être vérifié. L'hypothèse peut être retirée en faisant la condition de la boucle intérieure adj_matrix[v].size() (donné une v de noeud) ou bien si c'est un invariant, ajoutez une assertion avant que la boucle intérieure: assert( adj_matrix[v].size() == adj_matrix.size() && "adj_matrix is not square!" ); --Le va de même pour le membre size et la taille de la adj_matrix elle-même.

L'algorithme entier semble plus complexe qu'elle ne devrait, un DFS de départ au noeud v est de la forme générale:

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

Votre algorithme semble être (à tort par la voie) transversing le graphique dans le sens opposé. Vous définissez le nœud donné comme visited, et puis essayer de localiser un noeud qui est le point de départ d'un bord à ce noeud. Autrement dit, au lieu de nœuds suivants accessible de v, vous essayez d'obtenir des noeuds pour lesquels v est accessible. Si tel est le cas (à savoir si l'objectif est d'imprimer tous les chemins qui convergent dans v) alors vous devez faire attention de ne pas frapper le même bord deux ou vous finirez dans une boucle infinie -> stackoverflow.

Pour voir que vous terminerez avec stackoverlow, considérez cet exemple. Le noeud de départ est 1. Vous créez le vecteur visited et 1 de position marque comme visité. Vous trouvez qu'il ya un bord (0,1) dans l'arbre, et qui déclenche le cas: adj_matrix[0][1] != 0 && visited[1], vous entrez récursive avec noeud de départ étant 1 à nouveau. Cette fois-ci vous ne construisez pas les données auxiliaires, mais remarque visited[1], entrer dans la boucle, trouver le même bord et appelez récursive ...

Answer 2

Vous supprimez visited avant la fin du programme. Pour en revenir au sommet de départ ne signifie pas que vous avez terminé. Par exemple, pour le graphe de V = {1,2,3}, E = {(1,2), (2,1), (1,3)}.

En outre, un avis que vous utilisez v comme paramètre d'entrée et comme la variable boucle.

Answer 3

Je vois quelques problèmes:

La ligne suivante

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

devrait être modifié à

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

(Vous voulez récursivité uniquement sur les sommets qui ont pas déjà été visité.)

En outre, vous créez une nouvelle v variable dans la boucle de for qui cache le paramètre v. Qui est C ++ juridique, mais il est presque toujours une idée terrible