Nachbar von Knoten bestimmen

[mamelinchen]

Wie finde ich herraus, ob ein Knoten einen Nachbarn hat?

Mittels der Adjazenzliste.

Aber wie komme ich da ran?

Und wie muss das ganze aussehen?

for(Knoten v, der : Nachbar von Knoten u)

Wie finde ich das herraus?

 

[Civilazi]

Ich geh mal davon aus, dass du irgendwo / irgendwie (Uni, Schule, was weiß ich) eine Graphenklasse schreibst / geschrieben hast / zumindest dran rankommst.
Woher sollen wir wissen, wie du da an die Adjazenzliste kommst? Woher sollen wir wissen, wie du von nem Knoten an die Nachbarn kommst?
Meine Knoten bieten eine Methode getNeighbours() an, vll. hast du etwas ähnliches?

Mehr Informationen sind hier doch angebracht

 

[mamelinchen]

Sorry, dachte das es allgemein beantwortet werden kann.

Ja ich habe eine.

Der Graph besteht aus:
static HashMap<Integer, Integer> vertexIndex;
// gibt zu einer Knoten-Id Index an, an dem der Knoten in vertices
// und die inzidenten Kanten in adjList abgelegt ist
private ArrayList<V> vertices; // Liste mit allen Knoten
private ArrayList<LinkedList<E>> adjList;

Die Knoten haben ne ID,farbe,entfernung,und vorgänger.

 

[mamelinchen]

public Collection<V> getNeighbours(V v) {
int id = v.getId();
return getNeighbours(id);
}

wie kann ich den jetzt damit arbeiten?
Steh echt aufm Schlauch...

 

[Civilazi]

Die Knoten haben ne ID,farbe,entfernung,und vorgänger.

Das ergibt meiner Meinung nach keinen Sinn. Meinst du die Kanten? was ist der Vorgänger?
Also sagen wir mal so:
Wenn du nen V v hast, kriegst du über v.getId() ja anscheinend die Id. In der HashMap kannst du dann zu dieser Id den Index nachschlagen. Dann schaust du in
List<E> adjEdges = adjList.get(index);
Dann gehst du durch alle inzidenten Kanten, merkst dir die Endknoten, die nicht dein ursprünglicher Knoten v sind und hast deine Nachbarn.

Mal nebenbei: Wofür brauchst du das? Und wer hat die Klasse geschrieben?

 

[mamelinchen]

Für die Breitensuche.

Die Klasse Graph ist von meiner Dozentin.

Die enthält eine Vertex, mit InstanzV. ID
Ich habe VertexNew extends Vertex erzeugt, mit farbe, distanz (um die distanz zum startknoten zu verdeutlichen, alle kantenlängen haben die Länge 1),
und vorgänger, damit man die Knoten einfärbt, nachdem man die besucht hat.

Der Vorgänger ist selber ein Knoten.
an die Methoden selber komme ich nicht ran, da sie alle nicht statisch sind.

Ich dachte mir eher so, das ich eine Collection <V> mache, dort alle Knoten vom gegebenen Graphen übergebe, und die alle als unbesucht markiere, und dann in eine collection alle nachbarn vom startknoten packe, und dann untersuche,ob die unmarkiert sind.
und die dann alle nacheinander ablaufe.

 

[Civilazi]

Aha, na das ist ja schonmal etwas An die Methoden, die Graph anbietet, kommst du ran, indem du einfach den Graphen erzeugst und dann g.methode(bla) einfach ausführst.
Ansonsten klingt das mit der Breitensuche doch nach einem Plan, du musst nur aufpassen, was du wo einfügst und wann ein Knoten als "besucht" gilt, damit du eine echte Breitensuche hast. Also Knoten hinten einfügen, vorn herausnehmen, Nachbarn wieder hinten ran... na ja wie BFS geht wirst du ja wissen
Die Nachbarn müsstest du so bekommen können, wie ich dir schrieb, oder diese Methode getNeighbours(id) benutzen? Irgendwas muss die ja auch tun. Oder hast du die geschrieben und die tut noch nix?

 

[mamelinchen]

JA die Breitensuche hab ich schon

Noch ne letzte Frage:

Mein Code:

			Collection<VertexNew> link =graph.getVertices();
			for (VertexNew a : link) {
				markiere,erhöhe
			}
			while (!queue is leer) {
				VertexNew u = queue.remove();
				Collection<VertexNew> nachbarn = graph.getNeighbours(u);
				for (VertexNew n : nachbarn)

DIe Collection haben alle die Verweise auf die jeweiligen Knoten oder nicht?

Würde das so funzen?

Oder stell ich mir das zu einfach vor?
------------------------------------

Die Graph-Klasse sieht wie folgt aus:

public class Graph <V extends VertexNew, E extends Edge<V>> {

Die Methoden liefern jeweils eine Collection <V>.

Das macht doch aber nichts das ich eine Collection <VertexNew>.erzeuge, V ist doch selber auch eine.

ODER?

 

[Civilazi]

			Collection<VertexNew> link =graph.getVertices();
			for (VertexNew a : link) {
				markiere,erhöhe
			}
			while (!queue is leer) {
				VertexNew u = queue.remove();
				Collection<VertexNew> nachbarn = graph.getNeighbours(u);
				for (VertexNew n : nachbarn)

DIe Collection haben alle die Verweise auf die jeweiligen Knoten oder nicht?

Würde das so funzen?

Ja, wenn die Methoden das tun, wie sie auch heißen, dann sollte das so funktionieren.
Klappts denn?