CODEWITHSUNDEEP
python
John Lorenz Inocentes
John Lorenz Inocentes

Reputation: 35

Finding path from point A to point B using recursion in Python

{'John': ['Bryant', 'Debra', 'Walter'], 'Bryant': ['Olive', 'Ollie', 'Freda', 'Mercedes'], 'Mercedes': ['Walter', 'Robin', 'Bryant'], 'Olive': ['John', 'Ollie'], 'Debra': ['Walter', 'Levi', 'Jennie', 'Robin'], 'Walter': ['John', 'Levi', 'Bryant'], 'Levi': ['Ollie', 'John', 'Walter'], 'Ollie': ['Mercedes', 'Freda', 'Bryant'], 'Jennie': ['Levi', 'John', 'Freda', 'Robin'], 'Robin': ['Ollie'], 'Freda': ['Olive', 'John', 'Debra']}

This dictionary will be the "network", the input in the path function which contains the users and their corresponding connections.

I have to define a function that finds a connection path from a userA to userB and return the path in a list using recursion. It should also return None if no path exists but I don't know how to achieve that.

Example Input: find_path_to_frind(network,"Levi", "Jennie")

Output: ['Levi', 'Ollie', 'Mercedes', 'Walter', 'John', 'Debra', 'Jennie']

This my attempt but it raises a RecursionError:

def find_path_to_friend(network, user_A, user_B):
    path = [user_A]
    connections = network[user_A]["is connected to "]
    if user_B in connections:
        path.append(user_B)
        return path
    for i in connections:
        return find_path_to_friend(network, i, connections)

Upvotes: 1

Views: 637

Answers (2)

John Lorenz Inocentes
John Lorenz Inocentes

Reputation: 35

After a day, I finally solved it using recursion but I don't what to do if there is no path found from user_A to user_B.

def find_path_to_friend(network, user_A, user_B):
    res = [user_A]
    connections = network[user_A]
    if user_B in connections:
        res.append(user_B)
        return res
    used = [user_A]
    for i in connections:
        if user_B in network[i]:
            res = res + [i] + [user_B]
            used.append(i)
            return res
    for i in connections:
        return res + find_path_to_friend(network,i, user_B)

Upvotes: 0

AlirezaAsadi
AlirezaAsadi

Reputation: 803

Here is my solution with BFS. You can also write recursive programs for that but as BFS is not usually implemented recursively, I wrote it this way. But if you insist on recursion, I can change it:

from collections import defaultdict


def find_path_to_friend(network, src, dest):
    queue = [src]
    visited = defaultdict(bool)
    path = []
    while len(queue) != 0:
      node = queue.pop(0)
      path.append(node)
      visited[node] = True
      if node in network:
        for adj in network[node]:
          if adj == dest:
            return path + [dest]
          if not visited[adj]:
            queue.append(adj)
    return None

network = {'John': ['Bryant', 'Debra', 'Walter'], 'Bryant': ['Olive', 'Ollie', 'Freda', 'Mercedes'], 'Mercedes': ['Walter', 'Robin', 'Bryant'], 'Olive': ['John', 'Ollie'], 'Debra': ['Walter', 'Levi', 'Jennie', 'Robin'], 'Walter': ['John', 'Levi', 'Bryant'], 'Levi': ['Ollie', 'John', 'Walter'], 'Ollie': ['Mercedes', 'Freda', 'Bryant'], 'Jennie': ['Levi', 'John', 'Freda', 'Robin'], 'Robin': ['Ollie'], 'Freda': ['Olive', 'John', 'Debra']}
print(find_path_to_friend(network, 'John', 'Freda'))
# ['John', 'Bryant', 'Freda']

Here is the recursive approach to eliminate the outer for loop in BFS:

def find_path_to_friend(network, src, dest):
    visited = defaultdict(bool)
    def rec(queue):
      if len(queue) == 0:
        return []
      node = queue.pop(0)
      path = [node]
      visited[node] = True
      if node in network:
        for adj in network[node]:
          if adj == dest:
            return path + [dest]
          if not visited[adj]:
            queue.append(adj)
      return path + rec(queue)
    queue = [src]
    return rec(queue)

Upvotes: 3

Related Questions