1. 图的表示：邻接矩阵和邻接表
- 邻接矩阵：大小为|V|的二维数组，对于每条边(u, v)，置A[u][v]=1或该边的权值
- 邻接表：对每一个顶点，使用一个表存放所有邻接的顶点，并将所有顶点的表头存放在一个大小为|V|的表中
2. 拓扑排序：如果存在一条到
的路径，那么在排序中
出现在
的前面，要求图为有向无圈图，且排序结果不唯一
- 将没有入边（入度为0）的顶点放入一个队列中（可以使用邻接表的表头存放顶点的入度）
- 队列进行出队，并出队顶点的边删除，并将这些边连接的其他顶点的入度减1
- 重复上述操作，直到队列为空
3. 无权最短路径：给定图G=(V, E)和一个顶点s，找出从s到G中每一个顶点的最短路径
- 广度优先搜索(BFS)：按层处理顶点，距开始顶点最近的顶点首先被遍历，最远的顶点最后被遍历
- 深度优先搜索(DFS)：从顶点s开始，递归的处理所有与s邻接的顶点，对每一个可能的分支路径深入到不能再深入为止，而且每个顶点只能访问一次
4. Dijkstra算法：该算法分阶段进行，在每个阶段，选择一个顶点v，它在所有未知顶点中具有最小的带权路径，并认为从s到v的最短路径是已知的，然后更新其他与v邻接的顶点的带权路径，直到所有顶点已知（图无圈时可以按拓扑顺序选择顶点改进算法，因为选择某个顶点时，它没有从未知顶点发出的进入边，则它的距离不会再降低）
5. Floyd算法：解决任意两点间的最短路径，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包
- 算法思想：从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。所以，我们假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置Dis(i,j) = Dis(i,k) + Dis(k,j)，这样一来，当我们遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离。
- 算法描述：
1️⃣从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大
2️⃣对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它 -
十字交叉法：给出矩阵，其中矩阵A是邻接矩阵，而矩阵Path记录u,v两点之间最短路径所必须经过的点
5. 最小生成树：由图中所有顶点和连接所有顶点的边构成，且其总价值最低
- Prim算法：构建一个已知顶点集K和一个未知顶点集U，初始状态K为空集，U=V；在U中随机选取一个顶点v从U中删除，并放入K中；选择以K中顶点为端点，另一端在U中的且边上权值最低的边添加到最小生成树中，并将U中的对应顶点移动至K中，重复操作直到U为空集
- Kruskal算法：连续的选择权值最小且不构成圈的边添加到最小生成树中，即选择两端不连通且权值最小的边
