概念

完全图：任何两个节点之间都有边。
连通图：任何两个节点之间都有路径。

数据结构	描述	优点
邻接矩阵法	用一个数组存顶点，用一个矩阵存边	直观
邻接表法	用一个数组存顶点，每个顶点维护一个它指向的节点链表	找节点出去的边容易
逆邻接表法	用一个数组存顶点，每个顶点维护一个指向它的节点的链表	找节点进入的边容易
十字链表法	结合邻接表与逆邻接表，相当两套链表用同样的节点	找节点出边和入边都容易
邻接多重表法	每个顶点都维护一个与它相邻的边的链表，边节点是各顶点共用的	存无向图，易于对边操作

图搜索算法

深度优先搜索：节点优先级=父节点优先级-1，越深的节点优先级越小，越优先。
广度优先搜索：节点优先级=父节点优先级+1，越深的节点优先级越大，浅节点比深节点优先。

最短路径-Dijkstra算法：优先探索累积权值最小的那条路径，这是贪心算法，结果并不一定是全局最优的。
最短路径-Floyd算法：

第一次迭代，所有节点绕行1号节点。
第二次迭代，所有节点绕行2号节点。
...
第n次迭代，所有节点绕行n号节点。

最终会得到所有节点到所有节点的最小路径。

最小生成树-Prim算法：非常类似于Dijkstra算法，总是获取离定点最近的那个点。
最小生成树-Kruskal算法：最小生成树的各边权值之和最小，所以搜索时总是朝着权值最小的边扩展生成树。

①每个定点出现且只出现一次
②若A定点排在B的前面，则在图中不存在B到A的路径。

①只有在某定点所代表的事件发生后，从该定点出发的各有向边所代表的活动才能开始；
②只有在进入某定点的各有向边所代表的活动都已结束时，该定点所代表的事件才能发生。