标签图论下的文章

自学最小生成树

生成树是和原图点集相同，树形态的子图。树是一个整体（霍格沃兹除外），而图可能不连通。生成树一定是连通的，不连通的图可以组成生成森林。最小生成树即边权之和最...

2020 年 08 月 24 日

为了复习一下BFS和邻接表，出了这么一道水题。要注意的是，输入中可能存在很多环——所以DFS的处境就很鸡肋了——那么用BFS。题目描述很久很久以前，有一只...

2020 年 08 月 21 日

先引用一段度娘的话：Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法名称...

2020 年 07 月 15 日

最短路问题是图和树问题中常见的问题，Dijkstra算法又是一种较为常见的最短路算法，所以...好用，嗯嗯，好用单源最短路径问题...在一张有向图上，节点...

2020 年 07 月 14 日

对于图或树，一般有邻接矩阵和邻接表两种储存方式。其中，邻接矩阵更加直观，a[i][j]表示第i个点到第j个点的权值，值为0则表示无边；邻接表更适合以更小的...

2020 年 07 月 09 日