javascript - 按父级排序(拓扑排序)和数组中元素的重要性

Question

嗯，我有一个包含对象的数组，其中某些元素依赖于其他元素。

因此，我需要按重要性(父级的依赖性)对其进行排序，以将其存储在数据库中，并用相应的父级 id 替换所有子级的 parent 属性。

数组示例:

[
    {
        "id": 1,
        "email": "<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="c5a485a7eba6aaa8" rel="noreferrer noopener nofollow">[email protected]</a>", // unique
        "parent": "<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="85e6c5e7abe6eae8" rel="noreferrer noopener nofollow">[email protected]</a>" // is nullable
    },
    {
        "id": 2,
        "email": "<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="583a183a763b3735" rel="noreferrer noopener nofollow">[email protected]</a>",
        "parent": null
    },
    {
        "id": 3,
        "email": "<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="f291b290dc919d9f" rel="noreferrer noopener nofollow">[email protected]</a>",
        "parent": "<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="583a183a763b3735" rel="noreferrer noopener nofollow">[email protected]</a>"
    },
    {
        "id": 4,
        "email": "<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="8ce8cceea2efe3e1" rel="noreferrer noopener nofollow">[email protected]</a>",
        "parent": "<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="721332105c111d1f" rel="noreferrer noopener nofollow">[email protected]</a>"
    },
    ...
]

依赖关系的图形示例:

预期结果: 按依赖项(父级)排序:

[
    {
        "id": 2,
        "email": "<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="6d0f2d0f430e0200" rel="noreferrer noopener nofollow">[email protected]</a>",
        "parent": null
    },
    {
        "id": 3,
        "email": "<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="553615377b363a38" rel="noreferrer noopener nofollow">[email protected]</a>",
        "parent": 2
    },
    {
        "id": 1,
        "email": "<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="2849684a064b4745" rel="noreferrer noopener nofollow">[email protected]</a>",
        "parent": 3 
    },
    {
        "id": 4,
        "email": "<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="680c280a460b0705" rel="noreferrer noopener nofollow">[email protected]</a>",
        "parent": 1
    },
    ...
]

要设置我正在使用的相应父id(但它没有按父级别排序:父、子、孙...):

let users = [
{
    "id": 1,
    "email": "<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="bddcfddf93ded2d0" rel="noreferrer noopener nofollow">[email protected]</a>", // unique
    "parent": "<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="294a694b074a4644" rel="noreferrer noopener nofollow">[email protected]</a>" // is nullable
},
{
    "id": 2,
    "email": "<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="274567450944484a" rel="noreferrer noopener nofollow">[email protected]</a>",
    "parent": null
},
{
    "id": 3,
    "email": "<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="6d0e2d0f430e0200" rel="noreferrer noopener nofollow">[email protected]</a>",
    "parent": "<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="bedcfedc90ddd1d3" rel="noreferrer noopener nofollow">[email protected]</a>"
},
{
    "id": 4,
    "email": "<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="98fcd8fab6fbf7f5" rel="noreferrer noopener nofollow">[email protected]</a>",
    "parent": "<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="2b4a6b4905484446" rel="noreferrer noopener nofollow">[email protected]</a>"
}
];

users = users.map(user => {
    user.parent = _.findIndex(users, i => user.parent === i.email);
    return user;
});

附: 在这种情况下，重要性概念指的是父级别。 所以，首先我需要 parent ，然后是 child 、孙子等等......

如果这个帖子的解释很差，我很抱歉，如果您有疑问，我会寻找表达想法的最佳方式。

Answer 1

我将通过首先生成一个新输入来解决此问题，其中将父电子邮件替换为父ID以及与它们相关的树的节点级别的新属性属于。然后我们可以通过此 level 属性对节点进行排序，并在相同的 level 上按 id 进行排序。

const input = [
    {"id": 1, "email": "<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="5e3f1e3c703d3133" rel="noreferrer noopener nofollow">[email protected]</a>", "parent": "<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="a6c5e6c488c5c9cb" rel="noreferrer noopener nofollow">[email protected]</a>"},
    {"id": 2, "email": "<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="4a280a2864292527" rel="noreferrer noopener nofollow">[email protected]</a>", "parent": null},
    {"id": 3, "email": "<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="d7b497b5f9b4b8ba" rel="noreferrer noopener nofollow">[email protected]</a>", "parent": "<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="056745672b666a68" rel="noreferrer noopener nofollow">[email protected]</a>"},
    {"id": 4, "email": "<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="1a7e5a7834797577" rel="noreferrer noopener nofollow">[email protected]</a>", "parent": "<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="375677551954585a" rel="noreferrer noopener nofollow">[email protected]</a>"},
    {"id": 5, "email": "<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="ed95ad8fc38e8280" rel="noreferrer noopener nofollow">[email protected]</a>", "parent": "<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="b8daf8da96dbd7d5" rel="noreferrer noopener nofollow">[email protected]</a>"},
    {"id": 6, "email": "<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="b2c8f2d09cd1dddf" rel="noreferrer noopener nofollow">[email protected]</a>", "parent": "<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="047c44662a676b69" rel="noreferrer noopener nofollow">[email protected]</a>"},
    {"id": 7, "email": "<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="423b02206c212d2f" rel="noreferrer noopener nofollow">[email protected]</a>", "parent": null},
    {"id": 8, "email": "<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="9bf6dbf9b5f8f4f6" rel="noreferrer noopener nofollow">[email protected]</a>", "parent": "<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="235a63410d404c4e" rel="noreferrer noopener nofollow">[email protected]</a>"}
];

const findParent = (mail) => input.find(x => x.email === mail);

const getLevel = (mail, lvl) =>
{    
    return mail ? getLevel(findParent(mail).parent, lvl + 1) : lvl;
}

let newInput = input.map(({id, email, parent}) =>
{
    return {
        id: id,
        email: email,
        parent: findParent(parent) ? findParent(parent).id : null,
        lvl: getLevel(parent, 0)
    };
});

let sortedInput = newInput.sort((a, b) =>
{
    return (a.lvl - b.lvl) ? a.lvl - b.lvl : a.id - b.id;
});

console.log(sortedInput);