0

请看图。以下。作为我项目的一部分，我需要将森林边缘列表转换为唯一最长路径列表。最长的路径实际上是将任何根节点连接到叶节点或将叶连接到叶节点的路径。这里的问题是，我只有边列表作为输入，我应该从中得出这些路径。

我试图通过使用字典（使用边缘列表创建）查找邻居节点来递归地解决这个问题，但它看起来不是处理问题的正确方法，而且我发现很难可视化。请建议是否有任何已知的有效算法/方法来解决这个问题。

PS：请忽略权重（它们只是标签）。“最长”是指覆盖最大节点的路径。

输入：
元组列表（边） 

edges = [('point', 'floating'), ('754', 'floating'),
('clock', 'IEEE'), ('ARM', 'barrel'), 
('barrel', 'shifter clock'), ('shifter', 'barrel'), 
('representation', 'representation'), ('cycles', '754'), 
('point representation', 'point'), ('barrel shifter', 'point')]

预期输出： 

inference_paths = [
    ['cycles', '754', 'floating', 'point', 'point representation'],
    ['cycles', '754', 'floating', 'point', 'barrel shifter'],
    ['point repr', 'point', 'barrel shifter'],
    ['ARM', 'barrel', 'shifter clock'],
    ['shifter', 'barrel', 'shifter clock'],
    ['ARM', 'barrel', 'shifter'],
    ['clock', 'IEEE'],
    ['representation']
]

我失败的代码： 

edges = [('point', 'floating'), ('754', 'floating'), ('clock', 'IEEE'), ('ARM', 'barrel'), ('barrel', 'shifter clock'), ('shifter', 'barrel'), ('representation', 'representation'), ('cycles', '754'), ('point representation', 'point'), ('barrel shifter', 'point')]
neighbors = {}
inference_paths = []

for edge in edges:
    neighbors[edge[0]] = edge[1]

for edge in edges:
    neighbor = neighbors.get(edge[1])
    if neighbor:
        if not edge[1] == edge[0] == neighbor:
            inference_paths.append([edge[0], edge[1], neighbor])
        else:
            inference_paths.append([edge[0]])
    else:
        inference_paths.append([edge[0], edge[1]])


for path in inference_paths:
    print path

我的输出： 

[['point', 'floating'],
['754', 'floating'],
['clock', 'IEEE'],
['ARM', 'barrel', 'shifter clock'],
['barrel', 'shifter clock'],
['shifter', 'barrel', 'shifter clock'],
['representation'],
['cycles', '754', 'floating'],
['point representation', 'point', 'floating'],
['barrel shifter', 'point', 'floating']]

森林：

在此处输入图像描述

4

1 回答 1

1

我相信你的问题是，你说你正在使用递归，但你没有。尝试迭代地执行此操作是痛苦的。首先让我们看一个基本的递归树遍历函数。

function traverseTree(node) {
    if(node == NULL) return;
    traverseTree(node->leftSubTree);
    traverseTree(node->rightSubTree);
}

上面的函数将访问树中的所有节点，现在我们只需要弄清楚我们需要计算什么逻辑来计算路径等。注意：您的答案似乎表明给定节点只能在路径中使用一次并且不能再次交叉，使用此假设。

arrayOfPaths;
function traverseTree(node) {
    if(node == NULL) return emptyPathObject;

    leftPathObject = traverseTree(node->leftSubTree);
    rightPathObject = traverseTree(node->rightSubTree);
    arrayOfPaths.add(leftPathObject + node + rightPathObject);
    return ((node + leftPathObject) or (node + rightPathObject) whichever is longer);
}

//Code to figure out which paths are the longest here.  This is simpler than the other one too! :)
于 2013-05-02T17:19:44.383 回答