基础：按边或弧有无方向，分为有向图和无向图。n个顶点的图，若不计顶点到自己的边，
则无向图最多有n(n-1)/2条边（计到自己的边的话是n(n+1)/2条边），有向图则是最多n(n-1)条边（计到自己的边的话是n^2条边）
若图存在的边数达到最大值，则其为完全图，如果边带有数值，则称为带权图。
若无向图中任意两顶点是连通的，则为连通图。非连通图中，个连通子图称为连通分量。（有向图中为强连通图和强连通分量）
图的表示：二维矩阵，邻接表
顶点表示活动网，即AOV网：
用顶点表示活动，用弧表示活动间的优先关系的有向无回路图称为顶点表示活动的网（Activity On Vertex Network)，简称AOV网。
在网中，若从顶点i到顶点j有一条有向路径，则i是j 的前驱。
拓补排序：删除任意一个入度为0（即没有指向其的有向边）的顶点，从图中删除此顶点（同时删除边），
重复直至找不到入度为0的顶点。结束后如果还存在未被删除的顶点，则图中存在回路。
边表示活动网，即AOE网：
在带权有向图中若以顶点表示事件，有向边表示活动，边上的权值表示该活动持续的时间，这样的图简称为AOE网。
关键路径（临界路径）：在AOE网络中从源点（开始顶点）到汇点（结束顶点）的最长路径。关键路径上的活动为关键活动。
寻找最短路径：Dijkstra（单源点），Floyd（任意两个点之间），复杂度分别为O(n^2)和O(n^3)
Dijkstra：
a.初始时，S只包含源点，即S＝{v}，U={其他点}，然后用源点的边更新最短距离。
b.每次从U中选取一个距离v最小的顶点k，把k加入S中。以k作为中介点更新最短距离。
c.重复步骤b直到所有顶点都包含在S中。
Floyd：
对每对点（i，j），分别用所有顶点作为中介点更新最短距离。
寻找欧拉路径（一笔画）：
无向图: 图连通，所有点都是偶数度，或者只有两个点是奇数度。
当所有点是偶数度时欧拉路起点可以是任意点；当有两个奇数度点时起点必须是奇数度点。
有向图: 图连通，所有点出度=入度，或者有一个点入度-出度=1，有一个点出度-入度=1。
同样，当所有点出度=入度时任意点可作为起点；而后者必须以出度-入度=1的点做起点，入度-出度=1的点做终点。
生成树：一个连通图之中，连接所有顶点的，只有n-1条边的连通子图，其必为一棵树。
算法：Prim算法和Kruskal算法。
Prim算法：
1).输入：一个加权连通图，其中顶点集合为V，边集合为E；
2).初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {},为空；
3).重复下列操作，直到Vnew = V：
a.在集合E中选取权值最小的边<u, v>，其中u为集合Vnew中的元素，而v不在Vnew集合当中
（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
b.将v加入集合Vnew中，将<u, v>边加入集合Enew中；
4).输出：使用集合Vnew和Enew来描述所得到的最小生成树。
时间复杂度：
邻接矩阵、搜索：O(V^2)
二叉堆、邻接表 ：O((V + E) log(V)) = O(E log(V))
斐波那契堆：O(E + V log(V))
Kruskal算法：
（1）原图Graph中所有e个边按权值从小到大排序
（2）循环：从权值最小的边开始遍历每条边，直至图Graph中所有的节点都在同一个连通分量中：
若这条边连接的两个节点于图Graph_new中不在同一个连通分量中，则添加这条边到图Graph_new中
时间复杂度（快排）：elog2(e)（e为图中的边数）