Найти все возможные пути от ребенка к началу родительского уровня

Question

My graph looks like this

Как найти все возможные пути от ребенка до верхнего родительского уровня в графе в C#? У меня есть один верхний родитель на графике. Все узлы имеют собственный идентификатор, имя и родительский идентификатор. У родителя верхнего уровня есть родительский нуль, а у ребенка может быть несколько родителей. [Я должен найти все пути от H до A, как HEBA, HGDA AND HECA Мой узел выглядит следующим образом.

class Node 
    { 
     public int Id { get; set; } 
     public List<int> ParentId { get; set; } 
     public string Name { get; set; } 
    } 

Answer 1

вы можете найти все пути от 1 ребенка к родителю верхнего уровня, с BFS: https://en.wikipedia.org/wiki/Breadth-first_search или же ДФС: https://en.wikipedia.org/wiki/Depth-first_search. Оба могут быть записаны рекурсивно и итеративно. Но будьте осторожны, если у вас есть цикл вроде Node1 -> Node2 -> Node1 тогда эти алгоритмы не возвращают

Если вы ищете fastes образом, вы можете также использовать Алгоритм Дейкстры: https://de.wikipedia.org/wiki/Dijkstra-Algorithmus