C ++ gerichteten Graphen Tiefensuche

Question

Ich bin versucht, ein Verfahren DFS-Verfahren für einen gerichteten Graphen zu schreiben. Im Moment bin ich laufen in einen Segmentation Fault, und ich bin wirklich nicht sicher, wo es ist. Von dem, was ich von gerichteten Graphen verstehe ich glaube, dass meine Logik richtig ist ... aber eine neue Reihe von Augen wäre eine sehr schöne Hilfe sein.

Hier ist meine Funktion:

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

Klassendefinition:

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

Danke!

Answer 1

Es gibt ein paar Dinge, die Sie vielleicht zu prüfen. Das ist zunächst, dass die Funktionsebene statische Variablen sind nicht in der Regel eine gute Idee, können Sie wahrscheinlich neu zu gestalten und diese entweder reguläre Variablen machen (auf Kosten der zusätzlichen Zuweisungen) oder Instanzmitglieder und halten sie am Leben.

Die Funktion geht davon aus, dass die Adjazenzmatrix ist quadratisch, aber die Initialisierung Code wird nicht angezeigt, so dass es überprüft werden soll. Die Annahme kann, indem die innere Schleifenbedingung adj_matrix[v].size() (Bei einer gegebenen Knoten v) oder auch entfernt werden, wenn diese eine Invariante ist, fügt eine assert vor dieser inneren Schleife: assert( adj_matrix[v].size() == adj_matrix.size() && "adj_matrix is not square!" ); --die gleiche gilt für das Element size und die Größe der adj_matrix selbst ein.

Der gesamte Algorithmus komplexer als scheint es sollte, ein DFS am Knoten v Start hat die allgemeine Form:

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

Ihr Algorithmus scheint (übrigens falsch) quert die Grafik in der entgegengesetzten Richtung zu sein. Sie setzen den gegebenen Knoten als visited, und dann versuchen, einen beliebigen Knoten zu suchen, die den Startpunkt einer Kante zu diesem Knoten ist. Das heißt, anstelle von folgenden Knoten erreichbar von v, Sie versuchen, Knoten zu erhalten, für die v erreichbar ist. Wenn das der Fall ist (das heißt, wenn das Ziel druckt alle Pfade, die in v konvergieren), dann müssen Sie darauf achten, nicht die gleiche Flanke zu schlagen zweimal oder Sie werden in einer Endlosschleife am Ende -> Stackoverflow.

Um zu sehen, dass Sie mit stackoverlow enden werden, dieses Beispiel. Der Startknoten ist 1. Sie erstellen die visited Vektor und Markenposition 1 als besucht. Sie finden, dass es eine Kante (0,1) in dem Baum, und dass Auslöser der, wenn: adj_matrix[0][1] != 0 && visited[1], so dass Sie wieder rekursiv mit Startknoten 1 eingeben zu sein. Dieses Mal werden Sie konstruieren nicht die Hilfsdaten, sondern Bemerkung visited[1], die Schleife eingeben, die gleiche Kante finden und rekursiv rufen ...

Answer 2

Sie löschen visited vor dem Ende des Programms. Kommen wir zurück zu den Startecke bedeutet nicht, Sie fertig. Zum Beispiel für die graphische Darstellung von V = {1,2,3}, E = {(1,2), (2,1), (1,3)}.

Beachten Sie auch, Sie v als Eingabeparameter verwenden und auch als for-Schleife Variable.

Answer 3

Ich sehe ein paar Probleme:

Die folgende Zeile

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

sollte geändert werden

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

(Sie wollen nur auf Eckpunkte Rekursion, die haben nicht bereits besucht.)

Auch sind Sie eine neue Variable v in der for Schleife zu schaffen, dass Häuten der Parameter v:., Die legal C ++, aber es ist fast immer eine schreckliche Idee