0

E を指定された有向辺セットとします。E のエッジが、すべてのノード (ルート ノードを除く) が 1 次数しか持たない有向木 T を形成できることがわかっているとします。問題は、T 内のすべてのパスを見つけるために、エッジ セット E を効率的にトラバースする方法です。

たとえば、有向辺セット 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（Depth First Search）があなたの要件に合うはずだと思います。ここでそれを見てください -深さ優先検索 - ウィキペディア。必要な形式でパスを出力するように調整できます。複雑さに関しては、ツリー内のすべてのノードに次数 one があるため、ツリーのエッジの数は - |E| のように制限されます。= O(|V|)。DFS は O(|V|+|E|) の複雑さで動作するため、全体的な複雑さは O(|V|) になります。

于 2012-06-16T15:20:12.140 に答える
0

私は自分の課題の一部としてこの質問をしました。上記の紳士は、pathID を使用することを正しく指摘しています。少なくとも 1 回は各エッジにアクセスする必要があるため、複雑さの限界は O(V+E) ですが、ツリー E=O(V) の場合、複雑さは O(v) になります。詳細が少し複雑なので、簡単に紹介します。

各パスに一意の ID のラベルを付けます。パスには、0、1、2 などの増分値の ID が割り当てられます。パスのパス ID は、パス上のエッジの重みの合計です。したがって、DFS を使用してパスに重みを割り当てます。最初のパスに遭遇するまでエッジに 0 を使用することから始め、その後 1 を追加し続けることができます。また、正確性について議論し、重みを適切に割り当てる必要があります。DFS がそのトリックを行います。

于 2012-06-16T20:21:22.080 に答える