import pandas as pd
import numpy as np

# <<<CELL>>>

from collections import deque

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F', 'G'],
    'D': [],
    'E': [],
    'F': [],
    'G': []
}

stack = []
visited = set()
stack.append('A')
visited.add('A')
print('\nDFS Traversal')

while stack:
  node =  stack.pop()
  print(node,end=" ")
  for neighbour in graph[node]:
    if neighbour not in visited:
      visited.add(neighbour)
      stack.append(neighbour)

# <<<CELL>>>

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F', 'G'],
    'D': [],
    'E': ['H'],
    'F': [],
    'G': []
}

#Aim to reach F from A


visited = set()
queue = deque()
parent = {}
queue.append('A')
visited.add('A')
print('BFS Traversal A->F')
target = 'F'
found = False
parent['A']= None

while queue:
  node = queue.popleft()
  if node==target:
    found = True
    break
  for neighbour in graph[node]:
    if neighbour not in visited:
      parent[neighbour] = node
      visited.add(neighbour)
      queue.append(neighbour)

if found:
  path = []
  node = target
  while node is not None:
    path.append(node)
    node = parent[node]

path.reverse()
for p in path:
  print(p,end=" ")

# <<<CELL>>>

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F', 'G'],
    'D': [],
    'E': ['H'],
    'F': [],
    'G': []
}

#Aim to reach F from A

visited = set()
stack = []
parent = {}
stack.append('A')
visited.add('A')
print('DFS Traversal A->F')
target = 'F'
found = False
parent['A']= None

while stack:
  node = stack.pop()
  if node==target:
    found = True
    break
  for neighbour in graph[node]:
    if neighbour not in visited:
      parent[neighbour] = node
      visited.add(neighbour)
      queue.append(neighbour)

if found:
  path = []
  node = target
  while node is not None:
    path.append(node)
    node = parent[node]

path.reverse()
for p in path:
  print(p,end=" ")

# <<<CELL>>>

def path_weight(graph, path):
    return sum(graph[path[i]][path[i+1]] for i in range(len(path)-1))

def bfs_path(graph, start, goal):
    visited = {start}
    queue = deque([[start]])
    while queue:
        path = queue.popleft()
        node = path[-1]
        if node == goal:
            return path
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(path + [neighbor])
    return None

def dfs_path(graph, start, goal, visited=None, path=None):
    if visited is None:
        visited = set()
    if path is None:
        path = [start]
    visited.add(start)
    if start == goal:
        return path
    for neighbor in graph[start]:
        if neighbor not in visited:
            result = dfs_path(graph, neighbor, goal, visited, path + [neighbor])
            if result:
                return result
    return None

bfs_result = bfs_path(graph, 'a', 'z')
dfs_result = dfs_path(graph, 'a', 'z')

print("BFS path:", " -> ".join(bfs_result))
print("BFS total weight:", path_weight(graph, bfs_result))

print("DFS path:", " -> ".join(dfs_result))
print("DFS total weight:", path_weight(graph, dfs_result))
