如何在某些数据结构中表示奇怪的图

2024-04-03

表示图的一种简单方法是使用以下形式的数据结构:

{1:[2,3],
 2:[1,3],
 3:[1,2]}

该字典中的键是节点,边由它们连接到的其他节点的列表表示。如果链接不对称,此数据结构也可以轻松表示有向图:

{1:[2],
 2:[3],
 3:[1]}

我对图论了解不多,所以我要提出的可能已经有一个简单的解决方案,但我不知道要寻找什么。我遇到过一种情况,我认为图表在某种程度上是有方向的,具体取决于您所在的节点以及您来自的节点。为了说明这一点,我有一张图:

想象一下,您在卡丁车中沿着 A 边超速行驶,在节点 1 处,您向左转至 B 边。由于速度太快,当您到达节点 3 时,您被迫继续行驶到 F 边。但是,如果您来自边 F,您将能够继续前往边 E 或 B。很明显,节点 3 连接到 1 和 2,但是您是否可以从该节点到达它们取决于哪一个你来自的方向。

我想知道是否有一个图论概念来描述这一点和/或是否有一个简单的数据结构来描述它。虽然我将用 python 编写代码,但我会听取任何合理适用的语言的建议。

编辑: 我试图发布一张图片来配合此操作,但我不确定它是否会显示。如果不是,这里有一个链接image http://www.image-share.com/ijpg-721-238.html

编辑2: 我应该已经很清楚了。发布的图像是完整图表的一部分,其中 A、D 和 F 的屏幕外有更多节点。


这可以表示为有向图 http://en.wikipedia.org/wiki/Directed_graph.

图中的节点可以表示为图中的两个节点。 将节点视为代表街道特定一侧的位置 - 边缘就像入站和出站车道。

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

如何在某些数据结构中表示奇怪的图 的相关文章