图 - 最短路径(Dijkstra 和 Frolyd)
图 - 最短路径(Dijkstra 和 Frolyd) "最短路径问题是图论研究中的一个经典算法问题,旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。" 从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条,如何找到一条路径使得沿此路径上各边上的权值总和达到最小,例:公交查询系统。 问题解法: 1. 求从某个源点到其余各点的最短路径

2022年8月18日
大约 7 分钟
数据结构基础 - 知识体系
数据结构基础 - 知识体系 数据结构的作用 数据结构实际上可以理解为数据在计算机中的存储和使用结构。如果借助C++容器的概念,数据结构可以认为是以某种特定的布局方式存储数据的容器。 这种“布局方式”决定了数据结构对于某些操作是高效的,而对于其他操作则是低效的。首先我们需要理解各种数据结构,才能在处理实际问题时选取最合适的数据结构。不同的数据结构适用于不同的应

2022年7月2日
大约 4 分钟
图 - 最小生成树(Kruskal和Prim)
图 - 最小生成树(Kruskal和Prim) "在给定一张无向图,如果在它的子图中,任意两个顶点都是互相连通,并且是一个树结构,那么这棵树叫做生成树。当连接顶点之间的图有权重时,权重之和最小的树结构为最小生成树!" 在实际中,这种算法的应用非常广泛,比如我们需要在n个城市铺设电缆,则需要n-1条通信线路,那么我们如何铺设可以使得电缆最短呢?最小生成树就是为

2022年7月2日
大约 3 分钟
图 - 拓扑排序(Topological sort)
图 - 拓扑排序(Topological sort) 什么是拓扑排序? 维基百科对于拓扑排序有如下定义: "a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every direct

2022年7月2日
大约 6 分钟