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

#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, т. Е. Когда процесс поиска достигает определенного узла, а затем обнаруживает бактреки с него. Я имею в виду, что когда начинается DFS, он впервые посещает узел 0 так arrival[0] = 1 , то это рекурсивно вызывает на узле 1 так arrival[1] = 2 затем рекурсивно вызывает на узле 2 так arrival[2] = 3 теперь узел 2 не могу никого вызвать departure[2] должно быть 4 и впоследствии, но то, что выводит моя программа, не совпадает с тем, что я ожидал. Я думал, что объявление переменной времени t как статический, добился бы цели, но это не работает. Как это исправить?

0

Решение

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

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

Убери «статик» и поменяй DFSUtil в

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

Другие решения


По вопросам рекламы ammmcru@yandex.ru
Adblock
detector