C++ топологическая сортировка, дающая неверный вывод

Question

После обширного тестирования и отладки я не могу на всю жизнь выяснить, почему мой алгоритм топологической сортировки создает неверный вывод. Он просто перечисляет значения узлов в порядке убывания, а не сортирует их топологически. Я перечислил все соответствующие классы/входные файлы. Любые подсказки или помощь приветствуются, спасибо заранее. Заголовок для класса графа:

/* 
2/19/2016 
This is the header for class graph. It includes the definition of a node 
and the function signatures 
*/ 
#pragma once 

#include <iostream> 

using namespace std; 

struct node 
{ 
    // actual value at each node 
    int value; 
    // discovered time 
    int d; 
    // finished time 
    int f; 
    // keep track of how many edges each vertex has 
    int numEdges; 
    // keep track of color of node 
    char color; 
    // parent (previous) node 
    node* p; 
    // next node 
    node* next; 
}; 


// Class to represent a graph 
class Graph 
{ 
public: 
    // constructor, give number of vertexes 
    Graph(int V); 

    // depth first search 
    void DFS(); 

    // function to print sorted nodes 
    void print(); 

    // function for reading file into adjacency list 
    void readFile(istream& in); 

private: 
    // private function called in depth first search, visits every vertex 
    // of each edge in the graph 
    void DFSVisit(node* u); 

    // number of vertices 
    int V; 

    // array of node pointers, first node in each array is 
    // the vertex and following nodes are edges 
    node* adj[9]; 

    // linked list to keep track of the sorted list found from depth first search 
    node* sorted; 

    // keep track of when each node is discovered/finished 
    int time; 

    // keep track of number of backedges 
    int backEdge; 
}; 

Файл каст для класса графа

/* 
2/19/2016 
This is the cpp file for class graph. It defines function behavior 
*/ 

#include "Graph.h" 

using namespace std; 

#include <iostream> 
#include <string> 

Graph::Graph(int V) 
{ 
    // set graph's number of vertexes to number input 
    this->V = V; 
    this->backEdge = 0; 
} 


// Depth first search 
void Graph::DFS() 
{ 
    // initialize all colors to white and parent to null 
    for (int i = 0; i < V; i++) 
    { 
     adj[i]->color = 'w'; 
     adj[i]->p = NULL; 
    } 
    // initialize time to 0 
    time = 0; 
    // for each vertex, if it is white, visit its adjacent nodes 
    for (int i = 0; i < V; i++) 
    { 
     if (adj[i]->color == 'w') { 
      DFSVisit(adj[i]); 
     } 
    } 
} 

// Visit node used by depth first search 
void Graph::DFSVisit(node* u) 
{ 
    // increment time 
    time++; 
    // set u's discovered time 
    u->d = time; 
    // set color to grey for visited but not finished 
    u->color = 'g'; 
    // visit each adjacency, number of adjacencies stored by numEdges 
    for (int i = 0; i < u->numEdges; i++) 
    { 
     // create node pointing at u next 
     node* v = u->next; 
     // if the node is already grey, then it is a backedge 
     if (v->color == 'g') { 
      backEdge++; 
     } 
     // if it is white and undiscovered, set its parent to u and visit v's next nodes 
     else if (v->color == 'w') { 
      v->p = u; 
      DFSVisit(v); 
     } 
    } 
    // set last node to black 
    u->color = 'b'; 
    // increment time 
    time++; 
    // set finishing time 
    u->f = time; 

    if (backEdge == 0) { 
     // adds a node to front of linked list that contains sorted values 
     node* newNode = new node; 
     newNode->next = sorted; 
     newNode->value = u->value; 
     sorted = newNode; 
    } 
} 

void Graph::print() 
{ 
    if (backEdge == 0) { 
     node* curr = sorted; 
     if (sorted == NULL) { 
      return; 
     } 
     else { 
      cout << "Sorted List:\n"; 
      for (; curr; curr = curr->next) 
      { 
       cout << curr->value << " "; 
      } 
      cout << endl; 
     } 
    } 
    else cout << "Backedges: " << backEdge << endl; 
} 

