数组 – 不同顺序的3D数组遍历

这种方式的工作方式是创建一个图形,其中每个单元格都是一个节点.由于图形具有立方体的形状,因此每个节点必须具有到其X,Y和Z邻居的链接.第一个要做的是通过向程序提供邻居节点之间的关系来创建图形.例如,我们应该给程序一个输入,说节点零连接到节点1等等.在告诉程序节点如何连接以形成多维数据集之后,很容易开始考虑遍历该图.用于遍历图的流行算法称为广度优先遍历(BFT),该算法允许以分布式方式遍历节点.例如,如果你有一个树,这是一种图形,使用BFT遍历它将首先打印根,然后一次打印每个级别,所以它通过公平传播从起点遍历树的那种分支机构.在您从中间到角落的遍历立方体的示例中,BFT可以为您做什么.在这种情况下,BFT将从中间开始并逐个表面地开始遍历节点,并且由于我们从中间点开始,所以传播将采用球形.

什么是BFT

BFT需要使用名为Queue的数据结构,这是一个先进先出列表.首先,我们向队列提供起始点,并将其标记为已访问,这意味着它已进入队列,并且不允许在遍历中的任何时间进入.然后我们将应用一个程序,该程序将轮询头节点,将其标记为已访问,并提供其未访问的邻居.一次又一次地执行相同的过程,直到访问了所有节点,因此队列为空.我们在这里使用队列的原因是允许以平衡的方式遍历节点.在这个多维数据集遍历程序中,提供中间节点将跟随从队列中轮询并提供其6个邻居(在> = 3x3x3多维数据集的情况下).然后,每个邻居节点将按入口顺序轮询,并且它们的邻居将在队列的末尾提供.处理程序继续运行,直到没有未访问的邻居为止.

代码说明：

首先,我们需要知道立方体的大小. 3x3x3的立方体意味着我们应该创建27个节点.我创建了一个名为generateCubeGraph()的方法,它将生成输入字符串以通知程序有关邻居节点之间的关系.此方法返回输出的示例：

27 54
0 1
0 3
0 9
1 2
1 4
1 10
etc..

前两个值分别是节点的数量,以及相邻节点之间的链路/边缘的数量.其余的行是节点之间的连接.例如,第一行告诉节点零连接到节点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中的工作方式(您必须按节点处理顺序为节点着色,并且可以通过查看每个节点编号位置的图层输出来获取节点编号)：

3D Model for a 5 x 5 x 5 Cube