javascript - 如何创建树形图并输入 JSON 以运行 BFS（来自以下 json）

Question

我有一个 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: {}
    }

标签： javascriptbreadth-first-search

Answer 1

假设您有以下代表树节点的类：

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": []}
]

更新

现在您可以像这样对树进行 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);
        }
    }
}