リストとスタックを使用した深さ優先検索の C# への実装

https://stackoverflow.com/questions/5804844

24-10-2019
|

質問

ある程度成功した深さ優先検索を作成したいと考えています。

これまでのコードは次のとおりです (コンストラクターを除く、Vertex クラスと Edge クラスにはプロパティのみが含まれており、ここに投稿する重要なものは何もないことに注意してください)。

private Stack<Vertex> workerStack = new Stack<Vertex>();
private List<Vertex> vertices = new List<Vertex>();
private List<Edge> edges = new List<Edge>();

private int numberOfVertices;
private int numberOfClosedVertices;
private int visitNumber = 1;

private void StartSearch()
{
    // Make sure to visit all vertices
    while (numberOfClosedVertices < numberOfVertices && workerStack.Count > 0)
    {
        // Get top element in stack and mark it as visited
        Vertex workingVertex = workerStack.Pop();
        workingVertex.State = State.Visited;

        workingVertex.VisitNumber = visitNumber;
        visitNumber++;

        numberOfClosedVertices++;

        // Get all edges connected to the working vertex
        foreach (Vertex vertex in GetConnectedVertices(workingVertex))
        {
            vertex.Parent = workingVertex;
            workerStack.Push(vertex);
        }
    }
}

private List<Vertex> GetConnectedVertices(Vertex vertex)
{
    List<Vertex> vertices = new List<Vertex>();

    // Get all vertices connected to vertex and is unvisited, then add them to the vertices list
    edges.FindAll(edge => edge.VertexSource == vertex && edge.VertexTarget.State == State.Unvisited).ForEach(edge => vertices.Add(edge.VertexTarget));

    return vertices;
}

すべての頂点が訪問されるように機能しますが、正しい順序ではありません。

以下は、私のサイトへのアクセス状況をウィキペディアと比較したものです。 Comparison

私の場合は向きを変えて、右から左へ始まっているようです。

何が原因か知っていますか？(私の実装に関するアドバイスも大歓迎です)

編集：答えは得られましたが、それでも GetConnectedVertices メソッドの最終結果を表示したいと思いました。

private List<Vertex> GetConnectedVertices(Vertex vertex)
{
    List<Vertex> connectingVertices = new List<Vertex>();

    (from edge in edges
     where edge.VertexSource == vertex && edge.VertexTarget.State == State.Unvisited
     select edge).
     Reverse().
     ToList().
     ForEach(edge => connectingVertices.Add(edge.VertexTarget));

    return connectingVertices;
}

解決

私の場合は向きを変えて、右から左へ始まっているようです。何が原因か知っていますか？

他の人が指摘したように、スタック上の次に訪問するノードを左から右の順序でプッシュしています。これは、スタックの順序が逆になるため、右から左にポップオフされることを意味します。スタックは後入れ先出しです。

GetConnectedVertices にリストではなくスタックを構築させることで、この問題を解決できます。そうすれば、接続された頂点が反転されます二度, 、返されたスタックに入るときに 1 回、実際のスタックに入るときに 1 回です。

また、私の実装に関するアドバイスもいただければ幸いです

実装は機能していると思いますが、根本的な問題が数多くあります。もし私がレビューのためにそのコードを見せられたとしたら、私はこう言います。

まず、このデータ構造に対して 2 つの深さ優先検索を同時に実行したいとします。複数のスレッドで実行していたか、または内側のループが外側のループとは異なる要素に対して DFS を実行する入れ子になったループがあるためです。何が起こるのですか？どちらも「State」フィールドと「VisitNumber」フィールドを変更しようとするため、相互に干渉します。検索のような「クリーンな」操作であるべき操作が実際にデータ構造を「ダーティ」にしてしまうのは、非常に悪い考えです。

また、使用できなくなります。 永続的な不変データ グラフの冗長部分を表すために使用します。

また、クリーンアップするコードが省略されていることに気付きました。「状態」が元の値に戻るのはいつですか?をやったとしたらどうしますか 2番 DFS?ルートにはすでにアクセスしているため、すぐに失敗します。

