Graphen

Description

13. Klasse Informatik (Datenstrukturen) Note on Graphen, created by Ann-Kathrine Buchmakowsky on 27/04/2020.
Ann-Kathrine Buchmakowsky
Note by Ann-Kathrine Buchmakowsky, updated more than 1 year ago
Ann-Kathrine Buchmakowsky
Created by Ann-Kathrine Buchmakowsky over 4 years ago
9
0

Resource summary

Page 1

Die Klasse Graph

 Die Klasse Graph stellt einen ungerichteten, kantengewichteten Graphen dar. Es können Knoten- und Kanten Objekte hinzugefügt und entfernt, flache Kopien der Knoten- und Kantenlisten des Graphen angefragt und Markierungen von Knoten und Kanten gesetzt und überprüft werden. Des Weiteren kann eine Liste der Nachbarn eines bestimmten Knoten, eine Liste der inzidenten Kanten eines bestimmten Knoten und die kante von einem bestimmten Knoten zu einem anderen Knoten angefragt werden. Abgesehen davon kann abgefragt werden, welches Knotenobjekt zu einer bestimmten ID gehört und ob der Graph leer ist

Methoden

Konstruktor Graph () Ein Objekt vom Typ Graph wird erstellt. Der von diesem Objekt repräsentierte Graph ist leer.

Auftrag void addVertex (Vertex pVertex) Der Auftrag fügt den Knoten pvertex vom Typ Vertex in den Graphen ein, sofem es noch keinen Knoten mit demselben ID-Eintrag wie Vertex im Graphen gibt und vertex eine ID ungleich null hat. Ansonsten passiert nichts.

Auftrag void addEdge (Edge pEdge) Der Auftrag fügt die Kante pEdge in den Graphen ein, sofern beide durch die kante verbundenen Knoten im Graphen enthalten sind, nicht identisch sind und noch keine Kante zwischen den beiden Knoten existiert. Ansonsten passiert nichts.

Auftrag void removeVertex (Vertex pVertex) Der Auftrag entfernt den Knoten pvertex aus dem Graphen und löscht alle kanten, die mit ihm inzident sind. Ist der Knoten pvertex nicht im Graphen enthalten, passiert nichts.

Auftrag void removeEdge (Edge pEdge) Der Auftrag entfernt die Kante pEdge aus dem Graphen. Ist die Kante pEdge nicht im Graphen enthalten, passiert nichts.

Anfrage Vertex getVertex(String pID) Die Anfrage liefert das Knotenobjekt mit pID als ID. Ist ein solches Knoten Objekt nicht im Graphen enthalten, wird null zurückgeliefert.

Anfrage List<Vertex> get Vertices () Die Anfrage liefert eine neue Liste aller Knoten Objekte vom Typ ListVertex>. Enthält der Graph keine Knoten Objekte, so wird eine leere Liste zurückgeliefert.

Anfrage List <Vertex> get Neighbours (Vertex pVertex) Die Anfrage liefert alle Nachbarn des Knotens pVertex als neue Liste vom Typ List<Vertex>. Hat der Knoten Vertex keine Nachbarn in diesem Graphen oder ist gar nicht in diesem Graphen enthalten, so wird eine leere Liste zurückgeliefert.

Anfrage List<Edge> getEdges() Die Anfrage liefert eine neue Liste aller Kanten Objekte vom Typ List<Edge>. Enthält der Graph keine Kanten Objekte, so wird eine leere Liste zurückgeliefert.

Anfrage List<Edge> getEdges (Vertex pVertex) Die Anfrage liefert eine neue Liste aller inzidenten Kanten zum Knoten Vertex. Hat der Knoten Vertex keine inzidenten Kanten in diesem Graphen oder ist gar nicht in diesem Graphen enthalten, so wird eine leere Liste zurückgeliefert.

