인접 목록 구현 그래프

Question

가중치가없는 그래프 및 몇 가지 질문/우려 사항에 대한 인접성 목록을 구현하려고합니다. 나는 꼭지점을 저장할 수있는 링크 된 목록과 꼭지점을 저장할 배열이 필요하다는 것을 알고 있습니다. 현재 (기본) 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; 
     } 

    } 
} 

Answer 1

몇 가지 참고 사항 :

1. 당신은 당신의 노드를 저장하는 고정 된 크기의 배열을 사용합니다. 새로운 노드를 추가하는 동안 자동으로 커지는 arraylist로 전환하십시오.

2. 노드 (next)를 벗어나는 가장자리가 하나만있을 수 있다는 것을 정확하게 알고 있습니까? 여기에 목록을 사용해야합니다.

3. 만큼 그래프가 A에서 B로 실행 가장자리는 B에서에 따라서는 노드 A와 노드 B를

-목록을 가장자리로 추가 할 필요가 간다 돌봐 지시하지 않는 한