Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0613· openaiHugging Face Suzhen/CodeChat

Реализуй структуру данных граф на python

  1. User

    Реализуй структуру данных граф на python

  2. Assistant

    В Python, граф можно реализовать с помощью класса Graph. Вот пример реализации:

    class Graph:
        def __init__(self):
            self.graph = {}
    
        def add_vertex(self, vertex):
            if vertex not in self.graph:
                self.graph[vertex] = []
    
        def add_edge(self, vertex1, vertex2):
            if vertex1 in self.graph:
                self.graph[vertex1].append(vertex2)
            else:
                self.graph[vertex1] = [vertex2]
    
            if vertex2 in self.graph:
                self.graph[vertex2].append(vertex1)
            else:
                self.graph[vertex2] = [vertex1]
    
        def remove_vertex(self, vertex):
            if vertex in self.graph:
                del self.graph[vertex]
                for key in self.graph:
                    self.graph[key] = [v for v in self.graph[key] if v != vertex]
    
        def remove_edge(self, vertex1, vertex2):
            if vertex1 in self.graph and vertex2 in self.graph:
                self.graph[vertex1] = [v for v in self.graph[vertex1] if v != vertex2]
                self.graph[vertex2] = [v for v in self.graph[vertex2] if v != vertex1]
    
        def get_neighbors(self, vertex):
            if vertex in self.graph:
                return self.graph[vertex]
            else:
                return []
    
        def print_graph(self):
            for vertex in self.graph:
                print(vertex, "->", self.graph[vertex])
    

    Пример использования:

    # Создаем граф
    g = Graph()
    
    # Добавляем вершины
    g.add_vertex(1)
    g.add_vertex(2)
    g.add_vertex(3)
    g.add_vertex(4)
    g.add_vertex(5)
    
    # Добавляем ребра
    g.add_edge(1, 2)
    g.add_edge(1, 5)
    g.add_edge(2, 3)
    g.add_edge(2, 4)
    g.add_edge(3, 4)
    
    # Выводим граф
    g.print_graph()
    
    # Удаляем вершину
    g.remove_vertex(4)
    
    # Выводим граф после удаления вершины
    g.print_graph()
    

    Вывод:

    1 -> [2, 5]
    2 -> [1, 3, 4]
    3 -> [2, 4]
    4 -> [2, 3]
    5 -> [1]
    1 -> [2, 5]
    2 -> [1, 3]
    3 -> [2]
    5 -> [1]
    

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.