用Python实现一个Graph#

基于邻接列表的存储方式，用Python实现一个Graph，要求实现初始化，添加删除节点和边。

 1class Graph:
 2    def __init__(self):
 3
 4        self.adj_list = {}
 5
 6    def print_graph(self):
 7        for vertex in self.adj_list:
 8            print(vertex, ":", self.adj_list[vertex])
 9
10    def add_vertex(self, vertex):
11
12        if vertex not in self.adj_list:
13            self.adj_list[vertex] = []
14            return True
15        return False
16
17    def add_edge(self, v1, v2):
18
19        if v1 in self.adj_list and v2 in self.adj_list:
20            self.adj_list[v1].append(v2)
21            self.adj_list[v2].append(v1)
22            return True
23        return False
24
25    def delete_edge(self, v1, v2):
26        if v1 in self.adj_list and v2 in self.adj_list:
27            try:
28                self.adj_list[v1].remove(v2)
29                self.adj_list[v2].remove(v1)
30            except ValueError:
31                pass
32            return True
33        return False
34
35    def delete_vertex(self, vertex):
36        if vertex not in self.adj_list:
37            return False
38        for other_vertex in self.adj_list[vertex]:
39            self.adj_list[other_vertex].remove(vertex)
40        del self.adj_list[vertex]
41        return True
42
43
44graph = Graph()
45graph.add_vertex("A")
46graph.add_vertex("B")
47graph.add_vertex("C")
48graph.add_vertex("D")
49graph.add_edge("A", "B")
50graph.add_edge("A", "C")
51graph.add_edge("B", "C")
52print("before delete vertex: ")
53graph.print_graph()
54graph.delete_vertex("D")
55graph.delete_vertex("C")
56print("after delete vertex: ")
57graph.print_graph()