Anfrage Edge getEdge (Vertex Vertex, Vertex pAnothervertex) Die Anfrage liefert die Kante, welche die Knoten pVertex und pAnotherVertex verbindet, als Objekt vom Typ Edge. Ist der Knoten pVertex oder der Knoten panothervertex nicht im Graphen enthalten oder gibt keine Kante, die beide Knoten verbindet, so wird null zurückgeliefert.

Auftrag void setAllVertexMarks (boolean pMark) Der Auftrag setzt die Markierungen aller Knoten des Graphen auf den Wert pMark.

Anfrage boolean allverticesMarked() Die Anfrage liefert true, wenn die Markierungen aller Knoten des Graphen den Wert true haben, ansonsten false.

Auftrag void setAllEdgeMarks (boolean pMark) Der Auftrag setzt die Markierungen aller kanten des Graphen auf den Wert pMark.

Anfrage boolean allEdgesMarked() Die Anfrage liefert true, wenn die Markierungen aller Kanten des Graphen den Wert true haben, ansonsten False.

Anfrage boolean isEmpty() Die Anfrage liefert true, wenn der Graph keine Knoten enthält, ansonsten false.

Page 2

Die Klasse Vertex

Die Klasse Vertex stellt einen einzelnen Knoten eines Graphen dar. Jedes Objekt dieser Klasse verfügt über eine im Graphen eindeutige ID als String und kann diese ID zurückliefem. Darüber hinaus kann eine Markierung gesetzt und abgefragt werden.

Methoden

Konstruktor Vertex(String pID) Ein neues Objekt vom Typ Vertex mit der ID pID wird erstellt. Seine Markierung hat den Wert false.

Anfrage String getID() Die Anfrage liefert die ID des Knotens als String.

Auftrag void setMark (boolean pMark) Der Auftrag setzt die Markierung des Knotens auf den Wert von pMark.

Anfrage boolean isMarked () Die Anfrage liefert true, wenn die Markierung des Knotens den Wert true hat, ansonsten false.

Page 3

Die Klasse Edge

Die Klasse Edge stellt eine einzelne, ungerichtete Kante eines Graphen dar. Beim Erstellen werden die beiden durch sie zu verbindenden Knoten Objekte und eine Gewichtung als double übergeben. Beide Knoten Objekte können abgefragt werden. Des Weiteren können die Gewichtung und eine Markierung gesetzt und abgefragt werden.

Methoden

Konstruktor Edge (Vertex pVertex, Vertex pAnother Vertex, double pWeight) Ein neues Objekt vom Typ Edge wird erstellt. Die von diesem Objekt repräsentierte Kante verbindet die Knoten pVertex und panotherVertex mit der Gewichtung weight. Ihre Markierung hat den Wert false.

Auftrag void setWeight (double pweight) Der Auftrag setzt das Gewicht der Kante auf den Wert pweight.

Anfrage double getWeight () Die Anfrage liefert das Gewicht der Kante als double.

Anfrage Vertex[] getVertices() Die Anfrage gibt die beiden Knoten, die durch die kante verbunden werden, als neues Feld vom Typ Vertex zurück. Das Feld hat genau zwei Einträge mit den Indexwerten 0 und 1.

Auftrag void setMark (boolean pMark) Der Auftrag setzt die Markierung der Kante auf den Wert pMark.

Auftrag void set Weight (double pWeight) Der Auftrag setzt das Gewicht der Kante auf den Wert pweight.

Anfrage boolean isMarked() Die Anfrage liefert true, wenn die Markierung der Kante den Wert true hat, ansonsten false.

Show full summary Hide full summary

Similar

Stilmittel
Cassibodua
ein kleines Informatik Quiz
AntonS
Datenstrukturen
Ann-Kathrine Buchmakowsky
minimale Spannbäume und ihre Algorithmen
Ann-Kathrine Buchmakowsky
Such- und Sortieralgorithmen
Ann-Kathrine Buchmakowsky
Abiturvorbereitung (6 Monate)
AntonS
Mathe Themen
barbara91
Epochen und Literaturströmungen für das Abitur 2015
barbara91
Stochastik
barbara91