0

令 E 为给定的有向边集。假设已知 E 中的边可以形成一个有向树 T，所有节点（根节点除外）只有 1 个入度。问题是如何有效地遍历边集 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|，是否存在找到所有路径的复杂性？

4

3 回答 3

2

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

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; } }
}
于 2012-06-17T05:02:00.507 回答
0

我认为 DFS（深度优先搜索）应该适合您的要求。看看这里 -深度优先搜索 - 维基百科。您可以对其进行定制，以您需要的格式打印路径。至于复杂性，由于树中的每个节点都有一个度数，因此树的边数限制为 - |E| = O(|V|)。由于 DFS 以 O(|V|+|E|) 的复杂度运行，因此您的整体复杂度为 O(|V|)。

于 2012-06-16T15:20:12.140 回答
0

我把这个问题作为我作业的一部分。上面的先生已经正确指出使用 pathID。您必须至少访问每条边一次，因此复杂度界限为 O(V+E)，但对于树 E=O(V)，复杂度为 O(v)。由于涉及细节，我将给您一瞥-

您将用唯一的 ID 标记每条路径，并且在增量值中为路径分配 ID，例如 0、1、2...。路径的路径 ID 是路径上边的权重之和。所以使用 DFS 为路径分配权重。您可以从边使用 0 开始，直到遇到第一条路径，然后继续添加 1，依此类推。您还必须争论正确性并正确分配权重。DFS 可以解决问题。

于 2012-06-16T20:21:22.080 回答