具有最小内存的任意图的广度优先遍历

Question

我有一个巨大的有向图，我需要遍历它以搜索从给定起点到特定节点的最短路径。所讨论的图表并不明确存在；子节点是根据父节点通过算法确定的。
（举个例子：想象一个国际象棋位置图。每个节点都是一个国际象棋位置，它的子节点是从该位置开始的所有合法移动。）
所以我有一个开放节点队列，每次我处理队列中的下一个节点时，我都会将其所有子节点排入队列。但是由于图表可以有循环，我还需要维护所有访问过的节点的哈希集，这样我就可以检查我之前是否访问过一个节点。
这工作正常，但由于该图太大，我运行遇到了内存问题。队列中的所有节点也存储在哈希集中，在我的例子中，它往往占总数或实际访问节点总数的 50% 左右。
有没有什么神奇的方法可以在保持哈希集速度的同时摆脱这种冗余？（显然，我可以通过不散列和只进行线性搜索来摆脱冗余，但这是不可能的。）

Answer 1

我通过编写 class 解决了这个问题，它将键存储在列表中并将键的索引存储在哈希表中。 “队列中”的下一个节点始终是列表中的下一个节点，直到您找到要查找的内容或遍历整个图。

class IndexMap<T>
{
    private List<T> values;
    private LinkedList<int>[] buckets;
    public int Count { get; private set; } = 0;

    public IndexMap(int capacity)
    {
        values = new List<T>(capacity);
        buckets = new LinkedList<int>[NextPowerOfTwo(capacity)];
        for (int i = 0; i < buckets.Length; ++i)
            buckets[i] = new LinkedList<int>();
    }

    public void Add(T item) //assumes item is not yet in map
    {
        if (Count == buckets.Length)
            ReHash();
        int bucketIndex = item.GetHashCode() & (buckets.Length - 1);
        buckets[bucketIndex].AddFirst(Count++);
        values.Add(item);
    }

    public bool Contains(T item)
    {
        int bucketIndex = item.GetHashCode() & (buckets.Length - 1);
        foreach(int i in buckets[bucketIndex])
        {
            if (values[i].Equals(item))
                return true;
        }
        return false;
    }

    public T this[int index]
    {
        get => values[index];
    }

    private void ReHash()
    {
        LinkedList<int>[] newBuckets = new LinkedList<int>[2 * buckets.Length];
        for (int i = 0; i < newBuckets.Length; ++i)
            newBuckets[i] = new LinkedList<int>();
        for (int i = 0; i < buckets.Length; ++i)
        {
            foreach (int index in buckets[i])
            {
                int bucketIndex = values[index].GetHashCode() & (newBuckets.Length - 1);
                newBuckets[bucketIndex].AddFirst(index);
            }
            buckets[i] = null;
        }
        buckets = newBuckets;
    }

    private int NextPowerOfTwo(int n)
    {
        if ((n & n-1) == 0)
            return n;
        int output = 0;
        while (n > output)
        {
            output <<= 1;
        }
        return output;
    }
}

维护开放节点数组和访问节点哈希表的旧方法需要 n*(1+a)*size(T) space，其中 a 是 nodes_in_the_queue 超过 total_nodes_found 并且 size(T) 是节点的大小。
此方法需要 n*(size(T) + size(int))。如果您的节点明显大于 int，这可以节省很多。

具有最小内存的任意图的广度优先遍历

Breadth first traversal of arbitrary graph with minimal memory

graph

breadth-first-search

hashset