Реализация списка смежности графа - PullRequest
0 голосов
/ 24 апреля 2011

Я пытаюсь реализовать список смежности для невзвешенного графа и несколько вопросов / проблем. я понимаю, что мне нужен связанный список для хранения ребер и массив для хранения вершин. В настоящее время у меня есть (базовый) класс 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;
       }

    }
}

1 Ответ

2 голосов
/ 24 апреля 2011

Несколько примечаний к вашему коду:

  1. Вы используете массив фиксированного размера для хранения ваших узлов. Переключитесь на массив, который автоматически увеличивается при добавлении новых узлов.

  2. Правильно ли я понимаю, что у вас может быть только одно ребро, выходящее из вашего узла (next)? Вы также должны использовать список здесь.

  3. Пока ваш график не направлен, позаботьтесь о том, чтобы ребро, проходящее от А к В, также переходило от В к А, и, следовательно, вы должны добавить его в списки ребер узла А и узла В.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...