Kurs:Algorithmen und Datenstrukturen (hsrw)/Vorlesung/Datenstrukturen fuer Graphen

Links hinzufügen
Aus Wikiversity



Startseite
Vorlesung


Datenstrukturen für Graphen[Bearbeiten]

Auf dieser Seite werden die Datenstrukturen für Graphen behandelt. In Java gibt es keine hauseigene Graphimplementierung, aber es gibt diverse Pakete für verschiedene Anwendungen. 

Graph<Integer, String> g = new SparseMultigraph<Integer, String>();

g.addVertex((Integer)1);

g.addVertex((Integer)2);

g.addEdge("Edge1", 1, 2);

GraphDatabaseService= new 
"GraphDatabaseFactory().newEmbeddedDatabase(“PATH”);

Transaction tx = graphDb.beginTx();

try{

   Node firstNode = graphDb.createNode();

   Node secondNode = graphDb.createNode();

   Relationship relationship = firstNode.createRelationshipTo(secondNode, 
    … );

   tx.success();

}finally{

   tx.finish();

}

Die allgemeine Schnittstelle für die Vorlesung ist: 

 public interface Graph {
   public int addNode();
   public boolean addEdge (int orig, int dest);
}

Implementierung Adjazenzliste[Bearbeiten]

 public class AdjazenzListGraph implements Graph {
   private int [][] adjacencyList=null;

   //Knoten hinzufügen:
   public int addNode() {
      int nodeNumber = (adjacencyList ==null)?0: adjacencyList.length;
      int [][] newAdjacencyList= new int [nodeNumber+1][];
      //alte adjacencyList kopieren
      for (int i=0; i< nodeNumber; i++) 
         newAdjacencyList [i]=adjacencyList[i];
      //neuer Knoten hat noch keine Kanten
      newAdjacencyList[nodeNumber] =null; 
      adjacencyList=newAdjacencyList;
      return nodeNumber+1;
   }

   //Kante hinzufügen:
   public boolean addEdge (int orig, int dest){
      int nodeNumber = (adjacencyList == null)? 0: adjacencyList.length;
      if (orig > nodeNumber || dest > nodeNumber || orig < 1 || dest < 1 )
         return false;
      if (adjacencyList[orig-1] != null)
         for (int n : adjacencyList[orig-1])
            //Kante bereits vorhanden?
            if (n==dest) return false; 
      //Erste Kante am Knoten orig?
      if ( adjacencyList[orig-1] == null ) { 
         adjacencyList [orig-1] = new int[1];
         adjacencyList[orig-1][0]=dest;
      }  
      else {
         int[] newList= new int[adjacencyList[orig-1].length+1];
         System.arraycopy(adjacencyList[orig-1],0,newList,0,adjacencyList[orig-1].length);
         newList[adjacencyList[orig-1].length]=dest;
         adjacencyList [orig-1]=newList;
      }
      return true;
   }
}


Discussion


Abgerufen von „https://de.wikiversity.org/w/index.php?title=Kurs:Algorithmen_und_Datenstrukturen_(hsrw)/Vorlesung/Datenstrukturen_fuer_Graphen&oldid=629168“