Как "остановить" алгоритм BFS на определенном этапе C# (Visual Studio)

Question

В настоящее время я разрабатываю настольную игру под названием Trivial Persuit для 2-4 игроков. Основная цель - бросить кубик и переместить на доске шаги, которые им показывают. Доска представляет собой шестиугольник с ребрами внутри (множество возможных вариантов выбора для игрока)

До этого момента все идет замечательно, и мне нужно применить алгоритм BFS. Я реализовал график и BFS просто отлично, но теперь я не могу ограничить поиск определенных шагов / расстояний.

Я считаю, что мне нужно создать переменное расстояние или что-то в этом роде, но я не могу понять, как это сделать... Не могли бы вы, ребята, помочь мне?

Ура ребята!

Это мой код 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

На основании вашего вопроса о том, как ограничить алгоритм 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;
}