一、最小生成树和最短路径的区别

最短路径问题

最短路径是把两点之间路径最短的问题，应用如导航，两个地方怎么走距离最短。可以存在到不了的情况。

这个问题是说，如何找到从某个特定的节点出发，通向其他节点的最短路径。它只着眼于点与点之间的路径问题，并不关注整个图，也就意味着对一个节点运行算法的结果与另一个节点的结果之间没有多少关系。

比如说，可以把城市的路口看作图的节点，把公路看做边，综合长度、拥堵程度等指标作为边的权重，就可以通过Dijkstra算法计算出从城市一点到另一点的最短路线。

最小生成树问题

最小生成树是把连通的图的所有顶点连起来路径之和最小的问题，即生成树总权值之和最小。

即在一个连通的图里，如何去除图里的边，使得剩余的边仍能连接所有的节点，且这些边的权重之和最小。显然，满足这个要求的图不可能存在环，也就是一棵树，因此叫做生成树。这种算法与上面的相反，着眼于整个图的结构，并不关心某两个节点之间的路径是不是最短的。

这种算法的应用也很广泛，比如说有一个快递公司，每天都要开车把快递送到城市里的不同地点，怎样走才能不重复地经过每个节点，还能让总时间最短呢？我们就可以用Kruskal这样的最小生成树算法，找到一个最小生成树，只需要按这个路线走就行了。

延伸阅读：

二、Verilog的抽象层次

Verilog的抽象层次是指，要实现一个功能，我们可以怎么用怎样的Verilog语言去描述他。Verilog一共有五种抽象层次，分别是：系统级、算法级、寄存器级、门级、开关级，其中系统级和算法级又称作是行为级，寄存器级又称为数据流级，门级和开关级又称作是结构级。

行为级是通过模块之间的数据流描述系统实现，并不关心具体的硬件层次。这一层次抽象层次较高，描述也最灵活。这一层次和C语言时类似的，语法逻辑上十分相似。

数据流级是通过通过描述模块内部或者模块之间，数据在寄存器间的流动和数据处理。数据流级抽象层次较低，一般数据流级描述可以进行逻辑综合。和C语言不同，数据流级描述涉及到具体的线路连接（如线网驱动和寄存器驱动）。

结构级是用具体的逻辑门（如与、或、非门等）和具体的开关器件实现模块功能。这一抽象层次级别最低，灵活性也较差。但是，同一个逻辑表达式表达的功能，用不同的电路结构去实现，最终的电路面积功耗速度稳定性等性能参数是完全不同的。这一层次上考虑的问题，C语言是完全不会考虑的。

总言之，Verilog有着比C语言更加丰富的抽象层次，这使得进行代码优化时，Verilog不仅可以像C语言一样，从算法逻辑上进行优化，灵活性高，还可以从电路设计实现的角度进行优化，更大程度上提高电路性能。

上一篇

char*t和char t［10］的区别?

下一篇

Partial application 和 currying 在实际编程中的区别是什么?