在有向图中，顶点的度等于该顶点的入度与出度之和，其中顶点v的入度是以v为终点的有向边的条数，记做indev(v)顶点v的出度是以v为起始点的有向边的条数记做outdev（v）
无向图的度等于入度和出度 dev(v) = indev(v) = outdev(v)
路径在图G=(V,E)中，若从顶点vi出发有一组边使其可到达顶点vj，则称顶点vi到vj的顶点序列为从顶点vi到顶点vj的路径
权边附带的数据信息
路径长度对于不带权的图，一条边的路径长度是指该路径上的边的条数
对于带权的图，一条路径的长度是指一条路径的路径长度是指该路径上各个边权值的总和
简单路径与回路如路径上各个顶点 均不重复，则称这样的路径是简单路径，若路径上第一个顶点v1和最后一个顶点vm重合，则称这样的路径为回路或环
子图设图G={V,E}和图G1={V1.E1},若V1属于V且E1属于E，则称G1是G的子图
连通图无向图中，两个顶点之间有路径就是连通的，任一对顶点之间都是连通的则称这个图是连通图
强连通图在有向图中，任意一对顶点vi和vj之间都存在一条从vi到vj的路径，也存在一条从vj到vi的一条路径
生成树一个连通图的最小连通子图称作该图的生成树，有n个顶点的连通图的生成树有n个顶点和n-1条边
图的存储结构
邻接矩阵
邻接表
无向图
有向图
图的遍历深度优先
广度优先
连通分量当无向图为非连通图时，从图中某一顶点出发，利用深度优先搜索或广度优先搜索算法无法遍历图的所有顶点，而只能访问到该节点所在的最大连通子图的所有顶点，这些顶点构成一个连通分量
最小生成树
准则
只能使用图中的边来构造最小生成树
只能使用恰好n-1条边来连接图中的n个顶点
选用的n-1条边不能构成回路
贪心算法在问题求解时，总是做出当前看起来最好的选择，也就是局部最优解
Kruskal算法每次找一条具有最短权值且不再同一连通分量上的边加入生成树
prime算法挨着找
单元最短路径从在带权图的某一顶点出发，找出一条通往另一个顶点的最短路径，最短也即是沿路径各边的权值和最小