32

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

これまでの私のコードは次のとおりです（コンストラクターを除いて、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;
}

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

ウィキペディアと比較して、私の訪問方法を比較すると、次のようになります。 比較

私の物は向きを変えて右から左に始まっているようです。

何が原因か知っていますか？（また、私の実装に関するアドバイスをいただければ幸いです）

編集：私は答えを得ましたが、それでも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;
}
4

6 に答える 6

60

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

他の人が指摘しているように、あなたはスタックの次のノードを左から右の順にプッシュしています。つまり、スタックの順序が逆になるため、右から左に飛び出します。スタックは後入れ先出しです。

GetConnectedVerticesにリストではなくスタックを構築させることで、問題を修正できます。このようにして、接続された頂点が2回反転されます。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検索に使用している場合、検索基準が満たされると反復は中止されます。結果が早期に見つかった場合は、完全なトラバーサルを実行する必要はありません。

于 2011-04-27T15:43:29.880 に答える
6

@EricのDFSトラバーサルのコードを一般化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);
于 2012-09-21T19:54:01.320 に答える
1

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

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

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

于 2011-04-27T13:35:46.610 に答える
0

アイテムは、プッシュされたときと逆の順序でスタックからポップされます。

stach.push() の結果: 1 2 3 4 5

stack.pop() の結果: 5 4 3 2 1 (つまり、右から左へ)

于 2011-04-27T13:36:06.107 に答える
0

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

        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;
    }
于 2011-04-27T14:35:28.047 に答える