共计 1 篇文章

图的常用算法

纸上得来终觉浅,绝知此事要躬行。打算把图的常用算法梳理一遍,加深一下记忆和理解。 简介 前面写了一遍关于图的存储结构和遍历算法的文章,这一篇打算回顾一下图的一些常用算法,包括最小生成树、最短路径算法。这些算法很基础,在生活中经常用到,打算自己动手实现一下,加深理解~~ 最小生成树 生成树的概念:r若图是连通的无向图或强连通的有向图,则从任何一个顶点出发调用一次BFS或者DFS便可访问图中所有的顶点,这种情况下,图中所有顶点加上遍历过程中经历的边构成的子图成为原图的生成树。对于不连通和不是强连通的有向图,这样得到的是生成森林。 最小生成树:对于加权图,权值最小的生成树成为最小生成树。可以用kruskal(克鲁斯卡尔) ...