Gerichtete Graphen und ungerichtete Graphen - Java

Ich bin die Implementierung einiger algorithmen zu lehren mich über Graphen und wie mit Ihnen zu arbeiten. Was würden Sie empfehlen, ist der beste Weg, um dies in Java?

Ich wollte nur Fragen, u, wenn u geben kann, nur eine kurze Hilfe mit einer kurzen sehr einfach die Klasse definition für gerichtete Graphen und gewichteten gerichteten Graphen?

Schaute ich über das web, aber ich will nicht eine Umsetzung, nur eine kurze definition der Klassen....was u denken ist die beste Datenstruktur zu verwenden ? Angrenzenden Listen?

Für eine ungerichtete Graph i definiert es wie folgt:

public interface Graph { 
  Collection vertices();  //returns a collection of all the 
        //  Vertex objects in the graph 
  Collection edges();  //returns a collection of all the 
     //  Edge objects in the graph 
  Collection incidentEdges(Vertex v); //returns a collection of  
       //  Edges incident to v 
  boolean isAdjacent(Vertex v, Vertex w); //return true if v and     
}                 //  w are adjacent 

public class Vertex { 
  public boolean visited;  //initially false for all vertices 
} 

public class Edge { 
  Vertex v1, v2;     //undirected edge 
  Vertex opposite(Vertex v); //given a vertex return the one 
}          //at the other end of this edge
möglich, Duplikat der die Daten Struktur für gerichtete Graphen, so dass Knoten schnell löschen?

InformationsquelleAutor Patric | 2013-02-17

  1. 1

    Hier ist eine einfache Implementierung (dies sollte gut genug sein für viele grundlegende use cases): 

    public class Graph { 
  public List<Node> nodes = new ArrayList<Node>();
}                

public class Node{
  public List<Node> neighbors = new ArrayList<Node>();
 //here you can add stuff like "public boolean visited;", if your algorithm requires it
}

    (Dies ist nur ein Beispiel - es gibt Tonnen von Möglichkeiten zur Implementierung einer graph-Struktur).

    InformationsquelleAutor Amit Portnoy

  2. 0

    Die Datenstruktur zu verwenden, hängt von dem Zweck des Codes... Listen in der Regel tun ziemlich gut, aber wenn der graph stark verbunden (die meisten Knoten sind verbunden, um die meisten der Knoten), dann eine Liste zu umständlich ist, und eine matrix, eine Art ist in der Regel bevorzugt werden.

    Zum Beispiel, verwenden Sie eine matrix, halten ein Vektor von Knoten, dann verwenden Sie ein 2-dimensionaler Vektor von ganzen zahlen an Referenz-Knoten.

    Auch, für einen leichten Klasse, die Sie nicht deklarieren müssen, eine Klasse für die Knoten: Sie können Funktionen zur Verfügung stellen, das hinzufügen von Knoten und Kanten, und können Sie identifizieren, wie die Elemente mit den Ganzzahlen.

    Dass Node-oder Edge-Klassen können dann geeignet sein, wenn Sie planen, Unterklasse diese (zum Beispiel, könnte sein nützlich, wenn man eine GUI, die Darstellung eines Graphen), aber wenn Sie die Grafik für einige algorithmen, die Identifizierung von Knoten/Kanten mit ganzen zahlen ist schneller und einfacher.

    InformationsquelleAutor AkiRoss

Schreibe einen Kommentar