第四次算法作业

一、判断题

错误，$L\in \mathcal{NP-Hard}$的定义并未要求$L$一定属于$\mathcal{NP}$
无法判断正误，P与NP的关系并没证明。若P$\ne$NP，则正确；若P=NP，则错误，不为空集。
正确
正确

二、最小点集问题

问题分析

本题是连通有向图，并未强调无环，所以不能寻找入度为0的点作为答案。我们通过求强连通分量划分图，每个强连通分量缩点后入度为0的点可以达到其他点，且满足最小性。故我们求入度为0的强连通分量中任取一点组成点集$U$即为最小点集。

算法伪代码

时间复杂度分析

分别在反向图和原图上进行DFS时间复杂度是$O(|V|+|E|)$，缩点后求解入度的时间复杂度是$O(|E|)$，最后一个循环求入度为0的强连通分量中任取一点的时间复杂度为$O(|V|)$，综上本题时间复杂度为$O(|V|+|E|)$；

三、最小环问题

问题分析

（默认题目给出的边权矩阵中若$i,j$之间不可达则$w[i][j]=\infty$）

最小环至少有三个顶点，设编号最大的顶点编号为$k$，环上与$k$相邻两侧的两个点为$i,j$，环表示为$i-k-j-i$，则最小环边权和由$w[i][k]、w[k][j]$以及$i、j$之间的最短距离，求所有点之间的最短距离使用floyd算法。

floyd算法外层循环第$k-1$次结束、第$k$次开始时候，$D[i][j]$表示从前$k-1$个点选点经过，$i$到$j$的最短距离。我们从前$k-1$个点中选出两点$i,j$，两者间的最短路已经求得，加上$w[i][k]、w[k][j]$就是当前环的边权和，不断比较迭代求取最小环边权和。

算法伪代码

时间复杂度分析

初始化部分两层循环的时间复杂度为$O(n^2)$，floyd部分三层循环时间复杂度为$O(n^3)$

四、最短路经过次数问题

问题分析

由于图中边权为正，故我们可以使用 Dijkstra算法 计算从起点$S$到其他所有节点的最短距离。再通过反向 Dijkstra计算从终点$T$到其他所有节点最短距离。

最后遍历所有边$(u,v)\in E$,$dist_S[u]+w[u][v]+dist_T[v]=dist_S[T]$，则该边属于某条最短路径，累加两端点经过次数。遍历结束即可求得所有点的最短路经过次数。

算法伪代码

时间复杂度分析

两次使用 Dijkstra算法 的时间复杂度为$O((|E|+|V|)log(|V|)$,遍历所有边的时间复杂度为$O(|E|)$，综上总的时间复杂度为$O((|E|+|V|)log(|V|)$

五、扩张树问题

问题分析

对每对不直接相连的节点$(u,v)$，计算树$T$连接这两点的路径上的边权的最大值$w_{max}$，为这两点之间添加一条新边，权值为$w_{max}+1$，不能小于等于$w_{max}$，否则会产生替代路径，导致最小树不唯一。

我们先将$T$中边按边权升序排列，利用并查集来高效处理路径最大边权，并使用$num[1\cdots |V|]$记录录当前节点子树中节点的个数，当合并两个子树时，根节点$pu,pv$之间的边一定是当前的最大边，合并节点的同时，子树之间添加无向边$(num[pu]+num[pv]-1)$条，-1是因为根节点之间的连线在最小生成树中。

遍历所有边处理结束之后，得到添加边权和的最小值。

算法伪代码

时间复杂度分析

排序的时间复杂度是$O(|E|\log|E|))$，初始化部分时间复杂度为$O(|V|)$，遍历一遍所有边，计算时间复杂度为$O(|E|)$，因为由于我们的并查集进行了路径压缩，$find$时间复杂度是$O(\alpha(n))$，其中$\alpha(n)$是阿克曼函数的反函数，增长极慢，几乎可以视为常数时间。由于最小生成树的$|E|=|V|-1$，综上时间复杂度是$O(|E|\log |E|)$