Реализовать алгоритм BFS

Помогите реализовать поиск в ширину по графах уже сделал DFS и DLS, а BFS уже не могу вот это DFS

  class DepthFirstSearch
{
    private HashSet<Node> visited;
    private LinkedList<Node> path_DFS;
    private Node goal;
    public LinkedList<Node> DFS(Node start, Node goal)
    {
        visited = new HashSet<Node>();
        path_DFS = new LinkedList<Node>();
        this.goal = goal;
        DFS(start);
        if (path_DFS.Count > 0)
        {
            path_DFS.AddFirst(start);
        }
        return path_DFS;
    }

    private bool DFS(Node node)
    {
        node.Handler();
        if (node == goal)
        {
            return true;
        }
        visited.Add(node);
        foreach (var child in node.Children.Where(x => !visited.Contains(x)))
        {
            if (DFS(child))
            {
                path_DFS.AddFirst(child);
                return true;
            }
        }
        return false;
    }

    internal object DFS(Node n06, Node n10, int v)
    {
        throw new NotImplementedException();
    }
}

Program

class Node
{
    public string Name { get; }
    public List<Node> Children { get; }

    public Node(string name)
    {
        Name = name;
        Children = new List<Node>();
    }

    public Node AddChildren(Node node, bool bidirect = true)
    {
        Children.Add(node);
        if (bidirect)
        {
            node.Children.Add(this);
        }
        return this;
    }

    public void Handler()
    {
        Console.WriteLine($"visited {this.Name}");
    }
}

Вся програма здесь https://gitlab.com/Sat228/bfs


Ответы (1 шт):

Автор решения: MBo

В DFS у Вас LinkedList работает как стек - в начало вставляете, с начала же и обходите.

А если использовать его, как очередь - вставлять в конец вместо AddFirst, то получится BFS

→ Ссылка