Here is the DFS algorithm for the J5:
void bfs()
{
int j;
while ( ! myStack.empty() )
{
int i;
int dist;
/* ----------------------------------
Visit next node
---------------------------------- */
i = myStack.top(); myStack.pop();
dist = distances.top(); distances.pop();
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
/* --------------------------------------------
Check if page is terminal
-------------------------------------------- */
if ( page[i].size() == 0 ) // Terminal page
{
if ( dist < minPathLen )
{
minPathLen = dist ;
cout << " ** new shortest path length: " << minPathLen << endl;
}
}
/* ---------------------------------------------------------------
Visit pages reachable from page[i] that you have NOT visited
--------------------------------------------------------------- */
for ( int j = 0; j < page[i].size(); j++ )
{
if ( ! visited[ page[i][j] ] )
{
cout << " push(" << page[i][j] << ") " << dist+1 << endl;
myStack.push( page[i][j] );
distances.push( dist + 1 );
}
}
}
}
|
DEMO: CCC/2018/Progs/j5-stack.cc use input file j5-2a
Problem: DFS can visit an end point via a longer path first
|
>> 1
push(6) 2
push(3) 2
push(2) 2
>> 2
push(4) 3
>> 4
push(5) 4
push(7) 4
>> 7
** new shortest path
length: 4
>> 5
>> 3
>> 6
|
The algorithm will mark node 5 as visited and will not revisit again (through a possibly shorter path!!)