标签: 图论

2 篇文章

最短路
常用的 最短路 算法有三种:Floyd、Dijkstra、Bellman-Ford(SPFA),三种各有优劣。 Floyd 该算法可以计算任意两点之间的最短路径(全源最短路),算法实现简单,只需要三个for循环,但是时间复杂度高,适合数据量小的稠密图。 同时该算法可以计算负权图(不能有负环)。 该算法实现的本质是动态转移.我们使用邻接矩阵来存储更容…
图的存储和遍历
图的存储是 图论 的基础内容,常用的方式有两种:邻接矩阵与邻接表,前者主要借助数组实现,后者可以采用vector或链式前向星实现。在大部分算法中常使用邻接表做存储。本文介绍了以上三种以及边缘列表等四种方式。