При поиске алгоритма в vb.net или c#, но я не знаю, что это - имя!
Я приложу все усилия для объяснения, что алгоритм, как предполагается, делает:
Существует класс 'Рецепт'. Каждый Рецепт может включать другие Рецепты, но не может включать себя или любой другой Рецепт, который включает его.
Так, простой пример, у нас есть всего две Recipes & B.
Если A добавляет B сначала, то позже B не может добавить, потому что он вызовет цикл.
Более сложный пример:
A, B, C
(1) Рецепт C добавляет B
(2) Рецепт B добавляет A
(3) Рецепт попытки добавить C, но не может из-за отношений. C - B - A.
Я могу сделать это сам, я просто задался вопросом, было ли это стандартом, названным алгоритмом, и я мог бы захватить оптимальное решение.
Спасибо
4 ответа
In the Maths / На компьютерном жаргоне ваша структура называется ориентированным графом . Вам нужен « Направленный ациклический граф » - то есть без циклов в нем.
Чтобы узнать, есть ли в графе циклы, вы можете использовать алгоритм, называемый Топологическая сортировка . Он пытается переупорядочить граф так, чтобы если A ссылается на B, то A всегда появляется перед B по порядку. Он останавливается, если на графике есть циклы.
Если вы хотите найти все циклы на графике (что полезно для сообщений об ошибках), тогда этот вопрос и ответ о переполнении стека очень поможет.
В качестве фона:
График = все, что имеет узлы, связанные ребрами (в вашем случае узлы - это рецепты, а ссылки - ребра).
Направлено = края имеют направления.В вашем случае это правда, потому что «A» относится к «B», а не «A» и «B» друг к другу.
Учитывая ваши условия, я думаю, что вы получите структуру DAG.
Итак, мы можем узнать, создает ли добавление нового узла цикл, если да, то мы не добавляем его, иначе мы добавляем его.
class Foo
{
public List<Foo> Reachables { get; set; }
public Foo()
{
this.Reachables = new List<Foo>();
}
public bool Add(Foo other)
{
this.Reachables.Add(other); // add it
if(other.IsReachable(this)) // then see if it create a cycle
{
this.Reachables.Remove(other); // if yes remove it
return false;
}
else
{
return true; // else keep it
}
}
private bool IsReachable(Foo goal)
{
// BFS
Queue<Foo> nextQueue = new Queue<Foo>();
List<Foo> traversed = new List<Foo>();
bool found = false;
nextQueue.Enqueue(this);
while (!found) {
Foo node = null;
try { node = nextQueue.Dequeue(); }
catch { break; }
traversed.Add(node);
if (node.Equals(goal)) {
found = true;
break;
}
else
{
foreach (Foo neighbor in node.Reachables)
if (!traversed.Contains(neighbor) && !nextQueue.Contains(neighbor))
nextQueue.Enqueue(neighbor);
}
}
return found;
}
}
class Program
{
static void Main(string[] args)
{
Foo A = new Foo();
Foo B = new Foo();
Foo C = new Foo();
Console.WriteLine(C.Add(B));
Console.WriteLine(B.Add(A));
Console.WriteLine(A.Add(C));
Console.WriteLine(C.Add(A));
}
}
Вывод:
True
True
False
True
Топологическая сортировка/обнаружение петель? (Алгоритм топологической сортировки останавливается при обнаружении цикла.)
Это должно быть что-то близкое к тому, что вы делаете.