图的定义
图（Graph）是一个由顶点的有穷非空集合和顶点之间的边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
图中的数据元素我们称为顶点（Vertex）
图中不允许没有顶点，若V是顶点的集合，则强调顶点集合V有穷非空。
图中任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以为空
各种图的定义
无向边：若顶点vi到vj之间的边没有方向，则称这条边是无向边（Edge），用无序偶对（vi,vj）来表示。如果图中任意两个顶点之间的边都是无向边，则称该图是无向图
有向边：若从顶点vi到vj的边有方向，则称这条边为有向边，也称为弧（Arc）用有序偶<vi, vj>来表示，vi称为弧尾（Tail），vj称为弧头（Head）。如果图中任意两个顶点之间的边都是有向的，则称该图为有向图（Directed graphs）。
简单图：若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。
无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图是无向完全图。含有n个顶点的无向完全图有n(n-1)/2条边。
有向完全图：在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。含有n个顶点的有向完全图有n(n-1)条边
有很少条边或弧的图称为稀疏图，反之为稠密图。
有向图的边或弧具有与他相关的数字，这种与图的边或弧相关的数叫权（weight）。这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图常称为网。
假设有两个图G = (V,{E})和g = (v,{e}),如果V包含v 且 E 包含e,则称g为G的子图。
图的顶点与边之间的关系
对于无向图G = (V,{E})，如果（V,v）属于E,则称V和v互为邻接点（Adjacent），顶点v的度（Degree）就是和v关联的边的数目，记为TD(v)
对于有向图G = (V,{E}),如果弧<V,v>属于E，则称顶点V邻接到顶点v，V,v相关联。以顶点V为头的弧的数目称为V的入度（InDegree），记为ID(v)；以V为尾的弧的数目称为V的出度（OutDegree），记为OD(V)；顶点V的度为TD(V) = ID(V) + OD(V)。
路径的长度是路径上的边或弧的数目
第一个顶点到最后一个顶点相同的路径称为回路或环（Cycle）。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。
连通图相关术语
在无向图G中，如果从顶点V到v有路径，则称V和v是连通的。如果对于图中任意两个顶点vi,vj属于V，vi和vj都是连通的，则称G 是连通图（Connected Graph）
无向图中的极大连通子图称为连通分量
- 要是子图
- 子图要是连通的
- 连通子图含有极大顶点数
- 具有极大顶点数的连通子图包含依附于这些顶点所有边
在有向图G中，如果对于每一对vi,vj属于V，vi不等于vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。有向图中极大强连通子图称做有向图的强连通分量
连通图的生成树是一个极小的连通图，它含有图中全部的n个顶点，但只有构成一个数的n-1 条边。
如果一个图有n个顶点和小于n-1条边，则是非连通图，如果多于n-1条边，必定构成一个环。
如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一颗有向树。
一个有向图的生成森林由若干棵有向树组成，含有图中的全部顶点，但只有足以构成若干棵不相交的有向树的弧
图的存储结构
邻接矩阵
图的邻接矩阵（Adjacency Matrix） 存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。
邻接表
把数组和链表结合的方式叫做邻接表
