Обнаружьте циклы в графике генеалогии во время Поиска в глубину
Метод указывает, что существует T, расширяющий Root, который является типом возврата. Однако, пока метод не используется где-то, вы не знаете, какой это класс. Вы не знаете, будет ли T А, или В, или что-то еще. Каждый раз, когда он используется, это будет ровно один подкласс Root.
Но здесь ваш код предполагает, что это будут и A, и B одновременно. На самом деле, T не может быть ни тем, ни другим. Если T является A, вы не можете вернуть экземпляр B. Если T является B, вы не можете вернуть экземпляр A. Если T не является ни A, ни B, вы не можете вернуть ни экземпляр A, ни B.
Вы должны вернуть экземпляр T.
Вы можете не использовать дженерики, а просто вернуть Root.
6 ответов
Псевдо код:
void ProcessTree(GenTreeNode currentNode, Stack<GenTreeNode> seen)
{
if(seen.Contains(currentNode)) return;
// Or, do whatever needs to be done when a cycle is detected
ProcessHorse(currentNode.Horse); // Or whatever processing you need
seen.Push(currentNode);
foreach(GenTreeNode childNode in currentNode.Nodes)
{
ProcessTree(childNode, seen);
}
seen.Pop();
}
Основная идея состоит в том, чтобы сохранить список всех узлов, которые мы уже видели на нашем пути вниз к текущему узлу; если был, возвращаются к узлу, который мы уже прошли, то Вы знаете, что мы сформировали цикл (и мы должны пропустить значение или сделать любые потребности, которые будут сделаны),
Поддержите стопку всего продвижения элементов до корня дерева.
Каждый раз Вы совершенствуете вниз дерево, сканируете стек для дочернего элемента. Если Вы находите соответствие, то Вы обнаружили цикл и должны пропустить того ребенка. Иначе продвиньте ребенка на стек и продолжите двигаться. Каждый раз, когда Вы отслеживаете в обратном порядке дерево, высовываете элемент из стека и отбрасывания.
(В случае генеалогических данных "дочерний" узел в дереве является, по-видимому, биологическим родителем "родительского" узла.)
Очень простой способ обнаружить это, путем проверки что само ограничение:
То, что не может, произошло, который является лошадью, появляются как родительский элемент или дедушка или прадед СЕБЯ.
Каждый раз, когда Вы вставляете узел в свое дерево, пересекаете дерево к корню, чтобы удостовериться, что лошадь не существует как никакой вид родителя.
Для ускорения этого можно связать хеш-таблицу к каждому узлу, где Вы кэшируете ответ такого поиска. Затем Вы не должны искать весь путь в следующий раз, когда Вы вводите лошадь под тем узлом.
Это походит на случай, где можно наконец применить тот вопрос о мелочах интервью: найдите цикл в связанном списке с помощью только O (1) память.
В этом случае Ваш "связанный список" является последовательностью элементов, которые Вы перечисляете. Используйте два перечислителя, работайте один на половине скорости, и если быстрый когда-нибудь сталкивается с медленным затем, у Вас есть цикл. Это также будет O (n) время вместо O (n^2) время, требуемое для проверки 'замеченного' списка. Оборотная сторона, Вы только узнаете о цикле после того, как некоторые узлы были обработаны многократно.
В примере я заменил 'половину скорости' метод с более простым к записи 'методом' маркеров отбрасывания.
class GenTreeNode {
...
///<summary>Wraps an the enumeration of linked data structures such as trees and linked lists with a check for cycles.</summary>
private static IEnumerable<T> CheckedEnumerable<T>(IEnumerable<T> sub_enumerable) {
long cur_track_count = 0;
long high_track_count = 1;
T post = default(T);
foreach (var e in sub_enumerable) {
yield return e;
if (++cur_track_count >= high_track_count) {
post = e;
high_track_count *= 2;
cur_track_count = 0;
} else if (object.ReferenceEquals(e, post)) {
throw new Exception("Infinite Loop");
}
}
}
...
///<summary>Enumerates the tree's nodes, assuming no cycles</summary>
private IEnumerable<GenTreeNode> tree_nodes_unchecked() {
yield return this;
foreach (var child in this.nodes)
foreach (var e in child.tree_nodes_unchecked())
yield return e;
}
///<summary>Enumerates the tree's nodes, checking for cycles</summary>
public IEnumerable<GenTreeNode> tree_nodes()
{
return CheckedEnumerable(tree_nodes_unchecked());
}
...
void ProcessTree() {
foreach (var node in tree_nodes())
proceess(node);
}
}
Ваше решение для хеш-таблицы должно работать, если Вы отслеживаете узлы вместо лошадей. Просто удостоверьтесь каждый раз, когда Вы читаете новую лошадь, Вы создаете новый узел, даже если значение/лошадь совпадает со значением/лошадью предыдущего узла.
Вы имеете дело с направленным графом без петель, не деревом. Не должно быть никаких циклов, поскольку потомок лошади не может также быть ее предком.
Зная это, необходимо применить методы кода, характерные для направленных графов без петель.