Top.Mail.Ru
Ответы
Аватар пользователя
Аватар пользователя
Аватар пользователя
Аватар пользователя
Программирование
+2

Программирование Сириус! Помогите пожалуйста!

Нужно составить программу которая оптимально и быстро добавляет вершину в граф или добавляет ребро в граф (между двумя вершинами) или узнает есть ли путь между двумя вершинами! Пожалуйста помогите!

По дате
По рейтингу
Аватар пользователя
Знаток
6мес

Ответы на Сириус курсы ищи в тг канале "Сириус курсы ответы"

Аватар пользователя
Мудрец
9мес
12345678910111213141516171819202122232425262728293031323334
 class Graph: 
    def __init__(self): 
        self.nodes = {} 
 
    def add_node(self, value): 
        if value not in self.nodes: 
            self.nodes[value] = [] 
 
    def add_edge(self, from_node, to_node): 
        if from_node in self.nodes and to_node in self.nodes: 
            self.nodes[from_node].append(to_node) 
            self.nodes[to_node].append(from_node) 
 
    def has_path(self, start, end): 
        visited = set() 
        return self._dfs(start, end, visited) 
 
    def _dfs(self, current, target, visited): 
        if current == target: 
            return True 
        visited.add(current) 
        for neighbor in self.nodes[current]: 
            if neighbor not in visited and self._dfs(neighbor, target, visited): 
                return True 
        return False 
 
graph = Graph() 
for node in ["A", "B", "C", "D"]: 
    graph.add_node(node) 
graph.add_edge("A", "B") 
graph.add_edge("A", "C") 
graph.add_edge("B", "D") 
 
print(graph.has_path("A", "D"))