0

重み付けされていないグラフといくつかの質問/懸念事項の隣接リストを実装しようとしています。エッジを格納するためのリンク リストと、頂点を格納するための配列が必要であることに気付きました。現在、(基本)Node クラスと、特定の頂点へのエッジの追加を処理する Graph クラスがあります。ただし、これはエッジの連結リストを明示的に定義しません。DFS と BFS を実行したいのですが、どうすればよいでしょうか? これらのメソッドを組み込むために既に必要なコードを変更する必要がありますか、それとも今ですか。助けていただければ幸いです。

 // Inside the graph class

  public boolean insertNode(NodeRecord n) {
    int j;

    if (isFull()) return false;
    for (j=0; j<arraySize; j++)
        if (node[j]==null)
            break;
    node[j] = new Node(n);
    graphSize++;
    return true;
}
public boolean insertEdge(int nodeID, EdgeRecord e) {
    int j;

    for (j=0; j<arraySize; j++)
        if (nodeID==((NodeRecord) node[j].item).getID())
            break;
    if (j>=arraySize) return false;
    node[j].next = new Node(e, node[j].next);
            return true;
}

 // inside the node class

    class Node<E> {
   E    item;
   Node<E> next;

Node(E e) {
        item = e;
        next = null;
}

Node(E e, Node<E> newNext) {
        item = e;
        next = newNext;
}

Node(Node<E> n) {  // copy constructor
        item = n.item;
        next = n.next;
 }

 }

   public static void depthFirst(){

    for(int i=0;i<mygraph.arraySize;i++){
        Node counter =mygraph.node[i];
        while(counter!=null){
         System.out.println(" " +counter.item);
         counter= counter.next;
       }

    }
}
4

1 に答える 1

2

コードに関するいくつかの注意事項：

  1. 固定サイズの配列を使用してノードを格納します。新しいノードを追加するときに自動的に大きくなる配列リストに切り替えます。

  2. ノード（）を離れるエッジが1つしかない可能性があることを正しく理解していますnextか？ここでもリストを使用する必要があります。

  3. グラフが方向付けられていない限り、AからBに実行されるエッジもBからAに移動することに注意してください。したがって、ノードAとノードBのエッジリストにグラフを追加する必要があります。

于 2011-04-24T07:43:56.670 に答える