Как создать древовидную диаграмму и ввести JSON для запуска BFS (из следующего json) - PullRequest
Новая
       6

Как создать древовидную диаграмму и ввести JSON для запуска BFS (из следующего json)

0 голосов
/ 15 января 2019

У меня есть JSON, и мне нужно написать BFS на этом. Тем не менее, я запутался, чтобы сформировать правильный формат для запуска BFS. Можете ли вы показать мне схему и формирование входных данных для запуска в BFS 

 {
        1: {
            2: { 4: {}, 6: {}, 8: {}, 10: {}, 12: {} },
            3: {
                6: {},
                9: {},
                12: {},
                15: {}
            },
            4: { 8: {}, 12: {}, 16: {}, 20: {}, 24: {}, 28: {} }
        },
        2: { 4: {}, 8: { 16: {}, 24: {} }, 12: { 24: {} } },
        3: { 6: { 12: {}, 18: {}, 24: {}, 30: {} }, 9: { 18: {}, 27: {} }, 12: { 24: {}, 36: {} } },
        4: { 8: {}, 12: {}, 16: { 32: {} }, 20: {}, 24: {}, 28: {}, 32: {} },
        5: { 10: {}, 15: {}, 20: {}, 25: {} },
        7: { 14: { 28: {} }, 21: {} },
        11: { 22: {}, 33: {} },
        13: { 26: {} },
        17: {}
    }

1 Ответ

0 голосов
/ 15 января 2019

Предполагая, что у вас есть следующий класс, который представляет узел дерева: 

public class Node {
    private int value;
    private Node[] children;

    public int getValue() {
        return value;
    }

    public Node[] getChildren() {
        return children;
    }
}

JSON будет выглядеть так: 

[
    {"value": 1, "children": [
        {"value": 2, "children": [ {"value": 4, "children": []}, {"value": 6, "children": []}, {"value": 8, "children": []}, {"value": 10, "children": []}, {"value": 12, "children": []} ]},
        {"value": 3, "children": [
            {"value": 6, "children": []},
            {"value": 9, "children": []},
            {"value": 12, "children": []},
            {"value": 15, "children": []}
        ]},
        {"value": 4, "children": [ {"value": 8, "children": []}, {"value": 12, "children": []}, {"value": 16, "children": []}, {"value": 20, "children": []}, {"value": 24, "children": []}, {"value": 28, "children": []} ]}
    ]},
    {"value": 2, "children": [ {"value": 4, "children": []}, {"value": 8, "children": [ {"value": 16, "children": []}, {"value": 24, "children": []} ]}, {"value": 12, "children": [ {"value": 24, "children": []} ]} ]},
    {"value": 3, "children": [ {"value": 6, "children": [ {"value": 12, "children": []}, {"value": 18, "children": []}, {"value": 24, "children": []}, {"value": 30, "children": []} ]}, {"value": 9, "children": [ {"value": 18, "children": []}, {"value": 27, "children": []} ]}, {"value": 12, "children": [ {"value": 24, "children": []}, {"value": 36, "children": []} ]} ]},
    {"value": 4, "children": [ {"value": 8, "children": []}, {"value": 12, "children": []}, {"value": 16, "children": [ {"value": 32, "children": []} ]}, {"value": 20, "children": []}, {"value": 24, "children": []}, {"value": 28, "children": []}, {"value": 32, "children": []} ]},
    {"value": 5, "children": [ {"value": 10, "children": []}, {"value": 15, "children": []}, {"value": 20, "children": []}, {"value": 25, "children": []} ]},
    {"value": 7, "children": [ {"value": 14, "children": [ {"value": 28, "children": []} ]}, {"value": 21, "children": []} ]},
    {"value": 11, "children": [ {"value": 22, "children": []}, {"value": 33, "children": []} ]},
    {"value": 13, "children": [ {"value": 26, "children": []} ]},
    {"value": 17, "children": []}
]

UPDATE

Теперь вы можете выполнить обход дерева BFS следующим образом: 

public void bfs(Node[] roots) {
    List<Node> queue = new ArrayList<>();
    for (Node root: roots) {
        queue.add(root);
    }
    for (int i = 0; i < queue.size(); ++i) {
        Node current = queue.get(i);
        System.out.println(current.getValue()); // or do something useful with current
        for (Node child: current.getChildren()) {
            queue.add(child);
        }
    }
}
...