一千萬個為什麽

搜索

從鄰接列表創建樹的最有效方法

我有一個對象的鄰接列表(從SQL數據庫加載的行,帶有密鑰和它的父鍵),我需要用它來構建無序樹。它保證沒有周期。

這花費的時間太長了(在大約5分鐘內僅處理了870K節點中的〜3K)。在我的工作站Core 2 Duo上運行,有足夠的RAM。

關於如何加快速度的任何想法?

public class StampHierarchy {
    private StampNode _root;
    private SortedList _keyNodeIndex;

   //takes a list of nodes and builds a tree
   //starting at _root
    private void BuildHierarchy(List nodes)
    {
        Stack processor = new Stack();
        _keyNodeIndex = new SortedList(nodes.Count);

       //find the root
        _root = nodes.Find(n => n.Parent == 0);

       //find children...
        processor.Push(_root);
        while (processor.Count != 0)
        {
            StampNode current = processor.Pop();

           //keep a direct link to the node via the key
            _keyNodeIndex.Add(current.Key, current);  

           //add children
            current.Children.AddRange(nodes.Where(n => n.Parent == current.Key));

           //queue the children
            foreach (StampNode child in current.Children)
            {
                processor.Push(child);
                nodes.Remove(child);//thought this might help the Where above
            }
        }
    }
}

    public class StampNode {
        //properties: int Key, int Parent, string Name, List Children
    }

最佳答案

  1. 將節點放入已排序的列表或字典中。

  2. 掃描該列表,選取每個節點,在同一列表中找到其父節點(二進制搜索或字典查找),將其添加到父節點的Children集合中。

沒有必要將Stack放入樹中。

轉載註明原文: 從鄰接列表創建樹的最有效方法