Отметка времени DFS

Question

#include <iostream> 
#include <vector> 
#include <list> 

using namespace std ; 

class Graph 
{ 
public: 
    Graph(int V) 
    { 
     this->V = V ; 
     G.resize(V) ; 
    } 
    void addEdge(int v , int w) 
    { 
     G[v].push_back(w) ; 
     G[w].push_back(v) ; 
    } 
    void DFS(int s) 
    { 
     bool *visited = new bool[this->V] ; 
     for(int i = 0 ; i < this->V ; i++) 
      visited[i] = false ; 

     int *arrival = new int[this->V] ; 
     int *departure = new int[this->V] ; 

     static int t = 0 ; 
     DFSUtil(s,visited,arrival,departure,t) ; // Utility function to do the DFS 
     cout << "\n" ; 
     for(int i = 0 ; i < this->V ; i++) 
      cout << arrival[i] << "/" << departure[i] << " " ; 

    } 
    void printGraph() 
    { 
     vector< list<int> >::iterator i ; 
     list<int>::iterator j ; 

     int k = 0 ; 
     int t = 0 ; 
     for(i = G.begin() ; i != G.end() ; ++i) 
     { 
      cout << "Node " << k++ << "->" ; 
      for(j = G[t].begin() ; j != G[t].end() ; ++j) 
       cout << *j << "->" ; 
      cout << "NULL\n" ; 
      t++ ; 
     } 
    } 
private: 
    int V ; // number of vertices 
    vector< list<int> > G ; // array of lists 
    void DFSUtil(int s , bool *visited , int *arrival , int *departure , int t) // Utility function to do DFS 
    { 
     cout << s << " " ; 
     visited[s] = true ; 
     arrival[s] = ++t ; 
     list<int>::iterator i ; 
     for(i = G[s].begin() ; i != G[s].end() ; ++i) 
     { 
      if(!visited[*i]) 
       DFSUtil(*i,visited,arrival,departure,t) ; 
     } 
     departure[s] = ++t ; 
    } 
}; 

int main() 
{ 
    // Create a graph given in the above diagram 
    Graph g(6); 
    g.addEdge(0, 1); 
    g.addEdge(0, 2); 
    g.addEdge(1, 2); 
    g.addEdge(0, 4); 
    g.addEdge(0, 3); 
    g.addEdge(1, 4); 
    g.addEdge(1, 5); 
    g.addEdge(4, 5); 
    g.addEdge(3, 5); 
    g.printGraph() ; 
    cout << "Following is Depth First Traversal (starting from vertex 0) \n"; 
    g.DFS(0); 

    return 0; 
} 

Я хотел установить временную отметку процесса DFS, т.е. когда процесс поиска достигает определенного узла, а затем bactracks из него. То, что я имею в виду, что, когда ДФС начинается его первые визиты узел 0 так arrival[0] = 1, то он рекурсивно вызывает на узле 1 так arrival[1] = 2, а затем рекурсивно вызывает на узле 2 так arrival[2] = 3, теперь узел 2 не может позвонить по любому так departure[2] должен быть 4 и впоследствии, но то, что моя программа выходит не в том же направлении, что я ожидал. Я думал, что объявление переменной timestamp t как статичное могло бы сделать трюк, но оно не работает. Как это исправить?

Answer 1

«статический» в этом контексте по существу означает «существует только одна из них, которая разделяется всеми вызовами этой функции».
Вы по-прежнему передаете копию переменной в качестве параметра для других функций.

Если вы хотите, чтобы вызываемая функция могла изменять переменную, вы передаете ей ссылку на эту переменную.

Удалить "статический", и изменить DFSUtil к

void DFSUtil(int s, bool *visited, int *arrival, int *departure, int &t)