圖的鄰接列表的實現

我正在嘗試實現非加權圖的鄰接表以及一些問題/疑慮。我知道我需要一個鏈表來存儲邊和一個數組來存儲頂點。目前我有一個（基本的）節點類和一個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; 
     } 

    } 
}

來源

2011-04-24 dawnoflife

您的代碼的幾個注意事項：

您使用固定大小的陣列來存儲您的節點。切換到在添加新節點時自動增長的數組列表。
我是否正確理解您可能只有一條邊離開您的節點（next）？你也應該在這裏使用一個列表。
只要你的圖形不針對要小心，從運行到B的邊緣也變爲從B到A，因此你必須將它添加到邊緣列表節點A和節點B

來源

2011-04-24 07:43:56 Howard

輸入是固定的，所以我不需要arraylist。我理解你關於鏈接列表問題的觀點，這是我上面發佈的一個問題。然而，我發現我可以通過一個簡單的循環來訪問特定節點的所有邊緣，所以我不是一個真正的鏈表。代碼負責處理非定向問題。我的問題是如何去編碼的DFS和BF方法 – dawnoflife 2011-04-24 08:11:12

在那裏添加了一些代碼。希望它是有道理的。 – dawnoflife 2011-04-24 08:17:34

圖的鄰接列表的實現

回答

相關問題