六讲贯通C++图的应用之六 活动网络(AOV、AOE)(1)(3)

总结

不同于前面的链表和树，在图这里，储存方法不是重点，我们更多的注意力放在了算法上。我在写程序的时候，也尽量做到了算法和储存方法无关。然而算法实际上就是现实问题的抽象，如果我们的常识所不及，我们也就没有办法来介绍算法，反过来说，几乎遇不到的问题，我们也不会对它的算法感兴趣。

因此，在图的算法里面，由铺设管道引出了最小生成树，由提高通信、交通网络可靠性引出了关节点和重连通分量，由地图寻径引出了最短路径，由工程预算引出了关键路径。这些恐怕是我们能够理解的全部了，如果再来一个电气网络计算，没点物理知识恐怕是要完。

但即使这样，上面的各个算法仍然离我们很远，我们大多数人恐怕永远都不会知道管道是怎么铺的。我想，这里面除了最短路径能引起大多数人的兴趣之外，其他的就只能走马观花的看看罢了。这也使得图的学习很像“聋子的耳朵”，真正接触到图的用途的人不多，并且即使用到图，也仅仅是个别的算法。

正像数据结构教学的通病一样，学无所用常常导致学无所成，前面的链表、树好歹还能做点什么东西出来，到了图这里，除了做个导游系统，我们也做不出别的什么了。写到这里很无奈，但我也只能是无奈……

那么，学完了图，我们应该掌握什么呢，是上面零散的算法吗?我的看法是，不是。我觉得我们更应该知道那些算法是怎么“创造”出来的，如果遇到了类似的问题，能不能“派生”出新的算法。因此，我觉得《数据结构算法与应用-C++语言描述》这本书，将图的最小生成树、最短路径、拓扑排序算法放到了贪婪算法里讲解，是一种更为合理的安排。