不同顺序的3D数组遍历
Zia*_*ani 8 arrays algorithm 3d multidimensional-array
我有一个3D节点阵列,我想从数组的中间节点开始遍历它,然后向角落移动......就像这样
等等...但是出于可视化目的,我已经在2D中显示但实际上它是3D,所以当我们离开时,我们将在每个偶数迭代创建一个立方体并在每个奇数迭代上创建一个球体.但
它看起来像3D一样
希望我已经以最好的方式陈述了我的问题...请帮我构建一个算法,我已经尝试了很多但没有找到正确的路径......我熟悉C,C++,C# ,JAVA所以如果我能用这些语言得到答案,我将不胜感激,否则只需分享我将实现它的算法......
编辑:
下一次迭代
其工作方式是创建一个图表，其中每个单元格都是一个节点。由于图具有立方体的形状，因此每个节点必须有到其 X、Y 和 Z 邻居的链接。第一个要做的事情是通过向程序提供邻居节点之间的关系来创建图。例如，我们应该给程序一个输入，说明节点 0 连接到节点 1，等等……在告诉程序节点如何连接以形成立方体之后，很容易开始考虑遍历该图。一种流行的图遍历算法称为广度优先遍历（BFT），该算法允许以分布式方式遍历节点。例如，如果你有一棵树，它是一种图，使用 BFT 遍历它会首先打印根，然后一次打印每个级别，所以它是一种从起点遍历树的方式，在所有树中公平传播分支机构。在您从中间开始到角落遍历立方体的示例中，这正是 BFT 可以为您做的事情。在这种情况下，BFT将从中间开始并开始逐面遍历节点，并且由于我们是从中间点开始，因此传播将呈球形。
什么是 BFT
BFT 需要使用一种称为队列的数据结构，它是先进先出列表。首先，我们向队列提供起点，并将其标记为已访问，这意味着它已进入队列，并且不允许在遍历中的任何时间进入。然后我们将应用一个进程来轮询头节点，将其标记为已访问，并提供其未访问的邻居。一遍又一遍地执行相同的过程，直到所有节点都被访问，因此队列为空。我们这里使用队列的原因是为了允许节点以平衡的方式遍历。在此立方体遍历程序中，提供中间节点后，将从队列中轮询它并提供其 6 个邻居（在 >= 3x3x3 立方体的情况下）。然后，每个邻居节点将按进入顺序进行轮询，并且它们的邻居将在队列末尾提供。进程继续运行，直到没有未访问过的邻居为止。
代码解释：
首先我们需要知道正方体的大小。3x3x3 的立方体意味着我们应该创建 27 个节点。我创建了一个名为 的方法generateCubeGraph()，它将生成输入字符串来通知程序有关邻居节点之间的关系。此方法的返回输出示例：
27 54
0 1
0 3
0 9
1 2
1 4
1 10
etc..
前两个值分别是节点数和邻居节点之间的链接/边的数量。其余的线是节点之间的连接。例如，第一行告诉节点 0 连接到节点 1，等等...请注意，这是一个无向图，因此当程序存储节点之间的链接时，它存储从节点 x 到节点 y 以及从节点 y 到节点 x。
生成输入后，build()方法会将节点之间的链接存储在邻接列表中。创建另一个数组来计算为每个节点创建了多少条边。
存储链接后，我们需要做的就是使用 BFT 算法遍历立方图。检查上面关于它如何工作的描述，并阅读实现以更好地了解它如何工作。
打印方法是可选的，它们有助于实现和描述代码如何工作。
下图显示了我如何对 3x3x3 节点立方体中的节点进行编号。此外，我还添加了一个示例来展示节点如何链接到其 X、Y 和 Z 邻居（在图片底部）。
下面是 JAVA 中 3 x 3 x 3 节点的立方体的代码：（您可以通过修改 sideNode 变量来更改每边的节点数）
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
/**
* Driver class: Build, traverse, print linkage
*/
public class CubeDriver {
public static void main(String[] args) {
// How many nodes per side
int sideNodes = 3;
Cube cube = new Cube();
cube.build(cube.generateCubeGraph(sideNodes));
System.out.println("Node execution order: ");
cube.BFT();
System.out.println("Nodes links:");
dcube.printAL();
System.out.println("Nodes on Layers:");
cube.printLayers(sideNodes);
}
}
/**
* Cube creator
*/
class Cube{
// Adjacency list (Hold node's neighbors)
int al[][];
// Degree array (Count how many neighbor per node)
int dl[];
int NODES;
int EDGES;
int MAX_LINKS = 6; // No node can have more than 6 links in all case
/**
* Create the links between nodes based on the input generated by generateCubeGraph() mehtod
*/
public void build(String input){
Scanner scan = new Scanner(input);
// Get #Nodes and #Edges
NODES = scan.nextInt();
EDGES = scan.nextInt();
// Initialize 2D Array and Degree array
al = new int[NODES][MAX_LINKS];
dl = new int[NODES];
// Store the link between nodes
for(int i=0; i<EDGES; i++){
int node1, node2;
node1 = scan.nextInt();
node2 = scan.nextInt();
int node1Neighbors = dl[node1]++;
int node2Neighbors = dl[node2]++;
al[node1][node1Neighbors] = node2;
al[node2][node2Neighbors] = node1;
}
}
/**
* Traverse using Breadth first traversal method
* Plug the middle node in a queue, then poll it and put it's neighbor, then poll each neighbor and put their neighbors if not visited already
*/
public void BFT(){
int visited[] = new int[NODES];
Queue<Integer> q = new LinkedList<Integer>();
int VISITED = 1;
// Plug the center node
int middle = NODES/2;
q.offer(middle);
visited[middle] = VISITED;
while(!q.isEmpty()){
int polledNode = q.poll();
System.out.print(polledNode + " ");
for(int i=0; i < dl[polledNode]; i++){
int neighbor = al[polledNode][i];
if(visited[neighbor] != VISITED){
q.offer(neighbor);
visited[neighbor] = VISITED;
}
}
}
System.out.println("\n");
}
/**
* Input generator for a cube
*/
public String generateCubeGraph(int n){
int SIDE = n; // Number of nodes in one side of the cube
String links = ""; // Holds the final output
int link = 0; // Counts the number of links
for(int row=0; row<SIDE; row++){
for(int col=0; col<SIDE; col++){
for(int depth=0; depth<SIDE; depth++){
int current = depth + (col * SIDE) + (row * SIDE * SIDE);
// If not last depth
if(depth != SIDE-1){
links += String.format("%d %d\n", current, current+1);
link++;
}
// If not last col
if(col != SIDE-1){
links += String.format("%d %d\n", current, current+SIDE);
link++;
}
// If not last row
if(row != SIDE-1){
links += String.format("%d %d\n", current, current+(SIDE*SIDE));
link++;
}
}
}
}
// return #Nodes, #Edges, links ...
return String.format("%d %d\n%s", SIDE*SIDE*SIDE, link, links);
}
/**
* Prints the links between each nodes. Used for debugging only
*/
public void printAL(){
for(int node = 0; node < NODES; node++){
System.out.print(String.format("Node %3d linked to nodes: ", node));
for(int neighbor = 0; neighbor < dl[node]; neighbor++){
System.out.print(String.format("%3d ", al[node][neighbor]));
}
System.out.println();
}
System.out.println();
}
/**
* Print 3D layers nodes number
* */
public void printLayers(int sideNode){
for(int layer=0; layer<sideNode; layer++){
System.out.println("Layer: " + layer);
for(int row = 0; row < sideNode; row++){
for(int col = 0; col < sideNode; col++){
int current = layer + (col * sideNode) + (row * sideNode * sideNode);
System.out.print(String.format("%3d ", current));
}
System.out.println();
}
System.out.println();
}
}
}
输出
Node execution order:
13 4 10 12 14 16 22 1 3 5 7 9 11 19 15 21 17 23 25 0 2 6 8 18 20 24 26
Nodes links:
Node 0 linked to nodes: 1 3 9
Node 1 linked to nodes: 0 2 4 10
Node 2 linked to nodes: 1 5 11
Node 3 linked to nodes: 0 4 6 12
Node 4 linked to nodes: 1 3 5 7 13
Node 5 linked to nodes: 2 4 8 14
Node 6 linked to nodes: 3 7 15
Node 7 linked to nodes: 4 6 8 16
Node 8 linked to nodes: 5 7 17
Node 9 linked to nodes: 0 10 12 18
Node 10 linked to nodes: 1 9 11 13 19
Node 11 linked to nodes: 2 10 14 20
Node 12 linked to nodes: 3 9 13 15 21
Node 13 linked to nodes: 4 10 12 14 16 22
Node 14 linked to nodes: 5 11 13 17 23
Node 15 linked to nodes: 6 12 16 24
Node 16 linked to nodes: 7 13 15 17 25
Node 17 linked to nodes: 8 14 16 26
Node 18 linked to nodes: 9 19 21
Node 19 linked to nodes: 10 18 20 22
Node 20 linked to nodes: 11 19 23
Node 21 linked to nodes: 12 18 22 24
Node 22 linked to nodes: 13 19 21 23 25
Node 23 linked to nodes: 14 20 22 26
Node 24 linked to nodes: 15 21 25
Node 25 linked to nodes: 16 22 24 26
Node 26 linked to nodes: 17 23 25
Nodes on Layers: // Check the picture above to know what the below layers are.
Layer: 0
0 3 6
9 12 15
18 21 24
Layer: 1
1 4 7
10 13 16
19 22 25
Layer: 2
2 5 8
11 14 17
20 23 26
验证它在 3D 中如何工作的链接（您必须按照节点处理顺序对节点进行着色，并且可以通过查看每个节点编号位置的层输出来获取节点编号）：