不同的顺序三维数组遍历 [英] 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的邻居。第一proceeder做的是通过喂食程序邻居节点之间的关系产生的曲线图。例如，我们应该给程序的输入话说，节点零连接到节点之一，等等......讲述的节点如何连接形成立方体程序后，可以很容易地开始考虑通过遍历这个图形。一个流行的算法遍历图被称为广度优先遍历（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需要使用称为队列的数据结构是一种先进先出列表。首先，我们提供给队列的起点，我们将其标记为已访问，这意味着它已进入队列，并且不允许在遍历以后输入的任何时间。然后，我们将采用proceeder将轮询头节点，将其标记为参观，并提供其未访问过的邻居。直到所有的节点都访问过相同的过程被一次又一次地进行，因此，该队列是空的。我们在这里使用一队列中的原因是为了允许节点在平衡的方式来运行。在这个立方体穿越方案，提供中间节点将通过轮询它从队列中遵循，并提供了6邻居（以> = 3x3x3的立方体的情况下）。然后每个那些邻居节点将进入订单进行查询和他们的邻居将在队列的末尾提供。该proceeder继续运行，直到没有未访问的邻居离开了。
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.
code解释：结果
首先，我们需要知道立方体的大小。 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..
的前两个值分别是，节点的数量，和相邻节点之间的链路/边缘的数目。线的其余的节点之间的连接。例如，第一行告诉节点零被连接到节点1，等...注意，这是一个无向图，因此，当程序存储器节点之间的链路时，它从节点x存储到节点y和从节点y以节点x。结果
产生输入后，建立（）方法将存储在邻接表的节点之间的联系。另一个阵列创建计算有多少优势已为每个节点创建。结果
存储环节后，所有我们需要做的是用遍历算法BFT立方体图。检查上面的描述它如何工作的，并阅读它是如何工作更多的理解执行。结果
印刷方法是可选的，他们在实施和如何code是工作的描述有所帮助。
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).
这里的code为3×3×3的节点在Java中立方：（您可以通过修改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（你必须颜色节点处理的顺序节点，并可以通过查看输出层每个节点号位置得到节点编号）：
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):
这篇关于不同的顺序三维数组遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