これらすべての理由から、より良い選択は、「訪問済み」状態を各頂点ではなく、独自のオブジェクトに保持することです。

次に、すべての状態オブジェクトがクラスのプライベート変数であるのはなぜでしょうか?これは単純なアルゴリズムです。そのためにクラス全体を構築する必要はありません。深さ優先検索アルゴリズムは、オブジェクトの状態としてではなく、形式的なパラメーターとして検索するグラフを取得する必要があり、フィールドではなくローカル変数で必要に応じて独自のローカル状態を維持する必要があります。

次にグラフの抽象化ですが…まあ、それは抽象的なものではありません。これは 2 つのリストで、1 つは頂点のリスト、もう 1 つはエッジのリストです。これら 2 つのリストが一貫していることはどのようにして確認できるのでしょうか?頂点リストには存在しないが、エッジリストには存在する頂点があるとします。それをどうやって防ぐのですか？必要なのはグラフの抽象化です。グラフ抽象化の実装に、エッジを表現して近傍を見つける方法を考慮させます。

次に、ForEach の使用は合法かつ一般的ですが、頭が痛くなります。すべてのラムダを使用してコードを読んで推論するのは困難です。完璧に優れた "foreach" ステートメントが完成しました。これを使って。

次に、「親」プロパティを変更していますが、このプロパティが何のためにあるのか、また走査中になぜ変更されるのかはまったく明らかではありません。任意のグラフ内の頂点は、グラフがツリーでない限り「親」を持ちません。グラフがツリーの場合は、「訪問」状態を追跡する必要はありません。ツリーにはループがありません。ここで何が起こっているのでしょうか？このコードはただ奇妙なものであり、DFS を実行する必要はありません。

次に、GetConnectedVertices という名前のヘルパーメソッドは嘘です。接続された頂点を取得するのではなく、まだ訪問していない頂点を接続します。名前が偽っているメソッドは非常にわかりにくいです。

最後に、これは深さ優先検索であると主張していますが、 何も検索しません！ 探しているものはどこにあるのでしょうか？結果はどこに返されますか?これは決して検索ではなく、横断です。

やり直してください。なんでしょう？ 開始頂点を与えられたグラフの深さ優先の走査. 。次に、それを実装します。まず、何を通過するのかを定義します。グラフ。グラフからどのようなサービスが必要ですか?隣接する頂点のセットを取得する方法:

interface IGraph
{
    IEnumerable<Vertex> GetNeighbours(Vertex v);
}

メソッドは何を返しますか?深さ優先の頂点のシーケンス。何が必要ですか?開始頂点。わかりました：

static class Extensions
{
    public static IEnumerable<Vertex> DepthFirstTraversal(
        this IGraph graph, 
        Vertex start) 
    { ... }
}

これで、深さ優先検索の簡単な実装ができました。Where 句を使用できるようになりました。

IGraph myGraph = whatever;
Vertex start = whatever;
Vertex result = myGraph.DepthFirstTraversal(start)
                       .Where(v=>something)
                       .FirstOrDefault();

では、グラフの状態を破壊することなく走査を行うために、そのメソッドをどのように実装するのでしょうか?自分自身の外部状態を維持します。

public static IEnumerable<Vertex> DepthFirstTraversal(
    this IGraph graph, 
    Vertex start) 
{
    var visited = new HashSet<Vertex>();
    var stack = new Stack<Vertex>();

    stack.Push(start);

    while(stack.Count != 0)
    {
        var current = stack.Pop();

        if(!visited.Add(current))
            continue;

        yield return current;

        var neighbours = graph.GetNeighbours(current)
                              .Where(n=>!visited.Contains(n));

        // If you don't care about the left-to-right order, remove the Reverse
        foreach(var neighbour in neighbours.Reverse()) 
            stack.Push(neighbour);
    }
}

どれだけクリーンで短いかがわかりますか?状態の突然変異はありません。エッジリストをいじる必要はありません。不適切な名前のヘルパー関数はありません。そして、コードは実際に、記載されているとおりのことを実行します。グラフを横断します。

