1.图的基本概念：
? ? （1）有向图：
?? ?（2）无向图：
?? ?（3）简单图：
- ?? ??? ?不存在重复边；（比如上图中顶点4到顶点1有两条边）
- ?? ??? ?不存在顶点到自身的边。（环）
?? ?（4）多重图：存在重复边且存在顶点到自身的边。
?? ?（5）完全图（简单完全图）：
- ?? ??? ?对于无向图，任意两个顶点之间都存在边。
?? ??? ??? ?n*(n-1) /2
- ?? ??? ?对于有向图，任意两个顶点之间都存在方向相反的两条边。
?? ??? ??? ?n*(n-1)
?? ?（6）子图、生成子图：
- ?? ??? ?子图：如下图中的顶点和边数都是上图的子集。
- ?? ??? ?生成子图：如下图中的顶点集合和上图的是相等的，边集则是第一幅图的子集。
?
?? ?（7）连通、连通图：
- ?? ??? ?连通：顶点i到顶点j有路径。
- ?? ??? ?连通图：图中任意两个顶点之间都是连通的。
- ?? ??? ?极小连通子图：图连通且边数最少的子图。
- ?? ??? ?强连通图：图中任意两个顶点都连通，即从顶点i到顶点j和从顶点j到顶点i都存在路径。
- ?? ??? ?强连通分量：极大强连通子图。
?? ??? ??? ?强连通图只有一个强连通分量（本身），非强连通图可以有多个。
?? ?（8）生成树：包含图中全部顶点的一个极小连通子图。
?? ?（9）顶点的度、入度和出度：
?? ??? ?顶点1的度为2，顶点2的度为3（1，3，5）。
?? ??? ?图中所有顶点的度之和等于边数的两倍。
?? ??? ?入度、出度：顶点1的入度为1，出度为2。
?? ??? ?有向图的全部顶点的入度之和与出度之和相等，并且等于边数。
?? ?（10）边的权和网：
?? ??? ?权：边上带有数值。
?? ?（11）路径、路径长度和回路：
?? ??? ?顶点1到顶点4的路径长度为2。（1->3，3->4）
?? ??? ?回路：路径上的开始点与结束点为同一个顶点。（如上图中的顶点1、4）?
2.图的存储结构：
? ? （1）邻接矩阵法：
? ? ? ? 不带权无向图：
?? ??? ?不带权有向图：
?? ??? ?带权有向图：?? ?（2）邻接表法：
? ? ? ? 不带权无向图：V顶点，E边。
?? ??? ?不带权有向图：
?? ??? ?邻接表存储特点：
3.图的遍历：
? ? （1）广度优先：类似于二叉树的层序遍历算法。（队列实现）
?? ?（2）深度优先：类似于树的先序遍历。（栈实现）
?? ?
4.图的应用：
? ? （1）最小生成树：带权连通无向图中，所有生成树中权值之和最小的生成树。
?? ??? ?Prim算法：
?? ??? ?Kruskal算法：
?? ??? ?最小生成树是唯一的，并且边数=顶点数-1。
?? ?（2）最短路径：
?? ?（3）拓扑排序：（不唯一）152364
