不同顺序的 3D 数组遍历 [英] 3D Array Traversal in Different Order
问题描述
我有一个 3D 节点数组，我想从数组的中间节点开始遍历它，然后向角移动......像这样
I've a 3D array of nodes and I want to traverse it by starting from the middle node of array, and moving towards corners ... Like this
等等......但出于可视化的目的，我以2D形式显示，但实际上它是3D，所以当我们离开时，我们将在每个偶数迭代中创建一个立方体，并在每个奇数迭代中创建一个球体.但
and So on ... but for visualization purposes I've shown in 2D but actually it is 3D, so when we move away we will creating a Cube on every even iteration and creating a sphere on every odd iteration. but
它将在 3D 中看起来像
It will look like in 3D as
希望我已经以最好的方式表达了我的问题......请帮助我构建一个算法，我尝试了很多但没有找到正确的路径......我熟悉C，C++, C#, JAVA 所以如果我能得到这些语言的答案，我将不胜感激，否则只需分享我将实现它的算法......
Hopefully I've stated my question in a best possible way... please help me to build an algorithm, I've tried a lot but didn't get the right path ... I'm familiar with C,C++, C#, JAVA so I'll be grateful if I can get the answer in these languages, otherwise just share the algorithm I'll implement it ...
已
下一次迭代
推荐答案
其工作方式是创建一个图形，其中每个单元格都是一个节点.由于图形具有立方体的形状，因此每个节点都必须有一个到它的 X、Y 和 Z 邻居的链接.首先要做的是通过向程序提供邻居节点之间的关系来创建图.例如，我们应该给程序一个输入，说节点 0 连接到节点 1，等等……在告诉程序节点如何连接以形成立方体之后，很容易开始考虑遍历这个图.一种流行的遍历图的算法称为广度优先遍历(BFT)，该算法允许以分布式方式遍历节点.例如，如果你有一棵树，它是一种图形，使用 BFT 遍历它会先打印根，然后一次打印每个级别，所以它有点像通过公平地传播从起点开始遍历树分支.在您从中间到角落遍历立方体的示例中，这正是 BFT 可以为您做的.在这种情况下，BFT 将从中间开始，逐个表面开始遍历节点，由于我们是从中间点开始，因此传播将采取球体形状.
The way this works is by creating a graph, where each cell is a node. Since the graph have the shape of a cube, therefore each node must have a link to its X, Y and Z neighbour. The first proceeder to do is creating the graph by feeding the program the relation between neighbour nodes. For instance, we should give the program an input saying that node zero is connected to node one, etc ... After telling the program about how the nodes are connected to form the cube, it's easy to start thinking about traversing this graph. A popular algorithm for traversing graphs is called Breadth First Traversal (BFT), this algorithm allows nodes to be traversed in a distributed way. For example, if you have a tree, which is a type of graphs, traversing it using BFT will print the root first, then prints each level at a time, so it's kind of traversing the tree from the starting point by propagating fairly in all branches. In your example of traversing a cube starting from the middle to the corners is exactly what BFT can do for you. In this case, BFT will start from the middle and start traversing the nodes surface by surface, and since we are starting from the middle point, the propagation will take a sphere shape.
什么是 BFT
BFT 需要使用一个名为 Queue 的数据结构，它是一个先进先出列表.首先，我们向队列提供起点，并将其标记为已访问，这意味着它已进入队列，并且在遍历过程中的任何时间都不允许进入.然后我们将应用一个progresser，它将轮询头节点，将其标记为已访问，并提供其未访问的邻居.相同的过程一次又一次地进行，直到所有节点都被访问，因此队列为空.我们在这里使用队列的原因是允许以平衡的方式遍历节点.在这个立方体遍历程序中，提供中间节点将通过从队列中轮询它并提供它的 6 个邻居(在 >= 3x3x3 立方体的情况下).然后将按进入顺序轮询这些邻居节点中的每一个，并且将在队列末尾提供它们的邻居.继续运行直到没有未访问的邻居离开.
What is BFT
BFT needs to use a data structure called Queue which is a First In First Out list. First we offer to the queue the starting point and we mark it as visited, meaning that it has entered the queue and is not allowed to enter any time later in the traversal. Then we will apply a proceeder that will poll the head node, mark it as visited, and offer its unvisited neighbours. The same process is done again and again until all nodes are visited and therefore the queue is empty. The reason we use a queue here is to allow nodes to be traversed in balanced way. In this cube traversal program, offering the middle node will follow by polling it out from the queue and offering its 6 neighbours (in case of >= 3x3x3 cube). Then each of those neighbours node will be polled by order of entrance and their neighbours will be offered at the end of the queue. The proceeder keep running until no unvisited neighbour is left.
代码说明:
首先我们需要知道立方体的大小.一个 3x3x3 的立方体意味着我们应该创建 27 个节点.我创建了一个名为 generateCubeGraph() 的方法，它将生成输入字符串以通知程序有关邻居节点之间的关系.此方法的返回输出示例:
Code explanation:
First we need to know the size of the cube. A cube of 3x3x3 mean we should create 27 nodes. I created a method called generateCubeGraph() which will generate input string to inform the program about the relation between neighbour nodes. An example of return output by this method:
27 54
0 1
0 3
0 9
1 2
1 4
1 10
etc..
前两个值分别是节点数和邻居节点之间的链接/边数.其余的线是节点之间的连接.例如第一行告诉节点0连接到节点1，等等......注意这是一个无向图，所以当程序存储节点之间的链接时，它存储从节点x到节点y以及从节点y到节点 x.
生成输入后，build() 方法会将节点之间的链接存储在邻接列表中.创建另一个数组来计算为每个节点创建了多少条边.
存储链接后，我们需要做的就是使用 BFT 算法遍历立方图.检查上面关于它是如何工作的描述并阅读实现以进一步了解它是如何工作的.
打印方法是可选的，它们有助于实现和描述代码的工作方式.
The first two values are respectively, the number of nodes, and the number of links/edges between neighbour nodes. The rest of the lines are the connection between nodes. For example the first line tells that node zero is connected to node 1, etc... Note that this is an undirected graph, so when the program store the link between nodes, it store from node x to node y and from node y to node x.
After generating the input, build() method will store the links between nodes in an adjacency list. Another array is created to count how many edge have been created for every node.
After storing the links, all we need to do is traverse the cube graph using BFT algorithm. Check above description on how it works and read the implementation for more understanding of how it works.
The printing methods are optional, they help in the implementation and in the description of how the code is working.
下图显示了我如何为 3x3x3 节点的立方体中的节点编号.此外，我添加了一个例子来展示一个节点如何链接到它的 X、Y 和 Z 邻居(在图片的底部).
This picture below shows how I numbered the nodes in a cube of 3x3x3 nodes. Moreover, I have added an example to show how a node is linked to its X, Y and Z neighbour (At the bottom of the picture).
Java 中 3 x 3 x 3 节点的 Cube 代码如下:(您可以通过修改 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("
");
}
/**
* 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
", current, current+1);
link++;
}
// If not last col
if(col != SIDE-1){
links += String.format("%d %d
", current, current+SIDE);
link++;
}
// If not last row
if(row != SIDE-1){
links += String.format("%d %d
", current, current+(SIDE*SIDE));
link++;
}
}
}
}
// return #Nodes, #Edges, links ...
return String.format("%d %d
%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 中的工作方式(您必须按照节点处理顺序为节点着色，您可以通过查看每个节点编号位置的层输出来获取节点编号):
Link to verify how it works in 3D (You have to colour the nodes in the node processed order, and you can get the node number by looking at the layer output for each node number position):
这篇关于不同顺序的 3D 数组遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
