-1

I have a very interesting question regarding how to find a list of reachable destinations given a source (starting point) that only takes at most n moves.

Dew Man7
  • 33
  • 5
  • 1
    Simple BFS would solve the problem. https://stackoverflow.com/questions/2505431/breadth-first-search-and-depth-first-search/2508261 – Abhinav Mathur Apr 11 '21 at 20:29
  • Is there a way to do it for a beginner programmer taking intro to programming? I haven't learnt BFS but this problem is based on that course – Dew Man7 Apr 11 '21 at 20:32
  • You have a convenient adjacency list and a breadth first search with a limitation on the number of levels as number of moves will solve your problem. – SomeDude Apr 11 '21 at 20:32
  • Can you provide pseudocode since I am totally lost on how to apply BFS for this problem since I am taking intro to programming and have never learnt this in my class – Dew Man7 Apr 11 '21 at 20:57
  • Ok I implemented bfs but how do I keep track of depth level from starting position? I can show you what I have so far – Dew Man7 Apr 11 '21 at 22:44

1 Answers1

1

Normally BFS is written with a queue, and I think this is unnecessary and also somewhat confusing. I've written it the way one might think of it in pictures, with a fringe which expands step by step.

def bfs(n, neighbors, source):
    fringe = [source]
    seen = dict()

    for i in range(n):
        next_fringe = []
        for u in fringe:
            for v in neighbors[u]:
                if v not in seen.keys():
                    next_fringe.append(v)
                    seen[v] = i + 1
        fringe = next_fringe

    return seen


source_destination = {"A": ["B", "D"], "B": ["C"], "C": ["D", "A"], "D": ["A"]}
print(bfs(3, source_destination, "A"))

This also keeps track of distance. I would encourage you to think carefully about this code and why it is correct!

Jerry Halisberry
  • 176
  • 10
  • For the example bfs(2, source_destination, "A"), I was supposed to get ["A", "B", "C", "D"] but I ended up getting ["B", "C", "D"]. Is there a way to fix this? – Dew Man7 Apr 12 '21 at 19:21
  • You mentioned "I don't include the source (starting point) in my reachable destinations." Thus I added in `del seen[source]`. You can simply remove this line. – Jerry Halisberry Apr 12 '21 at 20:16
  • The reason for this output is because if starting from "A" and only require 2 moves at most, then the possible paths are: "A" -> "B" -> "C" and "A" -> "D" -> "A". Now in the second case, I include "A" because it is a reachable destination (returns to itself) based on the path. A little confusing – Dew Man7 Apr 12 '21 at 21:40
  • Gotcha. In that case, remove the del, and also replace the initialization of `seen` to just `set()`. Now, source will not be in there initially, but you can reach it at a later point in time. – Jerry Halisberry Apr 12 '21 at 21:51
  • I get an error when replacing seen initialization with set and removed del keyword. Would you mind editing your post to see what you mean? – Dew Man7 Apr 12 '21 at 21:59
  • I got an Attribute Error: AttributeError: 'set' object has no attribute 'keys' – Dew Man7 Apr 12 '21 at 22:03
  • Whoops - because it should be a dict. I'll edit again. – Jerry Halisberry Apr 12 '21 at 22:05
  • Ok now everything works well. How do I guarantee that it works for all edge cases? – Dew Man7 Apr 12 '21 at 22:08
  • When thinking about objects like graphs, it helps to prove things mathematically. Consider any vertex v, which has distance d from your source, u. So there is a path of length d from from u to v, and there is no path of length d-1 or shorter from u to v. Inductively, the bfs will reach a neighbor of v in d-1 steps. Then on the next step of the bfs, v will be reached, and marked with distance d. – Jerry Halisberry Apr 12 '21 at 22:10
  • As far as considering the implementation itself (and not the algorithm), I would guess that something with as low complexity as a bfs is OK if it passes a few handwritten cases. – Jerry Halisberry Apr 12 '21 at 22:11
  • Ok thanks. I've learnt alot about BFS so I'll keep that in mind. I accepted your answer – Dew Man7 Apr 12 '21 at 22:13
  • One more question: will algorithm work for very large datasets? – Dew Man7 Apr 12 '21 at 22:24
  • BFS will work in linear time. You can handle large datasets of size 10^5 probably just fine. But, Python is slow, and if you want to go above that reliably, you will want to write code in a different language, or look into Python libraries which optimize code or provide efficient BFS implementation. – Jerry Halisberry Apr 12 '21 at 22:33