一、图1.基本概念
图是一种抽象的数学结构，研究抽象对象之间的一类二元关系及其拓扑性质。而在计算机的数据结构领域中，图则是一种复杂的数据结构。
一个图是一个二元组 G = (V, E)，其中：
V 是非空有穷的顶点集合，也可以有空图。
E 是顶点偶数对的集合，即两个顶点组成一条边。
V 中的顶点也被称为图 G 的顶点，E 中的边也被称为图 G 的边。
图分为无向图和有向图。在无向图中边没有方向，用圆括号表示，例如(v1, v2)。在有向图中边是有方向的，用尖括号表示，例如<v1, v2>。
2.一些概念和性质1.完全图完全图：任意两个顶点之间都有边的图。完全图有如下性质：
n 个顶点的无向完全图有 n*(n-1)/2 条边。
n 个顶点的有向完全图有 n*(n-1) 条边。
2.路径对于图 G=(V, E)，如果存在顶点序列如 Vi0，Vi1，...，Vin，使得 (Vi0，Vi1）、(Vi1，Vi2）、...(Vin-1，Vin）都是图的边，则说从 Vi0 到 Vin 存在路径，并称 Vi0，Vi1，...，Vin 是从顶点 Vi0 到 Vin 的一条路径。对于路径，还有如下概念：
路径的长度就是该路径上边的数量。
成环的路径就是起点和终点相同的路径。
简单路径就是不含环的路径，也就是说除了该路径的起点和终点可能相同外，其他顶点均不相同。
需要注意的是，从一个顶点到另一个顶点，可能存在路径，也可能不存在路径。如果存在路径，还可能存在多条路径。
3.连通图1）连通
如果在一个无向图中存在 vi 到 vj 的路径，则称这两个顶点连通。
2）连通无向图
如果无向图 G 中任意两个顶点之间都连通，则称 G 为连通无向图。
3）强连通有向图
如果对于有向图 G 中任意两个顶点 vi 和 vj ，从 vi 到 vj 连通并从 vi 到 vj 也连通，则称 G 为强连通有向图。
4）带权图
如果图 G 中的每条边都被赋予一个权值，则称 G 为带权图，可以是有向图也可以是无向图。边的权值可用于表示实际应用中与顶点之间的关联的有关信息，带权的连通无向图也被称为网络。
3.抽象数据类型图作为一种复杂的数据结构，可以给图定义如下操作：
ADT Graph:
Graph(self) # 用于创建一个图
is_empty(self) # 判断图是否为空
get_vertex(self) # 获取顶点数量
get_edge(self) # 获取边的数量
add_edge(self, v1, v2) # 添加一条 v1 到 v2 的边
has_edge(self, v1, v2) # 是否有 v1 到 v2 的边
print(self) # 打印图
二、图的表示和实现1.邻接矩阵表示法
图的最基本表示方法是邻接矩阵表示法。邻接矩阵是表示图中顶点间邻接关系的矩阵，对于一个有 n 个顶点的图 G=(V, E)，其邻接矩阵是一个 n*n 的矩阵，图中每个顶点对应于矩阵里的一行和一列。
最简单的邻接矩阵是以0/1为元素的，即对于图 G 的邻接矩阵，当 Aij 为0时，表示顶点 vi 和 vj 无边， 当 Aij 为1时，表示顶点 vi 和 vj 有边。邻接矩阵表示了图中的顶点数量和顶点间的关系（即边），每个顶点对应矩阵的一对行列下标，听过一对下标就可以确定图中的某条边是否存在了。
要使用 Python 实现一个图类，可以使用列表（list）或者 numpy 模块里的矩阵（array），这里就用列表来实现，即用 list 为元素的 list，具体代码如下：
1#使用邻接矩阵2classGraph:3def__init__(self, v):4 self.V =v5 self.E =06 self.data = [[0 for_inrange(v)]for_inrange(v)]78defis_empty(self):9"""10判断图是否为空11:return:12"""13return self.V ==01415defget_vertex(self):16"""17获取顶点数量18:return:19"""20returnself.V2122defget_edge(self):23"""24获取边的数量25:return:26"""27returnself.E2829def add_edge(self, v1, v2):30"""31向图中增加一条v1到v2的边32 :param v1: 顶点33 :param v2: 顶点34:return:35"""36ifnotself.data[v1][v2]:37 self.data[v1][v2] = 138 self.data[v2][v1] = 139 self.E += 14041def has_edge(self, v1, v2):42"""43判断是否有v1到v2的边44 :param v1: 顶点45 :param v2: 顶点46:return:47"""48return self.data[v1][v2] == 14950defprint(self):51"""52将图打印出来53:return:54"""55foriinself.data:56print(i)