时间戳

首页 > 解决方案 > 在图中找到具有最小值的节点

javascript - 在图中找到具有最小值的节点

问题描述

有一个图，由对象表示的节点：

Node = {
    value: <number>,
    children: [Node, Node ... Node] 
}

我需要找到具有最小值字段的节点。

我找到了图表的最小值，但不知道如何返回节点。

const min = (graph) => !graph.children ? graph.value :
    Math.min(graph.value, ...graph.children.map(min));

图表示例：

{value:31,children:[{value:68},{value:10,children:[{value:100,children:[{value:21,children:[{value:21},{value:64}]},{value:86}]}]}]}

答案示例：

{value:10,children:[{value:100,children:[{value:21,children:[{value:21},{value:64}]},{value:86}]}]}

标签： javascriptrecursiondata-structuresgraph

解决方案

作为可能的解决方案，我建议：

function min(graph){
    // the obvious case
    if(!graph.children){
        return graph;
    } 
    //get the min children 
    const comparator = (g1,g2)=>g1.value-g2.value; 
    //leaf ie node without children
    const leafs = graph.children.map(g=>min(g));
    leafs.sort(comparator); 
    return comparator(graph,leafs[0]) <= 0 ? graph : leafs[0];
}

此解决方案适用于有限图，否则您应该更改结构以更有效地处理大图。

推荐阅读