什么数据结构适合用来表示有道口的铁路？

Question

我试图将铁路中的路径表示为数据结构，但我很难表示道口。

这感觉像是一个图问题，但与常规图相比是有区别的。铁路道口是连接到其他三个顶点的顶点。A，B和C。但是，在铁路系统中，图是按方向遍历的。因此，您可以采用路径B -> turnout -> A和C -> turnout -> A，但不能采用路径B -> turnout -> C。

有没有一种(图)数据结构，允许用方向表示路径？

这种数据结构将为软件系统提供基础，以实现小型模型铁路的自动化。

Answer 1

可以将道岔表示为2个顶点，每个顶点对应于道岔的每个状态。因此，如果您有源A和目的地B和C，以及可以在B和C之间切换的turnout您将有2个顶点用于此turnout：TB和TC。此外，您还将拥有以下边缘：A->TB、TB->B、A->TC、TC->C

这允许您从A -> TB -> B和A -> TC -> C旅行。而且，由于您将在TB和TC之间没有边缘-您将不能直接从B -> C旅行

Answer 2

每条路径可以看作是一个顶点，两条路径之间的连接可以看作是一条边。

B ->

一个

C ->

这可以表示为Go图中的图，

看一下下面的内容，在您的示例中，存在来自B -> A和C -> A的定向连接。这可以在地图中表示如下。

graph := map[string][]string{
    "B": []string{"A"},
    "C": []string{"A"},
}

映射中的每个键代表定向连接的起始路径。对应key数组中的每个值都是目标路径。