ok..the thing is I find so many different explanations of how dfs iterative search works I am not sure I am doing it the right way or which is the right way.
Code:
Graph :: DFS_iter( Vertex s)
Begin
Stack s
id = 0
for v = 1 to V
visited[v] = 0
s.push(s)
while (not s.isEmpty())
v = s.pop()
if (not visited[v])
visited[v] = ++id
for each vertex u adj(v)
if (not visited[u])
s.push(u)//shouldn't there be a break here? or something
end while
End
that is the algorithm I was given by my lecturer..but it looks to me as if it should be for BFS.
using this algorithm he is going through all the adjacent nodes of the current vertex and pushing them to the stack if unvisited...isn't that BFS? apart from using the queue...
if i start from node A.i find an unvisited node B then push it to the stack, I leave node A and find unvisited node B until I reach a dead end then backtrack.
And for recursion..we got this algorithm
Code:
Graph :: DFS( Vertex s)
Begin
id = 0
for v = 1 to V
visited[v] = 0
dfsVisit(s)
End
Graph :: dfsVisit( Vertex v)
Begin
visited[v] = ++id
for each vertex u adj(v)
if not visited[u]
dfsVisit(u)
End
again..it sounds like bfs to me..
i go through all the adj nodes of vertex A..if they're unvisited recursively call the function and mark them as visited. what happens if there are no nodes to visit? but other branches are unvisited? my brain hurts..