图的定义
图（graph） 是由一些点（vertex） 和这些点之间的连线（edge） 所组成的；其中，点通常称为顶点（vertex），而点到点之间的连线通常称之为边或者弧（edge）。通常记为G=（V,E）。
要注意的是：线性表可以是空表，树可以是空树，图不可以是空图，图可以没有边，但是至少要有一个顶点。
图的术语
顶点
顶点⼜称节点，是图的基础部分。它可以有⾃⼰的名字，我们称作“键”。顶点也可以带有附加信息，我们称作“有效载荷”。
边
边是图的另⼀个基础部分。两个顶点通过⼀条边相连，表⽰它们之间存在关系。边既可以是单向的，也可以是双向的。如果图中的所有边都是单向的，我们称之为有向图 。
权重
边可以带权重，⽤来表⽰从⼀个顶点到另⼀个顶点的成本。例如在路线图中，从⼀个城市到另⼀个城市，边的权重可以表⽰两个城市之间的距离。
路径
无论是无向图还是有向图，从一个顶点到另一顶点途径的所有顶点组成的序列（包含这两个顶点），称为一条路径。
环
如果路径中第一个顶点和最后一个顶点相同，则此路径称为"环"（或"回路"）。
图的实现
可以通过多种⽅式在Python中实现图的抽象数据类型。你会看到，在使⽤不同的表达⽅式来实现图的抽象数据类型时，需要做很多取舍。有两种⾮常著名的图实现，它们分别是邻接矩阵 和邻接表 。 本节会解释这两种实现，并且⽤Python类来实现邻接表。
邻接矩阵
要实现图，最简单的⽅式就是使⽤⼆维矩阵。在矩阵实现中，每⼀⾏和每⼀列都表⽰图中的⼀个顶点。第 V ⾏和第 W 列交叉的格⼦中的值表⽰从 顶点V 到 顶点W 的边的权重。如果两个顶点被⼀条边连接起来，就称它们是相邻的。
优点
简单。对于⼩图来说，邻接矩阵可以清晰地展⽰哪些顶点是相连的。
缺点
对于存储稀疏数据来说，矩阵并不⾼效。
邻接表
为了实现稀疏连接的图，更⾼效的⽅式是使⽤邻接表。在邻接表实现中，我们为图对象的所有顶点保存⼀个主列表，同时为每⼀个顶点对象都维护⼀个列表，其中记录了与它相连的顶点。在对Vertex 类的实现中，我们使⽤字典（⽽不是列表），字典的键是顶点，值是权重。
优点
能够紧凑地表⽰稀疏图。此外，邻接表也有助于⽅便地找到与某⼀个顶点相连的其他所有顶点。
图的代码实现
1class Graph: 2 3 def __init__(self): 4 self.vertices = {} 5 self.num_of_vertices = 0 6 7 def add_vertex(self, key): 8 new_vertex = Vertex(key) 9 self.vertices[key] = new_vertex 10 self.num_of_vertices = self.num_of_vertices + 1 11 12 return new_vertex 13 14 def get_vertex(self, n): 15 if n in self.vertices: 16 return self.vertices[n] 17 return None 18 19 def contains(self, n): 20 return n in self.vertices 21 22 def add_edge(self, f, t, cost=0): 23 if f not in self.vertices: 24 new_vertex = self.add_vertex(f) 25 26 if t not in self.vertices: 27 new_vertex = self.add_vertex(t) 28 29 self.vertices[f].add_neighbor(self.vertices[t], cost) 30 31 def get_vertices(self): 32 return self.vertices.keys() 33 34 def __iter__(self): 35 return iter(self.vertices.values()) 36 37 38class Vertex: 39 40 def __init__(self, key): 41 self.id = key 42 self.connect_to = {} 43 44 def add_neighbor(self, nbr, weight=0): 45 self.connect_to[nbr] = weight 46 47 def __str__(self): 48 return str(self.id) + "connect to" + str([x.id for x in self.connect_to]) 49 50 def get_id(self): 51 return self.id 52 53 def get_connections(self): 54 return self.connect_to.keys() 55 56 def get_weight(self, nbr): 57 return self.connect_to[nbr]