0

小さな問題があり、あなたの意見を聞きたいです。

他のドキュメントを参照できるドキュメントを扱っています。任意のドキュメントから始めて、このドキュメントが参照するすべてのドキュメントの ID を取得する必要があります。問題は、循環参照が許可されているため、A ref B ref C の場合、C が A を参照でき、ループに入るということです。C# でこの問題を解決するにはどうすればよいですか?

小さな例:

これがドキュメントを表すクラスであるとします。

public class Document
{
    public Document(int id)
    {
        this.ID = id;
    }

    private int m_ID;

    public int ID
    {
        get { return m_ID; }
        set { m_ID = value; }
    }

    private List<Document> m_Children = new List<Document>();

    public List<Document> Children
    {
        get { return m_Children; }
        set { m_Children = value; }
    }

    private List<Document> m_Parent = new List<Document>();

    public List<Document> Parent
    {
        get { return m_Parent; }
        set { m_Parent = value; }
    }

    public Document AddChild(Document child)
    {
        child.Parent.Add(this);
        this.Children.Add(child);

        return child;
    }

    public Document AddChild(int child)
    {
        Document d = new Document(child);

        return AddChild(d);
    }
}

次に、いくつかの参照を持つ Document クラスを作成しましょう。

public static Document CreateReferences()
{
    Document d = new Document(1);

    Document temp = d.AddChild(2);

    for (int i = 3; i < 6; i++)
    {
        temp = temp.AddChild(i);
    }

    temp.AddChild(d);

    return d;
}

今、次のような Document クラスにメソッドを実装する必要があります

public List<int> GetReferencedDocuments()
{    }

それを行う最善の方法は何ですか？特定のアルゴリズムを実装できますか?

どんな提案でも大歓迎です！

ありがとう

4

4 に答える 4

4

任意のツリートラバーサルアルゴリズムで問題ありません。

作成するドキュメントのリストだけでなく、まだチェックしていないドキュメントのキューを維持し、最初のドキュメントをそのリストに追加します。

次に、キューが空でないときに、次のドキュメントを取得します（リストにまだ含まれていない場合）。次にそれを追加し、参照されているすべてのドキュメントをキューに追加します。

List<Document> FoundDocs = new List<Documents();
Queue<Document> DocsToSearch = new Queue<Document>();

DocsToSearch.Enqueue(StartDoc);

while(DocsToSearch.Count != 0)
{
    Document Doc = DocsToSearch.Dequeue();
    if(!FoundDocs.Contains(Doc))
    {
        FoundDocs.Add(Doc);
        foreach(var ChildDoc in Doc.Children)
        {
            DocsToSearch.Enqueue(ChildDoc);
        }
    }
}
于 2011-07-01T08:16:26.177 に答える
0

The best way is to do a depth first search or a breadth first search

于 2011-07-01T08:15:18.213 に答える
0

この種の再帰的データに対する再帰的検索を解決するには、主に 2 つのアプローチがあります。マーキングまたは記録です。

マーキング: ドキュメントをリストするたびに、閲覧済みとしてフラグを立てます。フラグ付きドキュメントを処理しません。

したがって、GetReferenceDocuments は次のようになります。

GetReferencedDocuments (開始点)

if(startpoint.flaged) は null を返します

startpoint.flag

新しいリストの結果 = 開始点

foreach(サブドキュメント内

ドキュメント.子)

result.append(getreferenceddocuments(subdocuments))// null でない場合

記録: 同様のアプローチですが、フラグ インジケーターは既に参照されているドキュメントのリスト (ID の別のリストかもしれません) に置き換えられ、フラグ チェックはこのリストでこのドキュメントを検索します。

オブジェクト、サイズ、スケールに応じて、どちらの方法でも機能します。文書オブジェクトを変更できない場合は、それらをリストする必要があります。スキャンに 100 万件のドキュメントがある可能性がある場合は、それらを一覧表示する必要はありません。

于 2011-07-01T08:30:28.510 に答える
0

実装例:

public List<int> GetReferencedDocuments()
{    
    var referencedIds = new List<int>();
    var queue = new Queue<Document>(this);
    while (queue.Count > 0)
    {
         var newDocuments = queue.Dequeue().Children
                                           .Where(d => !referencedIds.Contains(d.ID))
         foreach (Document newDocument in newDocuments) 
         {
             queue.Enqueue(newDocument);
             referencedIds.Add(newDocument.ID);
         }
    }
    return referencedIds;
}
于 2011-07-01T08:34:35.123 に答える