Слайд 3: Деревья и графы

Деревья

Сложность операций (сбалансированное дерево):

  • Поиск: O(log n)
  • Вставка: O(log n)
  • Удаление: O(log n)

1. Дерево талантов:

class TalentNode:
    def __init__(self, name, level_req):
        self.name = name
        self.level_req = level_req
        self.children = []
        self.is_unlocked = False

class TalentTree:
    def __init__(self, character_name):
        self.character = character_name
        self.root = self._create_talent_tree()
    
    def _create_talent_tree(self):
        # Создание дерева талантов для персонажа
        root = TalentNode("Базовая атака", 1)
        
        # Первый уровень талантов
        skill = TalentNode("Элементальный навык", 2)
        burst = TalentNode("Взрыв стихии", 4)
        root.children = [skill, burst]
        
        # Созвездия
        skill.children = [
            TalentNode("Улучшенный навык", 20),
            TalentNode("Усиленный навык", 40)
        ]
        
        return root
    
    def unlock_talent(self, talent_name, character_level):
        """Разблокировать талант если выполнены требования"""
        def unlock_recursive(node):
            if node.name == talent_name:
                if character_level >= node.level_req:
                    if not node.parent or node.parent.is_unlocked:
                        node.is_unlocked = True
                        return True
            for child in node.children:
                if unlock_recursive(child):
                    return True
            return False
            
        return unlock_recursive(self.root)

Графы

Сложность операций:

  • Поиск в ширину (BFS): O(V + E)
  • Поиск в глубину (DFS): O(V + E)
  • Поиск кратчайшего пути (Дейкстра): O((V + E) log V)

где V - количество вершин, E - количество рёбер

2. Граф локаций и телепортов:

from collections import defaultdict, deque

class WorldMap:
    def __init__(self):
        self.locations = defaultdict(list)
        self.teleports = set()
    
    def add_connection(self, loc1, loc2, has_teleport=False):
        """Добавить связь между локациями"""
        self.locations[loc1].append(loc2)
        self.locations[loc2].append(loc1)
        if has_teleport:
            self.teleports.add((loc1, loc2))
            self.teleports.add((loc2, loc1))
    
    def find_shortest_path(self, start, end):
        """Поиск кратчайшего пути между локациями (BFS)"""
        queue = deque([[start]])
        visited = set([start])
        
        while queue:
            path = queue.popleft()
            location = path[-1]
            
            if location == end:
                return path
                
            for next_loc in self.locations[location]:
                if next_loc not in visited:
                    visited.add(next_loc)
                    new_path = list(path)
                    new_path.append(next_loc)
                    queue.append(new_path)
        
        return None

    def find_all_teleports(self, start):
        """Найти все достижимые телепорты из точки (DFS)"""
        visited = set()
        
        def dfs(location):
            visited.add(location)
            reachable_teleports = []
            
            for next_loc in self.locations[location]:
                if (location, next_loc) in self.teleports:
                    reachable_teleports.append((location, next_loc))
                if next_loc not in visited:
                    reachable_teleports.extend(dfs(next_loc))
                    
            return reachable_teleports
            
        return dfs(start)

3. Граф элементальных реакций:

class ElementalGraph:
    def __init__(self):
        self.reactions = defaultdict(dict)
        
    def add_reaction(self, element1, element2, reaction):
        """Добавить реакцию между элементами"""
        self.reactions[element1][element2] = reaction
        self.reactions[element2][element1] = reaction
    
    def get_possible_reactions(self, element):
        """Получить все возможные реакции для элемента"""
        return self.reactions[element]
    
    def find_reaction_chain(self, start_element, target_element):
        """Найти цепочку реакций между элементами"""
        visited = set()
        path = []
        
        def dfs(current_element):
            if current_element == target_element:
                return True
            
            visited.add(current_element)
            path.append(current_element)
            
            for next_element in self.reactions[current_element]:
                if next_element not in visited:
                    if dfs(next_element):
                        return True
            
            path.pop()
            return False
            
        if dfs(start_element):
            return path
        return None

Важно помнить:

  • Деревья - частный случай графов (без циклов)
  • BFS гарантирует кратчайший путь в невзвешенном графе
  • DFS может потребовать меньше памяти, чем BFS
  • Для взвешенных графов нужен алгоритм Дейкстры или A*

Задача: Навигация по миру

Создайте систему навигации по игровому миру с использованием графов:

Подсказка: Пример структуры графа:

class Location:
    def __init__(self, name, has_teleport=False):
        self.name = name
        self.has_teleport = has_teleport
        self.points_of_interest = []

class NavigationSystem:
    def __init__(self):
        self.locations = {}
        self.connections = defaultdict(list)
    
    def add_location(self, name, poi=None):
        loc = Location(name)
        if poi:
            loc.points_of_interest.append(poi)
        self.locations[name] = loc
    
    def connect_locations(self, loc1, loc2, distance):
        self.connections[loc1].append((loc2, distance))
        self.connections[loc2].append((loc1, distance))