Реализовать алгоритм 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