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

Datenstrukturen für Graphen

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.

Jung (http://jung.sourceforge.net)

Graph<Integer, String> g = new SparseMultigraph<Integer, String>(); 
g.addVertex((Integer)1); 
g.addVertex((Integer)2); 
g.addEdge("Edge1", 1, 2);

Neo4j (http://www.neo4j.org)

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

 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;
   }
}