图

概念&性质&实现

一个图是一个二元组G=(V,E),其中：

• V是顶点集合，E是边集合， E ⊆ V × V
• 有向图的边有方向，是顶点的有序对，无向图边无方向。（之后的 有向边 表示为尖括号，< v_i,v_j > 表示v_i到v_j的边，无向边用圆括号表示）
• < v_i,v_j > ∈ E,v_j为v_i的邻接点(无向图的邻接点是双向的)，不考虑顶点到自身的边，无重复的边。
• 完全图：任意两顶点之间都有边（有向图n×(n-1),无向图n×(n-1)/2）|E|≦|V|²,即|E|=O(|V|²)
• 度：一个顶点邻接边的条数，有向图有入度和出度,边数等于所有顶点度数和的一半（有向图要同时算入度和出度）
• 路径：沿着边（有向图边有方向）从一顶点v_i到另一顶点v_j的通路称为v_i到v_j的一条路径，长度为边的条数，环路指起点终点相同，若环路除了起点终点外都不同则称为简单回路，简单路径。
• 有根图：图里的某一顶点到任意其他顶点都有路径，则该图为有根图，该顶点称为根

ADT Graph	一个图的抽象数据类型
Graph(self)	图构造操作，创建一个新图
is_empty(self)