怎么判断图里有负环
用 Bellman-Ford 判断负环的办法是【0】。
Bellman-Ford 在那个反例上
同一张有负权边的图，这次用 Bellman-Ford。运行下面这段程序： def bellman(g, s): INF = 10 ** 9 d = {u: INF for u in g} d[s] = 0 f
两张图，各有没有负环
一张是上一节那个有负权边的图，一张是 0→1:1、1→2:-1、2→1:-1（1 和 2 之间绕一圈是 -2）。运行下面这段程序： def has_neg_cycle(g, s): INF = 10 ** 9 d = {u:
写一个 Bellman-Ford
补全 bellman：把所有边松弛 n-1 轮。在那个有负权边的图上跑，输出整张距离表。
⚠️ 加上负环检测
补全 has_neg_cycle：先松弛 n-1 轮，再多试一轮——还能松弛成功就说明有负环。 验两张图，把两个结果拼起来输出（有负权边那张在前）。
⚠️ 同一对算法，一张图一致、一张不一致
把 Dijkstra 和 Bellman-Ford 都写出来，在两张结构相同的图上各跑一次求 0 到 3 的距离： 把 2→1 那条边设成 +3（全是非负权） 把它设成 -3（有负权边） 各输出 结果一致 或 结果不一致，两个结论用 / 拼
最小生成树是什么
一张连通图的最小生成树是【0】。
生成树有多少条边
n 个顶点的生成树一定有【0】条边。
MST 和最短路差在哪
最小生成树和最短路的区别是【0】。
这五个点连起来最少要多少
主连通块有五个点、五条边：0-1:2 0-2:1 1-3:3 2-4:9 3-4:1。运行下面这段程序，看最小总长和用了几条边： def make(verts): return {u: u for u in verts} def