如何"stop"BFS算法在某步C#(Visual Studio)

Question

我目前正在开发一款名为 Trivial Persuit 的棋盘游戏，适合 2-4 名玩家。主要目标是掷骰子并按照骰子向他们显示的步骤在棋盘上移动。棋盘也是一个六边形，里面有边（有很多可能的方式供玩家选择）

一切都很顺利，直到这一刻我需要应用 BFS 算法。我很好地实现了图表和 BFS，但现在我无法限制对某些 steps/distances 的搜索。

我认为我需要创建一个可变距离或类似的东西，但我不知道该怎么做...你们能帮帮我吗？

伙计们干杯！

这是我的 BFS 代码：

public HashSet<T> BFS<T>(Graph<T> graph, T start, Action<T> preVisit = null)
{    
    var visited = new HashSet<T>();

    if (!graph.AdjacencyList.ContainsKey(start))
        return visited;

    var queue = new Queue<T>();
    queue.Enqueue(start);

    while (queue.Count > 0)
    {
        var vertex = queue.Dequeue();

        if (visited.Contains(vertex))
            continue;

        if (preVisit != null)
            preVisit(vertex);

        visited.Add(vertex);

        foreach (var neighbor in graph.AdjacencyList[vertex])
            if (!visited.Contains(neighbor))
                queue.Enqueue(neighbor);
    }

    return visited;
}

Answer 1

根据你的问题，当达到某个depth/level时如何限制BFS算法，你可以跟踪每个节点的深度，当没有更多节点时停止算法您想要的深度。这是基于您的代码使用元组的片段：

public HashSet<T> BFS<T>(Graph<T> graph, T start, int maxDepth, Action<T> preVisit = null)
{
    var visited = new HashSet<T>();

    if (!graph.AdjacencyList.ContainsKey(start))
        return visited;

    var queue = new Queue<Tuple<T, int>>();
    // Consider the start is in the depth "0"
    queue.Enqueue(new Tuple<T, int>(start, 0)); 

    while (queue.Count > 0)
    {
        Tuple<T, int> vertexWithDepth = queue.Dequeue();
        var vertex = vertexWithDepth.Item1;

        if (visited.Contains(vertex))
            continue;

        if (preVisit != null)
            preVisit(vertex);

        visited.Add(vertex);

        // If the current vertex's level is greater or equals
        // the maximum desired level, skip adding its
        // adjacent vertexes.
        int vertexLevel = vertexWithDepth.Item2;
        if(vertexLevel >= maxDepth)
             continue;

        foreach (var neighbor in graph.AdjacencyList[vertex])
            if (!visited.Contains(neighbor))
                queue.Enqueue(new Tuple<T, int>(neighbor, vertexLevel + 1));
    }

    return visited;
}

希望对您有所帮助

Answer 2

根据您的需要，这可能会更简单：您可能不需要在 while 循环中进行第二次检查，但这不会有什么坏处。

public HashSet<T> BFS<T>(Graph<T> graph, T start, int maxSteps, Action<T> preVisit = null)
{    
var visited = new HashSet<T>();

if (!graph.AdjacencyList.ContainsKey(start))
    return visited;

int stepsTaken = 0;
var queue = new Queue<T>();
queue.Enqueue(start);

while (queue.Count > 0 && stepsTaken < maxSteps)
{
    var vertex = queue.Dequeue();

    if (visited.Contains(vertex))
        continue;

    if (preVisit != null)
        preVisit(vertex);

    visited.Add(vertex);

    foreach (var neighbor in graph.AdjacencyList[vertex])
    {
        stepsTaken++;
        if (!visited.Contains(neighbor) && stepsTaken < maxSteps)
            queue.Enqueue(neighbor);
    }

return visited;
}

如何"stop"BFS算法在某步C#(Visual Studio)

How to "stop" BFS algorithm in certain step C# (Visual Studio)

c#

visual-studio

breadth-first-search