一. 基本概念：
1.什么叫顶点
2.什么叫弧，弧头（一条弧结束或者指向的地方），弧尾（一条弧发出或背离的地方）
3.什么叫有向图，什么叫无向图？
二. 基本术语
1.无向图边的取值范围是0 到 n(n-1)/2，有向图边的取值范围是0 到 n(n-1)
2.无向完全图：有 n(n-1)/2 条边（每个顶点与其余n-1个顶点都有连线）
3.有向完全图：有n(n-1)条边（每个顶点之间相互连通，是无向完全图的两倍）
4.稀疏图和稠密图：边数少于nlog(n)为稀疏图，反之为稠密图
5.子图 6. 邻接点
7.度，入度和出度：度可以认为是与顶点v相关联的边的数量；出度记作OD(v)，入度记作ID(v)，度记作TD(v)
8.边（或弧）与度的关系：
9.权与网 10.路径与回路
11.连通图 若图中任意两个顶点有路径相同，则该图为连通图
12.生成树
三. 图的存储结构
1. 邻接矩阵表示法：对于有向图，行表示出度，列表示入度；对于无向图，矩阵是个对称矩阵。数据结构见161页
时间复杂度：O(n2)
2. 邻接表表示法：数据机构的定义由三部分组成，表头节点（即顶点），弧节点（即弧），表头数组。其中，表头数组中存放的是顶点，而表头数组的每一个元素后边跟的单链表相当于这个顶点所发出的弧，也就是弧的集合。数据结构见164页
时间复杂度：O(n+e)
四. 图的遍历
1.深度优先搜索DFS：先初始化访问数组，接着判断第一个是否被访问过，没有的话调用DFS函数，每一个顶点都判断一次，就是程序中的for循环，循环顶点个数n次，就能把所有连通子图找到
2.DFS具体内容：首先访问当前顶点数据（visit(v0)），然后标记v0为已访问（visited[v0] = True），找v0的一条边（或弧）： p = g.vertex[v0].firstarc，看这条边（或弧）指向的顶点有没有被访问，若没有，递归调用DFS函数，若有，换下一条边（或弧）： p = p->nextarc，直到这个顶点的所有弧都被搜索完（即所有弧指向的顶点都被遍历过）
3.DFS具体算法在170页
4.广度优先搜索BFS：利用堆栈，先把某一顶点访问输出，然后一次性遍历这个顶点的全部边（或弧）所指向的顶点并访问输出。然后从第一条弧开始，再进行BFS，直到所有顶点被全部访问
五. 图的连通性问题
1.如何判断图的连通性：可以通过DFS中第二个循环的调用次数来判断，若只有一次，则该图是连通的，否则是非连通的。
2.最小生成树：在一个连通图所有生产树中，各边代价之和最小的那棵树叫做最小生成树
普利姆算法：挑选顶点，是将顶点不断放入树的集合，适用于边较多的情况，结合课本177页图7.18进行通俗解释
（2） 定义两个集合，图的集合为全部顶点和边，树的集合为空集
（1） 首先在图中挑一条权值最小的边（如果有多条就随意选一条），将边和边所连接的顶点（两个）放进树的集合中
（3） 再挑选一条边，这个边是以树的集合中顶点为基础的，注意，这时候边必须同时满足两个条件：一是边所连接的两个顶点必须一个在图的集合中，一个在树的集合中，二是在满足第一个条件的情况下，这条边的权重最小。然后将这条边和本来不属于树的集合（即属于图的集合）的那个顶点放入树的集合。
这一条也是与下一个算法的区别所在。
（4）重复上述（3），直到所有顶点都在树的集合中。
克鲁斯卡尔算法：挑选边，将边不断放入树的集合，时间复杂度O(elog2(e))是以2为底的e的对数，结合课本177页图7.18
（1）首先将所有边按权重大小由小到大排列，在本图中是 1，2，3，4，5，5，5，6，6，6
（2）挑选一个最小权重的边，将边和两个顶点放入树的集合。
（3）挑选一个权重次小的边，判断加入这条边后是否形成了回路，若有，则舍弃，挑选其他权重次小的边，若没有，保留并把边和顶点放入树的集合。其中，判断是否形成回路的方法由两个：一是人眼观察，二是判断这条边所连接的两个顶点是否同时在树的集合中。
（4）重复上述步骤，直到所有顶点都在树的集合中。
六. 有向无环图的应用——拓扑排序
1. 基本思想 课本180页
2.邻接表的拓扑排序
（1） 首先遍历所有顶点，求出所有顶点入度
（2） 将入度为零的顶点入栈
（3） 输出一个入度为零的顶点，然后将这个顶点的所有后继顶点入度数组响应减一，如果减一后出现入度为0的顶点，再入栈、
（4） 循环直到栈为空
注：应该也可以用队列实现。
3.邻接矩阵的拓扑排序
计算某顶点入度即计算该顶点所在列值不为空的个数
删除某顶点出度即将这一顶点所在行删除
