图的应用是考察的重点
主要包括：最小生成树、最短路径、拓扑排序和关键路径。
不会直接考算法设计题，会结合具体的图的例子考察算法中的具体操作，需要熟悉算法的执行过程。
1.最小生成树
关于联通图的生成树： 生成树包含图的全部顶点，并且只包含尽可能少的边 一个图可以有多个不同的生成树 对于一个带权连通无向图，不同的生成树可能有不同的权最小生成树的概念：一个图的所有生成树中权值最小的一个或几个生成树
最小生成树有以下这些性质
1.一个图可能有多个不同的最小生成树，即最小生成树的树形不唯一
关于这点有两个特殊情况
当图中各个边的权值各不相同时，则这个图只能有一个最小生成树
若无向连通图的边数等于顶点数-1，则这个图的最小生成树就是它本身
2.最小生成树只是树形不唯一，但是其权值和是唯一的
即一个图的各个最小生成树的权值和相同
3.最小生成树中，边数=顶点数-1
最小生成树的构造算法
算法通用模板：
GENERIC_MST(G){
T=NULL;
while T未形成一颗生成树 //没有包括全部顶点
do 找一条权值最小且加入树中后不会产生回路的边e
将e加入生成树T中
}
prim算法
prim算法可以概括为：不断选择**合适的点**扩大最小生成树 算法步骤： 1.选择任意一个顶点加入最小生成树T 2.继续选择一个与当前的T中顶点距离最小（也就是对应的边权值最小）的顶点，将这个顶点和对应的边加入T中 3.以此类推，直到T中包括图中的所有顶点，算法结束算法描述：
void prim(G,T){
//考试中不会考算法设计，熟悉这个算法中的细节即可
T=空集;//初始化空树
U={w};//初始的点集
while((V-U)!=空集){//算法结束的标志：T与G的点集相同
选出(u,v),其中u∈U,v∈(V-U),且(u,v)在满足这个条件的前提下权值尽量小;
T=T+{(u,v)};//并入新边
U=U+{v};//添加新结点
}
}
算法分析：
时间复杂度为O(V^2)，可以看出prim算法时间复杂度只与点的多少有关，与边数无关
适合用于边稠密的图
kruskal算法
这个算法是通过不断**选择合适的边**来构造生成树 选边的标准：选择未被选过并且权值最小的边，并且**这条边的两个顶点落在不同的连通分量上** 直到T中所有顶点都在同一个连通分量上。void Kruskal(V,T){
T=V;//对生成树的初始化，这时T里只有顶点，没有边
numS=n;//连通分量的个数，初始时有n个
while(numS>1){//算法结束的标志：numS=1
找到权值最小的边(u,v);
if(u和v处在不同的连通分量中){
T=T+{(u,v)};//将(u,v)并入T中
numS--;
}
}
}
时间复杂度为O(E * log2(E))
适合用于边稀疏并且顶点较多的图。
2，最短路径
1.用广度优先算法求非带权图中的单源最短路径![[1685953554162.jpg]]
2.dijkstra算法求单源最短路径问题
与1不同，这个算法适合用于带权图的情形
![[Pasted image 20230606165653.png]]