Udemy——Python数据结构与算法（10）

 课程：【Udemy高分付费课程】Python数据结构与算法 - 终极 Python 编码面试和计算机科学训练营（中英文字幕）_哔哩哔哩_bilibili

Graph

基本代码

class Graph:
    def __init__(self):
        self.adj_list={}
    def print_graph(self):
        for vertex in self.adj_list:
            print(vertex,":",self.adj_list[vertex])

添加顶点 add_vertex

    def add_vertex(self, vertex):
        if vertex not in self.adj_list.keys():
            self.adj_list[vertex] = []
            return True
        return False


my_graph = Graph()

my_graph.add_vertex('A')

my_graph.print_graph()

添加边 add_edge

    def add_edge(self, v1, v2):
        if v1 in self.adj_list.keys() and v2 in self.adj_list.keys():
            self.adj_list[v1].append(v2)
            self.adj_list[v2].append(v1)
            return True




my_graph = Graph()

my_graph.add_vertex(1)
my_graph.add_vertex(2)

my_graph.add_edge(1,2)

my_graph.print_graph()

移除边 remove_edge

    def remove_edge(self, v1, v2):
        if v1 in self.adj_list.keys() and v2 in self.adj_list.keys():
            self.adj_list[v1].remove(v2)
            self.adj_list[v2].remove(v1)
            return True
        return False



my_graph = Graph()

my_graph.add_vertex("A")
my_graph.add_vertex("B")
my_graph.add_vertex("C")

my_graph.add_edge("A","B")
my_graph.add_edge("B","C")
my_graph.add_edge("C","A")

my_graph.remove_edge("A","B")

my_graph.print_graph()

移除顶点remove_vertex

    def remove_vertex(self,vertex):
        if vertex in self.adj_list.keys():
            for other_vertex in self.adj_list[vertex]:#遍历需要删除的顶点相关的边
                self.adj_list[other_vertex].remove(vertex)#一个个删除相关的边
            del self.adj_list[vertex]#删除顶点
            return True
        return False

完整代码

class Graph:
    def __init__(self):
        self.adj_list={}
    def print_graph(self):
        for vertex in self.adj_list:
            print(vertex,":",self.adj_list[vertex])
    def add_vertex(self, vertex):
        if vertex not in self.adj_list.keys():
            self.adj_list[vertex] = []
            return True
        return False
    def add_edge(self, v1, v2):
        if v1 in self.adj_list.keys() and v2 in self.adj_list.keys():
            self.adj_list[v1].append(v2)
            self.adj_list[v2].append(v1)
            return True
    def remove_edge(self, v1, v2):
        if v1 in self.adj_list.keys() and v2 in self.adj_list.keys():
            self.adj_list[v1].remove(v2)
            self.adj_list[v2].remove(v1)
            return True
        return False
    def remove_vertex(self,vertex):
        if vertex in self.adj_list.keys():
            for other_vertex in self.adj_list[vertex]:#遍历需要删除的顶点相关的边
                self.adj_list[other_vertex].remove(vertex)#一个个删除相关的边
            del self.adj_list[vertex]#删除顶点
            return True
        return False


my_graph = Graph()

my_graph.add_vertex("A")
my_graph.add_vertex("B")
my_graph.add_vertex("C")

my_graph.add_edge("A","B")
my_graph.add_edge("B","C")
my_graph.add_edge("C","A")

my_graph.remove_edge("A","B")

my_graph.print_graph()