bfs.py

graph = {
    'Yogyakarta': {
        'Bantul', 
        'GunungKidul', 
        'Wates', 
        'Magelang', 
        'Klaten'
    },
    'Bantul': {
        'Wates', 
        'Yogyakarta', 
        'GunungKidul'
    },
    'GunungKidul': {
        'Bantul',
        'Yogyakarta',
        'Klaten',
        'Pacitan'
    },
    'Pacitan': {
        'GunungKidul',
        'Solo'
    },
    'Wates': {
        'Bantul',
        'Yogyakarta',
        'Magelang',
        'Purworejo',
        'Wonosobo'
    },
    'Purworejo': {
        'Wates',
        'Wonosobo'
    },
    'Wonosobo': {
        'Wates',
        'Magelang'
    },
    'Magelang': {
        'Wonosobo',
        'Yogyakarta',
        'Wates',
        'Semarang',
        'Salatiga'
    },
    'Semarang': {
        'Salatiga',
        'Magelang'
    },
    'Salatiga': {
        'Magelang',
        'Klaten',
        'Solo'
    },
    'Klaten': {
        'Salatiga',
        'Yogyakarta',
        'GunungKidul',
        'Solo'
    },
    'Solo': {
        'Salatiga',
        'Klaten',
        'Pacitan'
    },
}

def bfs_algo(graph, start, goal):
    explored = []
    queue = [[start]]
    
    if start == goal: 
        return "Start = Goal"
    
    while queue:
        path = queue.pop(0)
        node = path[-1]
        
        if node not in explored:
            cities = graph[node]
            
            for city in cities:
                new_path = list(path)
                new_path.append(city)
                queue.append(new_path)
                
                if city == goal:
                    return new_path
                
            explored.append(node)
    
    return "jalur tidak ditemukan"