Suche alle möglichen Pfade vom Kind bis zur Top-Level-Mutter

Question

My graph looks like this

Wie alle möglichen Pfade vom Kind bis zum Top-Level-Eltern in einem Diagramm in C# finden? Ich habe ein einzelnes Top-Elternteil in der Grafik. Alle Knoten haben eigene ID, Name und Eltern-ID. Der oberste Elternteil hat die Eltern-Null und ein Kind kann mehrere Eltern haben. [Ich muss alle Wege von H bis A als finden HEBA, HGDA UND HECA Mein Knoten ist wie folgt.

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

Answer 1

Sie können alle Pfade von 1 Kind auf die oberste Ebene Eltern herausfinden, mit einem BFS: https://en.wikipedia.org/wiki/Breadth-first_search oder auch ein DFS: https://en.wikipedia.org/wiki/Depth-first_search. Beide können rekursiv und iterativ geschrieben werden. Aber seien Sie vorsichtig, wenn Sie eine Schleife wie Node1 haben -> Knoten2 -> Node1 dann diese Algorithmen nie wieder

Wenn Sie die schnellste Art und Weise suchen Sie auch dijkstra verwenden können: https://de.wikipedia.org/wiki/Dijkstra-Algorithmus