イテレータブロックの利点も得られます。つまり、誰かがこれを DF 検索に使用している場合、検索基準が満たされると反復は放棄されます。結果が早期に見つかった場合は、完全な走査を行う必要はありません。

他のヒント

私は、任意のDFSトラバーサルの @ericのコードを一般化しました T 子供を持つあらゆるタイプで物事を機能させるために - 私は共有していると思いました：

public static IEnumerable<T> DepthFirstTraversal<T>(
    T start,
    Func<T, IEnumerable<T>> getNeighbours)
{
    var visited = new HashSet<T>();
    var stack = new Stack<T>();
    stack.Push(start);

    while (stack.Count != 0)
    {
        var current = stack.Pop();

        if (!visited.Add(current))
            continue;

        yield return current;

        var neighbours = getNeighbours(current).Where(node => !visited.Contains(node));

        // If you don't care about the left-to-right order, remove the Reverse
        foreach(var neighbour in neighbours.Reverse())
        {
            stack.Push(neighbour);
        }
    }
}

使用例：

var nodes = DepthFirstTraversal(myNode, n => n.Neighbours);

問題は、要素を検索する順序でです。君の for each の StartSearch 要素の順序を保証しません。あなたもそうしません FindAll の GetConnectedVertices 方法。この行を見てみましょう：

edges.FindAll(edge => edge.VertexSource == vertex && edge.VertexTarget.State == State.Unvisited).ForEach(edge => vertices.Add(edge.VertexTarget));

追加する必要があります OrderBy() 目的の順序を確保するため。

アイテムは、それらがどのようにプッシュされるかとして、逆の順序でスタックをポップします。

stach.push（）結果：1 2 3 4 5

stack.pop（）結果：5 4 3 2 1（so：右から左）

あなたはこれを楽しむかもしれません：

        public static bool DepthFirstSearch<T>(this IEnumerable<T> vertices, T rootVertex, T targetVertex, Func<T, IEnumerable<T>> getConnectedVertices, Func<T, T, bool> matchFunction = null)
    {
        if (getConnectedVertices == null)
        {
            throw new ArgumentNullException("getConnectedVertices");
        }
        if (matchFunction == null)
        {
            matchFunction = (t, u) => object.Equals(t, u);
        }
        var directlyConnectedVertices = getConnectedVertices(rootVertex);
        foreach (var vertex in directlyConnectedVertices)
        {
            if (matchFunction(vertex, targetVertex))
            {
                return true;
            }
            else if (vertices.DepthFirstSearch(vertex, targetVertex, getConnectedVertices, matchFunction))
            {
                return true;
            }
        }
        return false;
    }

これは私の告知であり、1つのスタックで十分です。 foreachループの前に逆が行われます。

    /// <summary>
    /// Depth first search implementation in c#
    /// </summary>
    /// <typeparam name="T">Type of tree structure item</typeparam>
    /// <typeparam name="TChilds">Type of childs collection</typeparam>
    /// <param name="node">Starting node to search</param>
    /// <param name="ChildsProperty">Property to return child node</param>
    /// <param name="Match">Predicate for matching</param>
    /// <returns>The instance of matched result, null if not found</returns>
    public static T DepthFirstSearch<T, TChilds>(this T node, Func<T, TChilds> ChildsProperty, Predicate<T> Match) 
        where T:class
    {
        if (!(ChildsProperty(node) is IEnumerable<T>))
            throw new ArgumentException("ChildsProperty must be IEnumerable<T>");

        Stack<T> stack = new Stack<T>();
        stack.Push(node);
        while (stack.Count > 0) {
            T thisNode = stack.Pop();
            #if DEBUG
            System.Diagnostics.Debug.WriteLine(thisNode.ToString());
            #endif
            if (Match(thisNode))
                return thisNode;
            if (ChildsProperty(thisNode) != null) {
                foreach (T child in (ChildsProperty(thisNode) as IEnumerable<T>).Reverse()) 
                    stack.Push(child);
            }
        }
        return null;
    }

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow