1

私は最近、各ノードが配列の要素の異なる配置である bfs 問題を解決していました。しかし、展開されたツリーで訪問したノードを追跡するための適切なデータ構造を思いつくことができませんでした。通常、ノードは異なる文字列であるため、マップを使用してノードを訪問済みとしてマークできますが、上記の場合はどの DS を使用すればよいですか?

4

5 に答える 5

4

次の擬似コードを検討してください。

type Node;  // information pertaining to a node
type Path;  // an ordered list of nodes
type Area;  // an area containing linked neighboring nodes
type Queue; // a FIFO queue structure

function Traverse(Area a, Node start, Node end) returns Path:
    Queue q;
    Node n;
                        // traverse backwards, from finish to start
    q.push(end);        // add initial node to queue
    end.parent = end;   // set first node's parent to itself

    while (not q.empty()):
        n = q.pop();    // remove first element

        if (n == start) // if element is the final element, we're done
            break;

        for (Node neighbor in a.neighbors(n)): // for each neighboring node
            if (neighbor.parent != Null):      // if already visited, skip
                continue;
            neighbor.parent = n;               // otherwise, visit 
            q.push(neighbor);                  // then add to queue

    Path p;             // prepare to build path from visited list

    for (Node previous = Null, current = n;
              previous != current;
              previous = current, current = current.parent):
        p.add(current); // for each node from start to end, add node to p
                        // Note that the first node's parent is itself
                        // thus dissatisfying the loop condition
    return p;

「訪問済みリスト」は、ノードの親として格納されます。これを C++ にコーディングすると、この疑似コードは参照動作に依存しているため、ほとんどのノードを参照またはポインターとして処理することになります。

ノードのフィールドであるエリアから始めます。この領域は、各ノードが他のノードとの関係でどこにあるかを認識しています。1 つの特定のノード (「開始」ノード) から開始し、それをキューにプッシュします。

エリアのトラバースは、エリアから近隣ノードのリストを取得し、それらが既にアクセスされている場合はそれらをスキップし、それ以外の場合は親を設定してキューに追加するだけです。キューから削除されたノードが宛先ノードと等しくなると、トラバーサルは終了します。ノードが最初に検出されたときに、ネイバー ループ中にこのチェックを行うことで、アルゴリズムを少し高速化できます。

注:トラバーサルを開始する前に、エリア内のすべての可能なノードを生成する必要はありません。エリアは、ノードを作成した後、それを追跡することのみを必要とします。これは、文字列または配列の順列を使用しているように見える状況に役立つ可能性があります。開始ノードと終了ノードをエリアにプッシュし、その場で隣接ノードを生成してキャッシュすることができます。それらをベクトルとして保存し、その順序と内容に基づいて等しいかどうかを == 演算子で比較できます。 この例を参照してください。

パスの再構築が容易になるため、トラバーサルは順方向ではなく逆方向に進みます (各親がその前のノードである終了ノードで終了するのではなく、各親がそのノードの後に​​ある開始ノードで終了します)。

データ構造のまとめ

NodeArea親ノードだけでなく、（配列インデックスまたは名前などを介して）一意に識別するために十分な情報を追跡する必要があります。トラバーサルは親セットを持つノードを無視するため、奇妙な動作を避けるために、トラバーサルの前に親ノードを NULL に設定する必要があります。これは、訪問済みの状態も追跡します。訪問済みは (parent != NULL) と同等です。このようにすることで、キュー内のパス全体を追跡する必要がなくなります。これは非常に計算量が多くなります。

Areaのリストを維持するNode必要があり、近隣マップ、またはどのノードが他のどのノードに隣接しているかのマッピングが必要です。このマッピングは、テーブルやより一般的なアプローチから検索するのではなく、関数を使用してオンザフライで生成できる可能性があります。ノードのネイバーを呼び出し元に提供できる必要があります。同様に、すべてのノードの親をクリアするヘルパー メソッドがあると役立つ場合があります。

Path基本的には、ノードの順序付きリストを含むリスト型です。

QueueFIFO キューが使用可能なものです。リンクされたリストでそれを行うことができます。

私の Wuggythovasp++ で構文の強調表示がどのように機能したかが気に入っています。

于 2012-08-01T19:00:13.017 に答える
1 
/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author VAISAKH N
 */
public class BFSME {

public static String path = "";
public static String add = "";

public static void findrec(String temp, String end, String[][] m, int j) {
    if (temp.equals(m[j][1])) {
        add = m[j][0] + temp + end + "/";
        end = temp + end;
        System.out.println(end);
        path = path + add;
        temp = "" + add.charAt(0);
        System.out.println("Temp" + temp);
        for (int k = 0; k < m.length; k++) {
            findrec(temp, end, m, k);
        }
    }
}

public static void main(String[] args) {

    String[][] data = new String[][]{{"a", "b"}, {"b", "c"}, {"b", "d"}, {"a", "d"}};
    String[][] m = new String[data.length][2];
    for (int i = 0; i < data.length; i++) {
        String temp = data[i][0];
        String end = data[i][1];
        m[i][0] = temp;
        m[i][1] = end;
        path = path + temp + end + "/";
        for (int j = 0; j < m.length; j++) {

            findrec(temp, end, m, j);
        }

    }
    System.out.println(path);
}
}
于 2014-03-15T05:25:33.310 に答える
1

少なくとも最初は、Java の Arrays.toString() のようなものを使用/実装し、マップを使用してみることができます。各配置は異なる文字列になるため、少なくともどこかに到達します。

于 2012-08-01T17:58:36.043 に答える
0

理解を深めるために、サンプル コードをここに示します (C# で作成されています)。

  private void Breadth_First_Travers(Node node)
  {
        // First Initialize a queue - 
        // it's retrieval mechanism works as FIFO - (First in First Out)
        Queue<Node> myQueue = new Queue<Node>();

        // Add the root node of your graph into the Queue
        myQueue.Enqueue(node);

        // Now iterate through the queue till it is empty
        while (myQueue.Count != 0)
        {
            // now, retrieve the first element from the queue 
            Node item = myQueue.Dequeue();
            Console.WriteLine("item is " + item.data);

            // Check if it has any left child   
            if (item.left != null)
            {
                // If left child found - Insert/Enqueue into the Queue
                myQueue.Enqueue(item.left);
            }

            // Check if it has right child 
            if (item.right != null)
            {
                // If right child found Insert/Enqueue into the Queue  
                myQueue.Enqueue(item.right);
            }

            // repeat the process till the Queue is empty
        }
   }

ここではサンプル コードをhttp://en.wikipedia.org/wiki/Binary_treeを参照して示します。 ツリーはそれ自体がグラフの一種であるためです。

于 2014-04-08T02:22:54.543 に答える