.net - 在 .NET 中实现的图的邻接列表的理想集合类型是什么？

Question

根据 Sedgewick 的算法书，他使用 Java 中的 Bag 集合来实现图的邻接列表。这非常有意义，因为在 O(1) 中搜索并允许从一个顶点到另一个顶点的重复边。 可以使用列表，但它们在 O(n) 中的搜索速度很慢，所以我会避免使用它。

不幸的是.NET 没有它。有像 Wintellect 这样的实现，但它们不是可移植的(或 .NET 标准兼容)。 我应该改用什么？

Answer 1

经过一番思考，我将自己的 Bag 实现为 Dictionary<'T,int> 这就像一个 multiset 或一个包。这是我在 F# 中的实现:

type Bag<'T when 'T : equality>() =
    let dict = Dictionary<'T,int>()
    let mutable count = 0

    member x.Add = (x:>ICollection<'T>).Add

    member x.Remove = (x:>ICollection<'T>).Remove

    member x.Count = (x:>ICollection<'T>).Count

    member x.Clear = (x:>ICollection<'T>).Clear

    member x.ItemCount item =
        match dict.TryGetValue item with
            | true, itemCount -> itemCount
            | _ -> 0

    interface ICollection<'T> with

        member x.Add item =
            count <- count + 1
            let itemCount =
                match dict.TryGetValue item with
               | true, itemCount -> itemCount
               | _ -> 0
            dict.[item] <- itemCount + 1

        member x.Clear() = dict.Clear()

        member x.Contains item = dict.ContainsKey item

        member x.CopyTo(array, arrayIndex) =
            x
            |> Seq.take(array.Length - arrayIndex)
            |> Seq.iteri (fun i item ->  array.[i + arrayIndex] <- item)

        member x.Count = count

        member x.GetEnumerator()  =
            (x :> ICollection<'T>).GetEnumerator() :> Collections.IEnumerator

        member x.GetEnumerator() =
            let seq =
                let innerSeq (kvp : KeyValuePair<'T,int>) =
                     Seq.init kvp.Value (fun _ -> kvp.Key)
                dict |> Seq.map innerSeq |> Seq.collect id
            seq.GetEnumerator()

        member x.IsReadOnly = false

        member x.Remove item =
            match dict.TryGetValue item with
            | true, 1 ->
                count <- count - 1
                dict.Remove item
            | true, itemCount ->
                count <- count - 1 
                dict.[item] <- itemCount - 1
                true
            | _ -> false