algorithm - 如何快速找到边序列中的所有路径？

Question

设 E 为给定的有向边集。假设已知E中的边可以形成一棵所有节点(根节点除外)的入度都只有1的有向树T。问题是如何高效地遍历边集E，从而找到T中的所有路径？

例如，给定一个有向边集 E={(1,2),(1,5),(5,6),(1,4),(2,3)}。我们知道这样的集合E可以生成一棵入度只有1的有向树T(根节点除外)。有没有快速遍历边集E的方法，求出所有的路径如下:

Path1 = {(1,2),(2,3)}
Path2 = {(1,4)}
Path3 = {(1,5),(5,6)}

顺便说一句，假设E中的边数是|E|，找到所有路径是否一定有复杂性？

Answer 1

我之前没有研究过这类问题。所以只是尝试了一个简单的解决方案。检查一下。

public class PathFinder
{
    private static Dictionary<string, Path> pathsDictionary = new Dictionary<string, Path>();
    private static List<Path> newPaths = new List<Path>();
    public static Dictionary<string, Path> GetBestPaths(List<Edge> edgesInTree)
    {
        foreach (var e in edgesInTree)
        {
            SetNewPathsToAdd(e);
            UpdatePaths();
        }
        return pathsDictionary;
    }        
    private static void SetNewPathsToAdd(Edge currentEdge) 
    {
        newPaths.Clear();
        newPaths.Add(new Path(new List<Edge> { currentEdge })); 
        if (!pathsDictionary.ContainsKey(currentEdge.PathKey()))
        {
            var pathKeys = pathsDictionary.Keys.Where(c => c.Split(",".ToCharArray())[1] == currentEdge.StartPoint.ToString()).ToList();
            pathKeys.ForEach(key => { var newPath = new Path(pathsDictionary[key].ConnectedEdges); newPath.ConnectedEdges.Add(currentEdge); newPaths.Add(newPath); });             
            pathKeys =  pathsDictionary.Keys.Where(c => c.Split(",".ToCharArray())[0] == currentEdge.EndPoint.ToString()).ToList();
            pathKeys.ForEach(key => { var newPath = new Path(pathsDictionary[key].ConnectedEdges); newPath.ConnectedEdges.Insert(0, currentEdge); newPaths.Add(newPath); });
        }            
    }
    private static void UpdatePaths()
    {
        Path oldPath = null;
        foreach (Path newPath in newPaths)
        {
            if (!pathsDictionary.ContainsKey(newPath.PathKey()))
                pathsDictionary.Add(newPath.PathKey(), newPath);
            else
            {
                oldPath = pathsDictionary[newPath.PathKey()];
                if (newPath.PathWeights < oldPath.PathWeights)
                    pathsDictionary[newPath.PathKey()] = newPath;
            }
        }
    }        
}

public static class Extensions
{
    public static bool IsNullOrEmpty(this IEnumerable<object> collection) { return collection == null || collection.Count() > 0; }
    public static string PathKey(this ILine line) { return string.Format("{0},{1}", line.StartPoint, line.EndPoint); }
}
public interface ILine 
{
    int StartPoint { get; }
    int EndPoint { get; }
}
public class Edge :ILine 
{
    public int StartPoint { get; set; }
    public int EndPoint { get; set; }

    public Edge(int startPoint, int endPoint)
    {
        this.EndPoint = endPoint;
        this.StartPoint = startPoint;
    }
}
public class Path :ILine
{
    private List<Edge> connectedEdges = new List<Edge>();
    public Path(List<Edge> edges) { this.connectedEdges = edges; }
    public int StartPoint { get { return this.IsValid ? this.connectedEdges.First().StartPoint : 0; } }
    public int EndPoint { get { return this.IsValid ? this.connectedEdges.Last().EndPoint : 0; } }
    public bool IsValid { get { return this.EdgeCount > 0; } }
    public int EdgeCount { get { return this.connectedEdges.Count; } }
    // For now as no weights logics are defined
    public int PathWeights { get { return this.EdgeCount; } }
    public List<Edge> ConnectedEdges { get { return this.connectedEdges; } }
}