void Graph::readFile(istream& in) 
{ 
    // create node pointers to use later 
    node* head; 
    node* prev; 
    node* curr; 

    // temp string to use while reading file 
    string temp; 
    int j; 
    // loop iterate vertex number of times 
    for (int i = 0; i < V; i++) 
    { 
     // 3rd character in string holds name of first edge 
     j = 3; 
     // read line by line 
     getline(in, temp); 

     // debug print out adjacency list 
     // cout << temp << endl; 

     // create head node, set value to value of vertex, put it at beginning of each linked list 
     head = new node; 
     head->value = i + 1; 
     adj[i] = head; 
     // set numEdges to 0 when row is started 
     adj[i]->numEdges = 0; 
     // set prev to head at end of each outer loop 
     prev = head; 

     // read every adjacency for each vertex, once j goes outside of string reading is done 
     while (j < temp.length()) { 
      // increment numEdges, meaning vertex has one more adjacency 
      adj[i]->numEdges++; 
      // create node and put in value, found by moving j up two spaces and subtracting 48 
      // because it is a char casted as an int 
      curr = new node; 
      curr->value = (int)temp.at(j) - 48; 
      // connect node, increment j by 2 because adjacencies separated by a whitespace 
      prev->next = curr; 
      prev = curr; 
      j += 2; 
     } 
    } 
} 

Драйвер для программы

/* 
2/19/2016 
This is the driver for the topological sort project. It reads a file of 
vertexes and edges into an adjacency list and performs a depth first 
search on that graph representation, creating a topological sort 
if no backedges exist, this indicates a DAG or directed acyclic graph 
if backedges do exist, this indicates a graph containing cycles meaning 
it cannot be topologically sorted 
*/ 

#include <iostream> 
#include <fstream> 
#include <string> 
#include "Graph.h" 

using namespace std; 

string FILE_NAME = "graphin-DAG.txt"; 
int NUM_VERTICES = 9; 

int main() 
{ 
    // create graph object giving number of vertices 
    Graph myGraph(NUM_VERTICES); 

    // open file 
    ifstream fin(FILE_NAME); 

    // validate that file was successfully opened, without file print 
    // error and exit program 
    if (!fin.is_open()) { 
     cerr << "Error opening " + FILE_NAME + " for reading." << endl; 
     exit(1); 
    } 

    // read file into adjacency list 
    myGraph.readFile(fin); 

    // perform depth first search 
    myGraph.DFS(); 

    // if graph is a DAG, print topological sort, else print backedges 
    // this is handled by the print function checking backedges data member 
    myGraph.print(); 
} 

И входного файла

1: 2 
2: 3 8 
3: 4 
4: 5 
5: 9 
6: 4 7 
7: 3 8 
8: 9 
9: 

Также средний ( http://i.imgur.com/6fEjlDY.png

Answer 1

Я думаю, что основная проблема заключалась в том, что между «реальными» узлами и узлами в списке смежности была некоторая путаница. По крайней мере, я запутался, поэтому я разделил структуру на struct Node и struct Adj. Граф теперь имеет Node* nodes[9] для узлов.

struct Node; 

struct Adj 
{ 
    Node* node; 
    Adj* next; 
}; 


struct Node 
{ 
    // actual value at each node 
    int value; 
    // discovered time 
    int d; 
    // finished time 
    int f; 
    // keep track of color of node 
    char color; 
    // the list od adjacencies for the node 
    Adj* adj; 
}; 

и вещи почти мгновенно работают. Ответ

Sorted List: 
6 7 3 4 5 1 2 8 9 

кажется правильным, [6 7 3 4 5] и [1 2 8 9]. См. Рабочий пример here

Обратите внимание, что по-прежнему существует множество проблем с кодом, особенно. в отношении управления памятью. Рассмотрим использование vector<Node> и std::vector<Adj>. В структурах также есть неинициализированные переменные.