圖graph：比樹更一般的結構，由節點和邊構成，樹就是特殊的圖。
class Vertex:
def __init__(self, key):
self.id = key
self.connected_to = {}
self.color = 'white'
self.distance = 0
self.pred = None
self.discovery = 0
self.finish = 0
def add_neighbor(self, nbr, weight=0):
self.connected_to[nbr] = weight
def __str__(self):
return str(self.id) + ' connected to:' + str([x.id for x in self.connected_to])
def get_connections(self):
return self.connected_to.keys()
def get_id(self):
return self.id
def get_weight(self, nbr):
return self.connected_to[nbr]
def set_color(self, color):
self.color = color
def get_color(self):
return self.color
def set_distance(self, dis):
self.distance = dis
def set_pred(self, vert):
self.pred = vert
def get_pred(self):
return self.pred
def get_distance(self):
return self.distance
def set_discovery(self, disc):
self.discovery = disc
def set_finish(self, fin):
self.finish = fin
class Graph:
def __init__(self):
self.vert_list = {}
self.num_vertices = 0
def add_vertex(self, key):
self.num_vertices += 1
new_vertex = Vertex(key)
self.vert_list[key] = new_vertex
return new_vertex
def get_vertex(self, n):
if n in self.vert_list:
return self.vert_list[n]
else:
return None
def __contains__(self, n):
return n in self.vert_list
def add_edge(self, f, t, cost=0):
if f not in self.vert_list:
nv = self.add_vertex(f)
if t not in self.vert_list:
nv = self.add_vertex(t)
self.vert_list[f].add_neighbor(self.vert_list[t], cost)
def get_vertices(self):
return self.vert_list.keys()
def __iter__(self):
return iter(self.vert_list.values())
if __name__ == "__main__":
g = Graph()
for i in range(6):
g.add_vertex(i)
g.add_edge(0, 1, 5)
g.add_edge(0, 5, 2)
g.add_edge(1, 2, 4)
g.add_edge(2, 3, 9)
g.add_edge(3, 4, 7)
g.add_edge(3, 5, 3)
g.add_edge(4, 0, 1)
g.add_edge(5, 4, 8)
g.add_edge(5, 2, 1)
print(g.get_vertex(0))
for v in g:
for w in v.get_connections():
print("(%s, %s)" % (v.get_id(), w.get_id())) 複制