Ungewichtete Graphen mit Adjazenzlisten

Question

Ich bin neu in der Programmierung und versuche, Datenstrukturen selbst zu lernen. Ich versuche, eine nicht gewichtete Graphklasse mit Adjazenzlisten zu implementieren, aber ich habe Probleme beim Implementieren der Methode getAdjacentVertices und ich weiß nicht genau, wie die addEdge-Methode wirklich funktioniert, speziell wie die Methode insertAtTheBeginning implementiert wird. Bitte helfen Sie mir, das Buch ich verwende wirklich nicht über diese Themen erklärt. *

enter code here 
public class Graph { 
    private ArrayList<Integer> vertices; 
    private ListNode[] edges; 
    private int vertexCount = 0; 
    public Graph(int vertexCount){ 
     this.vertexCount = vertexCount; 
     vertices = new ArrayList<Integer>(); 
     edges = new ListNode[vertexCount]; 
     for(int i = 0; i < vertexCount; i++){ 
      vertices.add(i); 
      edges[i] = new ListNode(); 
     } 
    } 
    public void addEdge(int source, int destination){ 
     int i = vertices.indexOf(source); 
     int j = vertices.indexOf(destination); 
     if(i != -1 || j != -1){ 
      edges[i].insertAtBeginning(destination); 
      edges[j].insertAtBeginning(source); 
     } 
    } 
    public int getNumberVertices() { 
     return vertexCount; 
    } 
    public Object getAdjacentVertices(int currentVertex) { 

    } 
} 

Answer 1

Um Ihre Fragen zu beantworten,

• getAdjacentVertices(i) können einfach das i -te Element von edges zurückzukehren.
• addEdge() muss nicht an den Anfang hinzugefügt werden. Wenn Sie nicht einen bestimmten Grund haben, eine Reihenfolge in der Nachbarliste festzulegen, benötigen die meisten Graphalgorithmen keinen.

Einige andere Punkte:

• Graph Eckpunkte werden traditionell 0-n nummeriert - 1. Also, wenn Ihr Scheitel eine Nutzlast haben (Namen, Kosten usw.), können Sie mit dem tun weg vertices Array.
• Betrachten Sie Ihre Klasse zu benennen UndirectedGraph um deutlich zu machen, dass die Graph ungerichtet ist (das heißt, wann immer v in der Liste der u erscheint ‚s Nachbarn, u erscheint auch in der Liste der v‘ s Nachbarn.
• Erwägen Sie die Verwendung ein List<Integer> für Ihre Adjazenzlisten und setzen es als LinkedList. die meisten Graphenalgorithmen nur die Fähigkeit, müssen über Adjazenzlisten laufen, nicht random access (die ein ArrayList zur Verfügung stellt).
• addEdge() führt keine Validierung. Je nachdem, wo der Eingang aus, möchten Sie vielleicht überprüfen, dass 0 ≤ u, v < vertexCount und dass die Kante (u, v) noch nicht existiert.

Ich habe die main() Methode in der gleichen Klasse der Kürze wegen.

import java.util.LinkedList; 
import java.util.List; 
import java.util.Vector; 

public class UndirectedGraph { 
    private Vector<List<Integer>> edges; 
    private int vertexCount = 0; 

    public UndirectedGraph(int vertexCount) { 
    this.vertexCount = vertexCount; 
    edges = new Vector<List<Integer>>(vertexCount); 
    for (int i = 0; i < vertexCount; i++){ 
     edges.addElement(new LinkedList<Integer>()); 
    } 
    } 

    public void addEdge(int u, int v) { 
    edges.get(u).add(v); 
    edges.get(v).add(u); 
    } 

    public int getNumberVertices() { 
    return vertexCount; 
    } 

    public Object getAdjacentVertices(int u) { 
    return edges.get(u); 
    } 

    public static void main(String [] args) { 
    UndirectedGraph g = new UndirectedGraph(4); 
    g.addEdge(0, 1); 
    g.addEdge(0, 2); 
    g.addEdge(1, 2); 
    g.addEdge(1, 3); 
    g.addEdge(2, 3); 

    for (int i = 0; i < g.getNumberVertices(); i++) { 
     System.out.println("Neighbors of node " + i + ": " + g.getAdjacentVertices(i)); 
    } 
    } 
}