Adjazenzliste

[Nirvana]

Hallo wir haben in der Vorlesung Graphen besprochen und dabei kamen zwei Arten von Graphen am Pc zu erstellen: Adjazenmatrix(mithilfe 2 dimensionalen Arrays) und Adjazenzliste.
Der gesamte Graph wird dabei als (einfach verkettete) Liste dargestellt.Die Knoten der Liste sind die Knoten des Graphen und stellen wiederum Listen dar.
Ich möchte zuerstmal einen ungerichteten Graphen ohne Gewichtungen ansehen.

int AnzKnoten;
		ArrayList<Integer>  gListe[] = new ArrayList[AnzKnoten];  
		for ( int i = 0; i<AnzKnoten ; i++ ){
			gListe[i] = new ArrayList<Integer>();
			
			for (int s = 0; s<AnzKnoten;s++){
				if (Element[s].nachbar(Element[i])) 
                                       gListe[s].add(i);
			}	
		}

FRAGEN:
1) Oder muss hier eine LinkedList her? Aber wie fügt man in diese Elemente ein? Diese haben ja nicht nur einen Wert sondern auch eine referenz auf den nächsten Knoten.
2) Wie kann ich am besten die Methode nachbar programmieren? Wie gebe ich den PC meine Graphik vor?

public boolean nachbar(int Element){
// soll herausfinden ob zwei Elemente Nachbarn sind.
}

 

[tribalup]

Du solltest den Graphen auch schondirekt als Liste von Listen an dein Program übergeben.
Darauf lassen sich dann alle weiteren Operationen durchführen.

Bsp:

K(0): (1)
K(1): (0,2,4)
K(2): (1,3)

Usw...

 

[Nirvana]

Ich bin absoluter anfänger und verstehe nicht wie ich das programmieren soll.
Du bist leider nicht wirklich auf meine Fragen eingegangen.

 

[tribalup]

zu 1: Es muss keine LinkedList her sondern eine Liste von Listen.
Dabei stellen die Elemente der ersten Liste die Knoten des Graphen dar und die Elemente der zweiten Liste die Nachbarn:
Bsp: K(0): (1,2) bedeutet, dass der Knoten 0 die Nachbarn 1 und 2 hat.

zu 2: Die Medthode schaut einfach ob der übergebene Knoten in der in der Liste K(i) liegt.

 

[Jodo]

Ich würde eine Klasse schreiben, die einen Knoten darstellt. Diese enthält dann den Wert des Knotens und eine Liste mit allen Nachbarknoten.
Weil was du gemacht hast sieht mehr nach einer Adjazenzmatrix aus.

Um zu prüfen ob 2 Knoten benachbart sind, implementierst du die nachbar()-Methode in diese Knotenklassen, und prüfst dann ob der Knoten mit dem Parameter-Wert in der Liste ist. Fall neine -> nicht benachbart

 

[tribalup]

Ich würde eine Klasse schreiben, die einen Knoten darstellt. Diese enthält dann den Wert des Knotens und eine Liste mit allen Nachbarknoten.
Weil was du gemacht hast sieht mehr nach einer Adjazenzmatrix aus.

Um zu prüfen ob 2 Knoten benachbart sind, implementierst du die nachbar()-Methode in diese Knotenklassen, und prüfst dann ob der Knoten mit dem Parameter-Wert in der Liste ist. Fall neine -> nicht benachbart

Das wäre auf jeden Fall schön objektorientiert.

 

[Nirvana]

sry, war falsch...

 

[tribalup]

Benutze bitte den Ansatz von Jodo da dieser wesentlich objektorientierter ist.

Hier meine main. Daraus kann man sich mit ein bisschen nachdenken die Klasse Knoten selber zusammenbauen.

	public static void main(String[] args)
	{
		//4 Knoten
		Knoten node0=new Knoten(0);
		Knoten node1=new Knoten(1);
		Knoten node2=new Knoten(2);
		Knoten node3=new Knoten(3);
		
		//Knoten 0 hat die Nachbarn 1, 2 und 3
		node0.addNode(node1);
		node0.addNode(node2);
		node0.addNode(node3);
		
		//Knoten 1 hat die Nachbarn 0 und 2
		node1.addNode(node0);
		node1.addNode(node2);
		
		//Knoten 2 hat die Nachbarn 0 und 1
		node2.addNode(node0);
		node2.addNode(node1);
		
		//Knoten 3 hat den Nachbarn 0
		node3.addNode(node0);
		
		//test, sollte stimmen
		if(node3.isNeighbor(node0))
		{
			System.out.println("stimmt");
		}
		
		//test, sollte nicht stimmen
		if(node3.isNeighbor(node1))
		{
			System.out.println("stimmt nicht");
		}
	}

 

