Back to General discussions forum
title.
also, can you make it more clear precisely what the output is? I've been trying to add Pair of number and the node "used to visit" but my output is consistently wrong... (ex. output: -1 0 0 31 16 16 16 16 32 18 18 12 12 1 1 1 1 8 25 25 17 40 29 29 29 15 6 7 3 14 27 30 30 5 10 38 38 34 36 22
expected: -1 25 0 13 31 13 40 25 29 3 3 2 23 0 40 1 31 23 25 7 27 1 11 0 33 0 22 40 5 13 29 0 17 23 23 16 5 23 5 10 2 ) any hints?
Hello, Goodwin,
I tried to solve this problem and can confirm now than output undeed should contain the space-delimeted seen array - the array describing in which order nodes are visited during search.
The element of seen array with index 0 contains -1, because starting node (with id 0) will not be visited from any node in the searching process.
Let say we visited nodes with ids a, b, and c from node with id 0. We reflect this fact by marking seen[a] = 0, seen[b] = 0, seen[c] = 0.
Later we visited nodes with ids x, y, z from node with id a and mark seen[x] = a, seen[y] = a, seen[z] = a. And so on for other nodes.
Hopefully I described the idea clearly enough.
I checked your code, very nice! The only modifications you needed are:
1) Add array of seen:
int seen[] = new int[V];
2) After receiving a pair from queue, update seen array:
seen[p.getKey()] = p.getValue();
3) Sort adjacency lists before looping over them.
4) Print entries of seen array after end of while loop.
thanks for the response! I had trouble interpreting what the problem meant but your assignment makes things clear.
May I ask, why doesn't the same idea work with DFS? I tried the similar " seen[p.getKey()] = p.getValue()" and sorting, but my output is still incorrect somehow...
Looks like DFS problem is trickier than BFS one...
First - why I don't see you using pairs in latest DFS solution? How can you use:
seen[p.getKey()] = p.getValue();
...if there are only vertex ids in stack instead of pairs?
Second, I think it is important that we do not need to check if vertex was seen (visited) when pushing it to stack. But we need to make such check while popping an item from stack.
So remove this check:
if(!visited.get(v)){
stack.push(v);
...
}
and do simply:
stack.push(new Pair<>(v, p.getKey()));
but don't forget to add this check after popping a pair from the stack!
Hope this helps.
I tried implementing this, but it wasn't right... any more hints? (I also added a recursive approach in case it was easier, but couldn't figure it out)
You should check if s is seen (visited) immediately after popping a pair, not in inner loop! And if s is seen (visited) you should simply skip remaining part (do not execute inner loop).
alright, after I popped it I tried to see if s was visited or not, and only executed inner if it wasn't visited, but my output is still wrong... man, this is tearing my hair apart.
Hello, Goodwin. I think you almost done it, only two things left:
1) Notice that graph is undirected, so add edges to both directions.
g.addEdge(e1, e2);
g.addEdge(e2, e1);
2) Because we pop items from stack in reversed order, we must sort in reversed order:
Collections.sort(adj[s], Collections.reverseOrder());
P.S. Congrats on receiving the Stargazer rank :)!