Блог пользователя iamdumb

This question using BFS ?

Автор iamdumb, 9 лет назад, По-английски

Can anybody please tell me how do i approach this question Two-Buttons using BFS. I know how to do this other way but not using BFS(new to graph algorithms :) ).And why did we use BFS not DFS.In what scenario we use DFS and in What BFS.Thanks

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

In every step you can choose multiple the current number by 2 or subtract 1. And for every new number you can do the same recursively.

Example (First input):

Input:

4 6

    4
 /    \
3      8
| \    |  \
2  6   7   16

Output:

2

Using BFS you can found the shortest path from 4 to 6 in this example is 2.

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks a lot..But why did you use BFS ?You could have used DFS instead

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      DFS doesn't work, because the first goal you reach in your DFS tree is not necessarily optimal.

      Suppose say, you find the goal node in your DFS tree at depth k, but it is certainly possible that there exists another goal node located at depth < k. You just haven't explored that goal yet.

      → Ответить