java - 如何通过将图表示为邻接列表来创建蜂窝网络拓扑

Question

给定 N 个节点，我想用它构建一个蜂窝网络图。它可以是一个完整的节点，如 SMn，其中节点数由 6n^2 给出，也可以具有超过严格的 SMn，例如 50 个节点，其比 SM2 多 26 个节点。目标是构建一个邻接表，其中每个节点的最大度数为 3。

给定 50 个节点来创建蜂窝网络，我从队列中选择前 6 个节点并将其视为二分图。 N1、N3和N5是黑色节点，N2、N4和N6是白色节点。构建初始邻接表，创建一个循环 N1->N2->N3->N4->N5->N6 ->N1，称之为第 1 层节点。

有空间添加 6 个新节点，六边形的每个顶点各一个，因此我从队列中再获得 6 个节点，3 个黑色和 3 个白色，并连接相反的节点并将它们称为第 2 层。类似地，继续直到我已经用尽了所有节点并更新了邻接表。需要一些有关如何改进此算法的帮助，或者任何有关如何实现此算法的建议都很棒![在此处输入图像描述][1]

Answer 1

为了构建图表，除了您描述的过程之外，还需要考虑几个不同的选项:

1) 想象一个小机器人在追踪一条连续的线。所以它从N1->N2->N3->N4->N5->N6开始。然后当转到N1时意识到它已经到达了这一点，因此在其连续线N1->N8中移出，然后继续:

• N8->N15->N16->N9(也连接到 N2)
• N9->N18->N17->N10(也连接到 N3)
• ......
• ....N24->N7(也连接到 N6)
• N7->N14->N13->N8 - 它意识到它应该“也连接到”的节点是它已经完成的节点(即它回到了这一级别开始的位置)，因此返回到 N13并为下一个级别创建节点，然后从那里继续。

因此，这需要一些智慧来知道“还连接到”哪个节点等，但它必须遵循常规的一般模式，因此易于实现/维护。

选项 2) 两种方法(你的和我的选项 (1))都非常适合根据固定模式进行初始设置，但是如果您还需要(现在或将来)按需添加新节点怎么办？例如，假设您需要允许通过删除序列中的节点来构建图(但始终连接到至少一个预先存在的节点):N1、N2、N6、N5、N8、N15、N16、N9

让我们考虑最后一个，将 N9 添加到 N16。查看该图，我们可以立即看到它也必须连接到 N2 - 但我们如何对其进行编程呢？有两个选项(再次!!):

选项2a)当添加每个节点(例如N9到N16)时，我们递归地遍历整个树，累积偏移量(距离N9上/下和左/右有多远)，直到找到匹配的节点。恕我直言，复杂且耗时

选项 2b)一旦放置了每个节点，它就可以根据它所附加的节点的坐标计算其在图中的坐标 - 例如，我们的序列变为:

N1(0,0)、N2(1,0)、N6(-1,-1)、N5(0,-2)、N8(-1,1)、N15(0,2)、N16 (1,2), N9(2,1)

现在，当添加节点 N9 时，我们显然可以计算它应附加到的任何节点的坐标 - (1,0) 和 (3,1) - 因此只需直接迭代列表寻找任何这些坐标处的现有节点(因此立即找到 N2)。坐标也可以方便地用于其他用途(显示等)。