Обход иерархии групп
Есть иерархия групп, в которой у групп являющихся корнем (вершиной) может быть несколько прямых потомков, у этих потомков могут быть тоже несколько прямых потомков и так далее. Программно это реализовано в виде объекта класса, содержащего ссылку на объект родитель и коллекцию содержащею ссылки на своих прямых потомков:
public class Groupu
{
public int IdGroup { get; set; }
public string Name { get; set; }
[DisplayName("Подчиняется")]
public virtual Groupu GroupParents { get; set; }
public virtual ICollection<Groupu> ChildGroups { get; set; }
}
Нужно узнать всех потомков какой-либо группы (объекта) на всю глубину, т.е. до самого низа. Чисто теоретически это обход графа в глубину, вроде как? Если нет, то исправьте меня.
Но есть ещё не понятные моменты, например при поиске в глубину у нас должно быть условия выхода - нахождение заданного объекта, в данной задаче у нас нет такого объекта, а нам нужно получить весь список его потомков (прямых и не прямых).
Я попытался реализовать алгоритм обхода графа в ширину, но у меня получилось, что я обхожу только прямых потомков потомков текущего объекта, а глубже уже не получается:
public List<Groupu> GetAllChildGroupsBFS(List<Groupu> groupChild, Groupu groupStart)
{
// groupChild - список потомков
// groupStart - начальный потомок
// t - пункт назначения, его нет
// Список всех посещенных потомков
List<Groupu> childGroupus = new List<Groupu>();
// инициализируем очередь
Queue<Groupu> queueGroupu = new Queue<Groupu>();
// добавляем groupStart в очередь
queueGroupu.Enqueue(groupStart);
// помечаем groupStart как посещенную вершину во избежание повторного добавления в очередь
groupStart.Visited = true;
while (queueGroupu.Count > 0)
{
// удаляем первый (верхний) элемент из очереди
Groupu gr = queueGroupu.Dequeue();
//Добавляем посещенную вершину в список потомков
childGroupus.Add(gr);
// groupChild - потомки
foreach (Groupu childgr in groupChild)
{
// если сосед не посещался
if (!childgr.Visited)
{
// добавляем его в очередь
queueGroupu.Enqueue(childgr);
// помечаем вершину как посещенную
childgr.Visited = true;
//Добавляем посещенную вершину в список потомков
childGroupus.Add(childgr);
//Условие выхода
}
}
}
// Возвращение списка потомков
return childGroupus;
}
Ещё попробовал реализовать обход графа в глубину, но тут у меня тоже получается обойти только прямых потомков моих потомков:
public bool GetAllChildGroupsDFS(List<Groupu> groupChild, Groupu group)
{
// groupChild - список потомков
// group - посещенный потомок
// t - пункт назначения, его нет
// Список всех посещенных потомков
List<Groupu> childGroupus = new List<Groupu>();
// это общие случаи
// либо достигли пункта назначения, либо уже посещали узел
if (group.Visited) return false;
// помечаем узел как посещенный
group.Visited = true;
//Добавляем посещенную группу в список потомков
childGroupus.Add(group);
// исследуем всех соседей (ближайшие потомки группы) group
foreach (Groupu childGr in groupChild)
{
// если сосед не посещался
if (!childGr.Visited)
{
// двигаемся по пути и проверяем, не достигли ли мы пункта назначения
bool reached = GetAllChildGroupsDFS(groupChild, childGr);
// возвращаем true, если достигли
if (reached) return true;
}
}
// Если прошли весь путь, а условие поиска не выполнилось
return false;
}
Помогите с реализацией пожалуйста
Ответы (1 шт):
Да, это обход дерева.
Какой именно - от вида обхода зависит порядок вывода. Вот для бинарных деревьев - для произвольного количества деток всё будет похоже
При обходе в глубину выводятся ветки до самого низа, потом подъём к корню и т.д.
При обходе в ширину вывод будет происходить по уровням - все узлы первого уровня, потом все узлы второго и т.д.
Условие остановки - нечего больше обходить.
public List<Groupu> GetAllChildGroupsBFS(List<Groupu> groupChild, Groupu groupStart)
{
// groupChild - список потомков
// groupStart - начальный потомок
// Список всех посещенных потомков
List<Groupu> childGroupus = new List<Groupu>();
// инициализируем очередь
Queue<Groupu> queueGroupu = new Queue<Groupu>();
// добавляем groupStart в очередь
queueGroupu.Enqueue(groupStart);
while (queueGroupu.Count > 0)
{
// удаляем первый (верхний) элемент из очереди
Groupu gr = queueGroupu.Dequeue();
//Добавляем посещенную вершину в список потомков
childGroupus.Add(gr);
// groupChild - потомки
foreach (Groupu childgr in gr.ПРЯМЫЕ_ПОТОМКИ)
{
// добавляем его в очередь
queueGroupu.Enqueue(childgr);
}
}
// Возвращение списка потомков
return childGroupus;
}