#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
как статический, добился бы цели, но это не работает. Как это исправить?
«статический» в этом контексте означает, что «существует только один из них, который используется всеми вызовами этой функции».
Вы все еще передаете копия переменной в качестве параметра для других функций.
Если вы хотите, чтобы вызываемая функция могла изменять переменную, вы передаете ей ссылку на эту переменную.
Убери «статик» и поменяй DFSUtil
в
void DFSUtil(int s, bool *visited, int *arrival, int *departure, int &t)