如何通过将图形表示为邻接表来创建蜂窝网络拓扑
How can I create a Honeycomb network topology by representing a graph as an adjacency list
给定 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]
为了构建图表，除了您描述的过程之外，还有几个不同的选项需要考虑：
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 - 它意识到它应该 "also connect to" 的节点是它已经完成的节点（即它回到了这个级别开始的地方），所以向后移动到 N13 并为下一层创建节点，然后从那里继续。
所以这需要一些智慧来知道哪个节点 "also connect to"，等等，但它必须遵循常规的一般模式，因此要直接 implement/maintain。
选项 2）这两种方法（您的和我的选项 (1)）都非常适合根据固定模式进行初始设置，但是如果您还需要（现在或将来）在要求 ？例如，假设您需要允许通过按顺序删除节点来构建图形（但始终连接到至少一个预先存在的节点）：N1、N2、N6、N5、N8、N15、N16、N9
让我们考虑最后一个，将 N9 添加到 N16。查看图表，我们可以立即看到它也必须连接到 N2 - 但我们如何对其进行编程？有两个选项（再次！！）：
选项 2a) 当添加每个节点（例如 N9 到 N16）时，我们递归地遍历整个树，累积偏移量（我们离 N9 有多远 up/down 和 left/right）直到我们找到一个匹配的节点。恕我直言，复杂且耗时
选项 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）。坐标也可以方便地用于其他用途（显示等）。
给定 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]
为了构建图表，除了您描述的过程之外，还有几个不同的选项需要考虑：
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 - 它意识到它应该 "also connect to" 的节点是它已经完成的节点（即它回到了这个级别开始的地方），所以向后移动到 N13 并为下一层创建节点，然后从那里继续。
所以这需要一些智慧来知道哪个节点 "also connect to"，等等，但它必须遵循常规的一般模式，因此要直接 implement/maintain。
选项 2）这两种方法（您的和我的选项 (1)）都非常适合根据固定模式进行初始设置，但是如果您还需要（现在或将来）在要求 ？例如，假设您需要允许通过按顺序删除节点来构建图形（但始终连接到至少一个预先存在的节点）：N1、N2、N6、N5、N8、N15、N16、N9
让我们考虑最后一个，将 N9 添加到 N16。查看图表，我们可以立即看到它也必须连接到 N2 - 但我们如何对其进行编程？有两个选项（再次！！）：
选项 2a) 当添加每个节点（例如 N9 到 N16）时，我们递归地遍历整个树，累积偏移量（我们离 N9 有多远 up/down 和 left/right）直到我们找到一个匹配的节点。恕我直言，复杂且耗时
选项 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）。坐标也可以方便地用于其他用途（显示等）。