子谦。

入门教程

未归档(52)

/ 注册

全部文章 / 入门教程（共2篇）

负环详解

什么是负环？顾名思义，就是一个所有边的边权和为负数的环出现负环会怎么样？我们知道，一般情况下，图上的最短路都是确定的。但是一旦图上有一个负环，\(s\)到\(t\)的最短路就会不远千里的去覆盖上这个环（只要能够到达），并且不厌其烦的走上一遍又一遍。由于负环的边权和是负的，并且...

入门教程图论负环

2019-08-16

0 556

最小生成树

何为最小生成树？最小生成树就是对于一个连通图，保留若干条边，使图依然联通，且边权和最小。因为\(n\)个点的连通图（以下自动默认为连通图，），最少要有\(n-1\)条边。所以对于一个图的最小生成树，也一定只有\(n-1\)条边。反证一下（此证明仅限于非负边权）：如果这个图的最小生成树...

图论最小生成树入门教程

2019-08-16

0 403