四、如果将输入的图用邻接矩阵来表示，并修改算法来应对此种形式的输入，请问BFS的运行时间将是多少？如果要写代码，请用go语言。

三、证明：使用单个位来存放每个结点的颜色即可。这个论点可以通过证明将算法第18行的伪代码删除后，BFS过程生成的结果不变来得到。如果要写代码，请用go语言。...

二、请计算出在图22-3所示无向图上运行广度优先搜索算法后的 d 值和 π 值。这里假定结点 u 为算法所用的源结点。

一、请计算出在有向图22-2(a)上运行广度优先搜索算法后的d值和π值。这里假定结点3为算法所用的源结点。如果要写代码，请用go语言。

六、多数以邻接矩阵作为输人的图算法的运行时间为$Ω(V^{2})$，但也有例外。给定图$G$的邻接矩阵表示，请给出一个$O(V)$时间的算法来判断有向图$G$是否存在一个通用汇点(universal sink)。通用汇点指的是入度为$|V|-1$但...

五、有向图$G=(V,E)$的平方图是图$G^{2}=(V,E^{2})$，这里，边$(u,v)∈E^{2}$当且仅当图$G$包含一条最多由两条边构成的从$u$到$v$的路径。请给出一个有效算法来计算图$G$的平方图$G^{2}$。这里图$G$既可以以邻接链表表示...

四、给定多图$G=(V,E)$的邻接链表(多图是允许重复边和自循环边的图)，请给出一个时间为$O(V+E)$的算法，用来计算该图的“等价”无向图$G^{'}=(V,E^{'})$的邻接链表表示。这里$E^{'}$是将$E$中的冗余边和...

三、有向图 $G=(V,E)$ 的转置是图 $G^{T} =(V,E^{T})$，这里 $E^{T} ={(v,u)∈ V times V$:(u,v)∈ E}$因此，图 $G^{T}$ 就是将有向图$G$中所有边的方向反过来而形成的图。对于邻接链表和邻接矩阵两种表示，请给出从图$G$...

二、给定一棵有 7 个结点的完全二叉树的邻接链表，请给出等价的邻接矩阵表示。这里假设结点的编号为从 1~7 。如果要写代码，请用go语言。

一、给定有向图的邻接链表，需要多长时间才能计算出每个结点的出度(发出的边的条数)？多长时间才能计算出每个结点的入度(进入的边的条数)？如果要写代码，请用go语言。...