定义
图G由两个集合V和E组成，定义为G=（V,E），其中V是顶点的有限非空集合，E是由V中顶点偶对表示的边的集合。
V（G）表示图G的顶点集合
E（G）表示图G的边集合
基本术语
有向图
若每条边都是有方向的，则称该图为有向图
一条有向边由两个顶点组成的有序对，通常用尖括号表示，<i,j>
有向边又称为<font color="#f15a23">弧</font>，边的起点称为<font color="#f15a23">弧尾</font>，边的终点称为<font color="#f15a23">弧头</font>
有向图的边的取值范围是<font color="#f15a23">0~n(n-1)</font>，具有<font color="#f15a23">n(n-1)</font>条边的有向图称为<font color="#f15a23">有向完全图</font>
顶点v的度分为入度ID(v)和出度OD(v)。入度是以该顶点为终点的入边数目，出度是以该顶点为起点的出边数目，<br>该顶点的度等于入度和出度之和
无向图
边均是顶点的无序对，通常用圆括号表示
无向图的边的取值范围是<font color="#f15a23">0~n(n-1)/2</font>，具有<font color="#f15a23">n(n-1)/2</font>条边的无向图成为<font color="#f15a23">无向完全图</font>
顶点v的度定义为以该顶点为一个端点的边的数目，记为D(v)
度数和边数的关系
不管是有向图或是无向图，边数<font color="#f15a23"> e = (D(v1)+D(v2)+D(v3)+···+D(vi))/2 </font>
简单回路
一条路径上除了起点和终点可以为同一个顶点外，其余均不相同<br>
权
边上的数值，边上带权的图称为带权图，带权的连通图称为网络
存储结构
领接矩阵
有向图矩阵中1的个数就是图的边的数量
无向图的邻接矩阵是对称的
时间复杂度<font color="#f15a23">O(n^2)</font>
领接表
找出度容易，入度困难
时间复杂度<font color="#f15a23">O(n+e)</font>
逆邻接表
拓扑排序
术语
顶点表示活动
边表示活动间先后关系的有向无环图(DAG)称为顶点活动网，简称AOV网
AOV网不允许有回路
拓扑序列
所有活动可排成一个线性序列，使得每个活动的所有前趋活动都排在该活动的前面，此序列就是拓扑序列
拓扑排序
由AOV网构造拓扑序列的过程称为拓扑排序
