Ищете алгоритм в vb.net или c #, но я не знаю его название!

Question

Я сделаю все возможное, чтобы объяснить, что должен делать алгоритм:

Есть класс 'Рецепт'.Каждый Рецепт может включать другие Рецепты, но не может включать себя или любой другой Рецепт, который включает его.

Итак, простой пример - у нас всего два рецепта A и B.

Если A сначала добавляет B, то позже B не может добавить A, потому что это вызовет цикл.

Более сложный пример:

A, B, C

(1) Рецепт C добавляет B
(2) Рецепт B добавляет A
(3) РецептПопытка добавить C, но не может из-за отношений.C - B - A.

Я могу сделать это сам, я просто подумал, что это стандартный алгоритм с названием, и смогу ли я найти оптимальное решение.

Спасибо

Answer 1

На жаргоне математики / информатики ваша структура называется ориентированным графом . Вам нужен « Направленный ациклический граф », то есть без циклов.

Чтобы выяснить, есть ли в графике циклы, вы можете использовать алгоритм под названием Топологическая сортировка . Он пытается переставить граф таким образом, чтобы, если A ссылается на B, то A всегда предшествует B по порядку. Останавливается, если на графике есть циклы.

Если вы хотите найти все циклы на графике (что полезно для сообщений об ошибках), тогда этот вопрос и ответ стекопотока дает большую помощь.

В качестве фона:
График = что-либо с узлами, связанными ребрами (в вашем случае узлы - это рецепты, а ссылки - ребра).
Directed = края имеют направления. В вашем случае это верно, потому что «A» относится к «B», а не «A» и «B» друг к другу.

Answer 2

Топологический порядок / обнаружение петли? (Алгоритм топологической сортировки останавливается, если обнаружен цикл.)

Это должно быть что-то близкое к тому, что вы делаете.

Answer 3

Учитывая ваши условия, я думаю, что структура, с которой вы в конечном итоге получите 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

Answer 4

Посмотрите на обнаружение цикла .