在 C# (DAG) 中向上遍历有向图

Question

我有一个没有 cycles/Multiple 边的简单图形。

它总是朝下。

我有一个边缘实例列表，它们根据它们在图形图像中的出现从上到下排序。我不知道这对你是否重要。我只是想你怎么知道图表底部的节点是什么？！

class Edge
{
   public string FromNodeId {get; set;}
   public string ToNodeId{get; set;}
}

class Node
{
   public int Id {get; set;}
   public string Name {get; set;}
}

由于某些业务逻辑需要遍历UP图

当我需要以递归方式访问每个节点时调用的算法是什么？
什么可以作为递归向上迭代边列表的起点？

Answer 1

这里是一个图从下到上的浏览方法

您需要使用最后一个元素对其进行初始化。

            class Edge
            {
                public int FromNodeId { get; set; }
                public int ToNodeId { get; set; }
            }
            class Node // nodes from 0 or 1 to infinit
            {
                public int Id { get; set; }
                public string Name { get; set; }
            }

            void fromBottom(List<Edge> Edges,List<Node> Nodes, Node current)  
            {
                var willVisit = Edges.Where(x => x.ToNodeId == current.Id).ToList();
                if (willVisit.FirstOrDefault()==null)
                {
                    // do your stuff for the last node
                }
                else
                {
                    foreach(var nd in willVisit)
                    {
                        fromBottom(Edges, Nodes,Nodes.Where(x=>x.Id==nd.FromNodeId).First());
                    }
                }
            }

这里是一个图从上到下的浏览方法。

            void fromTop(List<Edge> Edges,List<Node> Nodes, Node current)  
            {
                var willVisit = Edges.Where(x => x.FromNodeId == current.Id).ToList();
                if (willVisit.FirstOrDefault()==null)
                {
                    // do your stuff for the last node 
                }
                else
                {
                    foreach(var nd in willVisit)
                    {
                        fromTop(Edges, Nodes,Nodes.Where(x=>x.Id==nd.ToNodeId).First());
                    }
                }
            }

注意：为避免多次访问一个节点，您可以在结构中添加一个布尔变量来验证访问并稍后在 foreach 循环中检查它。

在 C# (DAG) 中向上遍历有向图

Traverse up a directed graph in c# (DAG)

c#

recursion

directed-acyclic-graphs