Recursive Depth First Search:
bool visited[N];
void dfs(int i)
{
int j;
visited[i] = true; // Mark node i as "visited"
/* ---------------------------------------------------------------
We reached node i... Something wonderful may happen at i
I print node i out - Replace with code that solves your problem
--------------------------------------------------------------- */
cout << i << endl; // Debug use
/* ---------------------------------------------------------------
How you find nodes j will depend on how you represent the graph
--------------------------------------------------------------- */
for ( each node j that can be reached from node i )
{
if ( ! visited[j] )
{
dfs(j); // Function calls are LIFO
}
}
}
|
Depth First Search can also be implemented using a stack (which is LIFO):
bool visited[N];
void dfs(int i)
{
int j;
visited[i] = true; // Mark node i as "visited"
/* ---------------------------------------------------------------
We reached node i... Something wonderful may happen at i
I print node i out - Replace with code that solves your problem
--------------------------------------------------------------- */
cout << i << endl; // Debug use
/* ---------------------------------------------------------------
How you find nodes j will depend on how you represent the graph
--------------------------------------------------------------- */
for ( each node j that can be reached from node i )
{
if ( ! visited[j] )
{
|
Stack-based implementation of the Depth First Search algorithm:
void dfs()
{
int i, j;
while ( myStack != empty )
{
i = myStack.pop(); // Get next node to visit
visited[i] = true; // Mark node i as "visited"
/* ----------------------------------------------------------
We reached node i... Something wonderful may happen at i
---------------------------------------------------------- */
cout << i << endl; // Change accordingly
/* -------------------------------------------------------------
How you find nodes j will depend on how you represent the graph
------------------------------------------------------------- */
for ( each node j that can be reached from node i )
{
if ( ! visited[j] )
{
myStack.push(j); // Visit node j
} // When you loop back up, myStack.pop() will visit the node!
}
}
}
|
void dfs()
{
int i, j;
int x, y;
while ( ! xCoord.empty() )
{
// Visit next node
x = xCoord.top(); xCoord.pop();
y = yCoord.top(); yCoord.pop();
visited[x][y] = true; // Mark (x,y) as visited
if ( x == M && y == N )
{
cout << "yes" << endl;
exit(0);
}
// Go to next nodes
for ( i = 1; i <= M; i++ ) // M can be reduced...
{
// DO NOT search, j can be computed as: j = grid[x][y]/i
{ j = grid[x][y] / i;
if ( i*j == grid[x][y] && j <= N ) // j must be value: j <= N !!!
if ( ! visited[i][j] )
{
xCoord.push(i); yCoord.push(j); // Visit node (i,j)
}
}
}
}
}
|
Demo: CCC/2020/Progs/sol5-stack.cc