<b>最小生成树</b>
实质上是带权无向图。最小生成树是权值之和最小的生成树，不唯一
普利姆(Prim)算法
特点：只与顶点个数n有关，与边的个数e无关，适用于稠密图
V为连通网顶点集，U为生成树顶点集，TE为生成树边集
U={v₀}，TE=∅
计算U到其他顶点的最小代价，将该顶点纳入U，边纳入TE
重复上一步骤，知道U=V
克鲁斯卡尔(Kruskal)算法
特点：只与边的个数n有关，与顶点个数e无关，适用于稀疏图
不构成环条件下，每次选最小的边(做题技巧，不要过程时使用)
时间复杂度： <b>Prim <font color="#c41230">O(n²)</font>，Kruskal <font color="#c41230">O(e log₂e)</font></b>
<b>最短路径</b>
两顶点之间带权路径长度最短的路径
<b>Dijkstra</b>算法
初始化数组
从顶点<b>V</b>中选出<b>vⱼ，</b>满足<b>dist[j]=Min{dist[i], vⱼ∈V}</b>
<b>vⱼ</b>为当前所求最短路径终点，另求<b>S∪{j} </b>
修改此时从<b>v₀出发到集合V-S</b>上任意顶点<b>vₖ</b>最短路径的长度
若<b>dist[j]+arcs[j][k]<dist[k]</b>则令<b>dist[k]=dist[j]+arcs[j][k]; path[k]=j</b>
重复2、3、4步骤n-1次，知道S中包含全部顶点
<b>Floyd</b>算法
使用邻接矩阵<b>A⁽⁰⁾、A⁽¹⁾、A⁽²⁾······、A ⁽ⁿ⁾</b>
第n次计算从起点经过n-1个顶点到达某个顶点最小带权之和
若到某个顶点有更小的权值之和，则替换之前的值并修改路径
直到到达终点
<b>拓扑排序</b>
有向无环图：一个有向图中不存在环，简称DAG图
AOV网：用DAG图表示一个工程，顶点为活动，有向边为优先级，这样的网络为AOV网
由一个有向无环图的顶点组成的序列，满足一下要求，则称该图的拓扑排序
要求：
若顶点A在B的前面，则图中不存在从B到A的路径
每个顶点只出现一次
<b>关键路径</b>
AOE网：用DAG图表示一个工程，顶点代表事件，边代表活动，这样的网络为AOE网
AOE网只有一个入度/出度为0的顶点，称为<b>源点</b>/<b>汇点</b>
问题：
整个工程完工需要多多长时间
哪些活动影响工程进度？
事件(顶点)：最早发生时间<b>Ve(i)</b>，最晚发生时间<b>Vl(i)</b>
活动(边)a(i,j)：最早开始时间<b>e(i,j)</b>，最晚发生时间 <b>l(i,j)</b>
整个工程完工的时间就是终点的最早发生的时间，关键路径就是路径长度最长的路径。
算法：
对顶点进行拓扑排序<i>（*是任意前驱事件）</i>
计算<b>Ve(j)</b>
<b>Ve(1)=0</b>
<b>VE(j)=max{Ve(*)+a(*,j)}</b>
计算<b>Vl(i)</b>
<b>Vl(n)=Ve(n)</b>
<b>Vl(i)=min{Vl(*)-a(i,*)}</b>
计算<b>e(i,j)</b>和 <b>l(i,j)</b>
<b>e(i,j)=Ve(i)</b>
<b>l(i,j)=Vl(j)-a(i,j)</b>
结论：工程总用时<b>Ve(n)</b>，关键活动是<b>e(i,j)= l(i,j)</b>的活动<b>a(i,j)</b>
