顶点和边之间的差异[图,算法和DS]
Sri*_*nth 4 algorithm graph-theory data-structures
我刚刚开始阅读一本定义Graphs的算法书,如下所示:
图形 - 表示任意对象对之间的关系.图1.8(b)将道路网络建模为图形,其中顶点是城市,边缘是连接城市对的道路.无论何时寻求"网络","电路","网络"或"关系",图形都可能是有问题的对象.
图1.8(b)是这样的:
让我困惑的是以下几行:
......顶点是城市,边缘是连接城市的道路......
Roe*_*ler 13
顶点是点,边是线.因此城市和道路.
我不确定是什么让你感到困惑,但一般情况下,图表确实用于模拟对象之间的连接.
如果您有一堆可能彼此"连接"的对象(顶点),则Graph将是维护它的高级数据结构.我说的是"高级别",因为在实践中你可能需要支持数据结构来维护内存/数据库/文件中的图形:矩阵,链接列表,多对多表等.
如果"方向"不重要,就像上面的情节(即所有道路都是双向的),你有一个"无向图".如果连接方向确实具有重要性(例如,如果城市之间存在单向道路),则您将拥有"有向图",其中每个边实际上都是指向某个方向的"箭头".
如果您对此非常陌生,我建议您阅读相关的维基百科条目.对于一些"真实"的学习,我推荐Cormen等人的"算法导论",这本书是我研究过的,在我看来,这本书是有史以来最好的计算机科学着作之一.