[Nirvana]

Danke für die Auflistung der methoden. Mir machen mehr die Grundsteine Probleme.

Klasse, die Knoten darstellt und den Wert des Knotens erhält ist leicht zu machen.
Aber wie erstelle ich eine Liste mit allen Nachbarknoten? Der Graph kann doch soviele Nachbarn haben wie er will. Ich wollte vorher in den Konstruktor die Nachbarn reinscheiben, bin mir aber nicht sicher ob das okay ist, wegen der Anzahl der Nachbarn.

public class Knoten<T> {
 
    public T inhalt;
    ArrayList<Knoten<T>> list = new ArrayList<Knoten<T>>(2);
 
    public Knoten(T elem, ArrayList Liste){
        inhalt = elem;
        list = Liste;
}

 

[tribalup]

Ich verstehe nicht wo nun genau das Problem liegt, ich hab bereits knoten als nachbarn hinzugefügt und es ist möglich die Nachbarn eines Knotens auszugeben.

Ein Graph hat keine Nachbarn, ein knoten hat welche.
Und nein ein knoten kann nicht soviele nachbarn haben wie er will sondern höchstens n - 1.

Erkläre bitte genauer wo du nicht weiterkommst bzw. welche Anforderunen du als nicht erfüllt betrachtest.

 

[Jodo]

Hier mal ein Ansatz.

public class Knoten {
     private int wert;
     private List<Knoten> nachbarn;

     public Knoten(int wert) {
          this.wert = wert;
          this.nachbarn = new LinkedList<Knoten>();
     }
}

Dann brauchst du eben noch Methoden ob einen weiteren Nachbarn hinzuzufügen und auf Nachbarn prüfen. Wenn du nicht willst, dass der Graph geändert wird, kannst du auch mit einer Array arbeiten und das dem Konstruktor übergeben. Aber laut Aufgabenstellung von dir, muss es ne Liste sein?!

Die Methoden von tribalup geben dir ja hinweise wie du die weiteren Methoden schreiben/überschreiben musst

 

[hüteüberhüte]

Vielleicht solltest du dich bei deinen Aufgaben erst mal ein bisschen in die Materie einlesen. Hier ein paar Links:

Liste (Datenstruktur) ? Wikipedia
Verkettete Liste - Tutorials - spieleprogrammierer.de
Tutorial: Algorithmen und Datenstrukturen für Spiele - verkettete Liste - YouTube

Binärbaum ? Wikipedia
12.01.2 Baum als Datenstruktur - YouTube
JAVA Tutorial Deutsch #60 - Binärer Suchbaum [GER] [HD] - YouTube

Für eine verkettet Liste brauchst du eigentlich nur zwei Klassen: das Element selbst und eine Klasse, mit der du die Listenelemente managen kannst

 

[Daniberto]

Hallo,

ich habe das eigentlich ähnlich gelöst. Ich habe auch eine Liste erstellt für alle Knoten des Graph und für jeden Knoten eine Liste mit seinen Nachbarn. So kann man zu jeder Zeit Knoten hinzufügen oder löschen.

Ich habe nun folgendes Problem: Ich benötige für den Graph verschiedene Arten von Knoten mit teils gleichen – aber auch mit unterschiedlichen – Eigenschaften.
Beispielsweise soll eine Knoten-Klasse eine Schranke darstellen.

Momentan habe ich ein Interface geschrieben, die verschiedenen Knoten-Klassen erben von dem Interface die gemeinsamen Eigenschaften.
Sollte ich hier vielleicht eher eine abstrakte Klasse nutzen?

Die Nachbarn-Liste steht momentan in dem Interface. Ist dies die eleganteste Lösung?

MfG,
Daniberto

 

[Xyz1]

Ist zwar Weihnachten, aber da muss man doch nicht gleich Leichen ausbuddeln!!!!

Ich erkenne aber ,die Basics habt ihr verstanden.