（1）图由顶点和边构成
（2）图不能没有顶点
（3）任意两个顶点都可能有关系
（1）稠密图与稀疏图（相对的）
（2）有向图：
若顶点之间的边有方向，则称这条边为有向边，也称为弧；如果图中任意两个顶点之间都是有向边，则称该图为有向图。
（3）无向图：
若顶点之间的边没有方向，则称这条边为无向边；如果图中任意两个顶点之间都是无向边，则称该图为无向图。
（1）度：
有向图中有入度和出度，无向图中无入出之分；
（2）权：
与图的边或弧相关的数叫作权，这种带权的图通常称为网。
（3）路径：
两点之间的连线；
路径上第一个点和最后一个相同，则称之为环。
（4）连通图/强连通图
若任意两顶点都是连通的，则图就是连通图，有向则称为强连通图。
图的邻接矩阵存储方式使用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。（边数相对顶点较少的图适用）
邻接表就是把数组与链表相结合的存储方法。
深度优先遍历,也称为深度优先搜索，简称DFS，它从图中某个顶点A出发，访问此顶点，然后从A未被访问的邻接点出发深度优先遍历图，直至图中所有和A有路径相同的顶点都被访问到。
广度优先遍历，又称为广度优先搜索，简称BFS；类似于树的层序遍历。
普里姆算法就是选定一个起点（任一顶点）然后找到它的最小生成树。
（1）初始化U={v}，以v到其他顶点的所有边为侯选边。
（2）重复以下步骤（n-1）次。使其它（n-1）个顶点被加入到U中。
1.从后侯选边中挑选出权值最小的边加入TE，设该边在V-U中的顶点是k，将k加入U中；
2.考察当前V-U中所有顶点j，修改后选编，若（k，j）的权值小于原来的顶点j关联的候选边，则用其替代。
按权值的递增次序选择合适的边来构造；
（1）置U的初始值为V（包含所有顶点），TE的初值为空集
（2）将图中的边按权值从小到大的顺序依次选取；若未形成回路则加入TE；反之，舍弃。
Dijkstra算法是一个按路径长度递增的次序产生的最短路径算法。
如果要求顶点到终点之间的最短距离，根据算法，我们不是一下子就能求出最短路径，而是要一步步求出它们之间顶点的最短路径，过程中都是基于已经求出的最短路径的基础上，求得更远顶点的最短路径，
从而得到最短路径。
Floyd算法是求所有顶点到所有顶点的最短路径
设图中有N个顶点，则对图进行N次更新；每次更新出V[起点][终点]中的起点后的一个点路径即为V[起][中]=V[中][终]。
所谓拓扑排序，其实就是对一个有向图构造拓扑序列的过程。
即不断取出图中入度为零的节点，将该节点从图中删除。
在一个表示工程的带权有向图中，用顶点表示事件，用弧表示活动，用弧上的权值表示活动持续时间，这种用有向图表示活动的网，称之为AOE网，把AOE网中没有入边的的顶点称为始点或源点，把没有出边的顶点称为终点或汇点。
把路径上各个活动所持续的时间之和称为路径长度，从源点到汇点有最大的长度的路径叫关键路径，在关键路径上的活动叫关键活动。
有以下参数：
最早发生时间即某个顶点的最早发生时间。
最晚发生时间即某个顶点的最早发生时间也是每个事件的最晚需要开始的事件。
最早开始时间即某个弧的最早发生时间。
最晚开始时间即某个弧的最晚发生时间。
思维导图：
原文：https://www.cnblogs.com/yyddeegg/p/14832284.html