如何在十二面体图中编写邻接表？

Question

它有：

20 个顶点 30条边 G{20,30}

如何为每个顶点 1,2,...20 生成邻接表？ V1 与 2 和 3 相连 v2 与 1 和 4 相关联 v3 与 1 和 5 链接 ??

有公式吗？这是一个游戏项目，不知道我是否漏掉了数学 class 之类的东西？我应该学习什么才能理解解决方案？

Answer 1

我认为 link 列表通常是手动构建的。但是，您可以查看 https://en.wikipedia.org/wiki/Dodecahedron 中 2:1 pyritohedron 的特殊情况，以了解如何从立方体变为十二面体。（另请查看 "Cartesian Coordinates" 部分中的动画 gif）

这告诉我们，可以通过插入新的顶点平分每个立方体的 12 条边来构造十二面体。然后插入连接这些新顶点的新边，使它们沿交替方向平分立方体 6 个面的每个面。

我认为这种理解会有所帮助，无论是对于构建算法，还是只是帮助您构建手动 link 列表。

这当然只处理顶点-links，以找到每个顶点的坐标，参见例如How to generate/calculate vertices of dodecahedron?

Answer 2

手动构建：

int adjs[] = { 1, 4, 7, 0, 2, 9, 1, 3, 11, 2, 4, 13, 0, 3, 5, 4, 6, 14, 5, 7, 16, 0, 6, 8, 7, 9, 17, 1, 8, 10, 9, 11, 18, 2, 10, 12, 11, 13, 19, 3, 12, 14, 5, 13, 15, 14, 16, 19, 6, 15, 17, 8, 16, 18, 10, 17, 19, 12, 15, 18 };

for (int i = 0, int j = 0; i < 20; i++, j = i * 3) {
    caves[i] = Cave(i);
    for (int c = j; c < j + 3; c++) {
        caves[i].adjsListy.addAdj(adjs[c]);
    }

我在此处的解决方案中找到了帮助：https://rosettacode.org/wiki/Hunt_The_Wumpus/C%2B%2B

如何在十二面体图中编写邻接表？

How to code adjacency lists in a dodecahedron graph?

graph

adjacency-list