Adjazenzliste
- Themenstarter Missy
- Beginndatum
- Status
mic_checker
Top Contributor
Adjazenzlisten können alternativ zu einer Adjazenzmatrix verwendet werden. Abhängig vom Anwendungsfall eignet sich eher Matrix oder Liste.
Was genau ist dein Problem Missy?
Willst du eine simple Adjazenzliste oder eine Adjazenzliste als Liste von Listen ? D.h. Die einzelnen Listen können natürlich anstatt ein Array zu verwenden auch als Liste verwaltet werden.
Was genau ist dein Problem Missy?
Willst du eine simple Adjazenzliste oder eine Adjazenzliste als Liste von Listen ? D.h. Die einzelnen Listen können natürlich anstatt ein Array zu verwenden auch als Liste verwaltet werden.
Also ich habe ein 2d array,
und auf den möchte ich den Dijkstra Alg. verwenden.
Das geht ja bekanntlich nur, wenn ich vorher meinen 2D Array in einen "Graphen" umgewandelt habe, sprich:
Ich brauche deshalb eine Adjazenzliste.
Mein 2d array hat 44 Felder. 4 Spalten & 11 Reihen, wowür ich eine Adjazenzliste bräuchte.
Gruss
Missy
und auf den möchte ich den Dijkstra Alg. verwenden.
Das geht ja bekanntlich nur, wenn ich vorher meinen 2D Array in einen "Graphen" umgewandelt habe, sprich:
Ich brauche deshalb eine Adjazenzliste.
Mein 2d array hat 44 Felder. 4 Spalten & 11 Reihen, wowür ich eine Adjazenzliste bräuchte.
Gruss
Missy
mic_checker
Top Contributor
Du hast wohl was falsch verstanden. Du hast eine Distanzmatrix gegeben. Auf dieser basierend kannst du auch den Algorithmus anwenden. Effizientere Implementierung nutzen in der Regel aber wenn eher Adjazenzlisten etc.
G
Guest
Gast
???
Also brauche ich doch keine Adjazenzliste???
Also brauche ich doch keine Adjazenzliste???
mic_checker
Top Contributor
Du hast verschiedene Möglichkeiten Graphen darzustellen. Dazu zählen Adjazenzlisten und Adjazenzmatrizen. Der Unterschied besteht v.a. in der Laufzeit/Speicherplatz-Effizienz.
D.h. für dich, du kannst sowohl eine Adjazenzmatrix, als auch eine Liste nehmen.
D.h. für dich, du kannst sowohl eine Adjazenzmatrix, als auch eine Liste nehmen.
Die Distanzmatrix und eine Adjazenzliste sind nur unterschiedliche Darstellungen der gleichen Information (falls man bei der Adjazenzliste auch Entfernungen abfragen kann). Nämlich: "Welche Nachbarknoten hat ein Knoten, und wie weit weg sind die Nachbarn?". Du kannst also entweder das eine oder das andere verwenden. Im Idealfall KÖNNTE man den Dijkstra implementieren, ohne zu wissen, ob das eine oder das andere verwendet wird: Wenn es Methoden gibt, die z.B. zu einem gegebenen Knoten alle Nachbarn liefern, dann können diese Methoden entweder auf die Matrix oder auf die Adjazenzliste zurückgreifen. Ab Dijkstra selbst ändert sich dadurch nichts.
hmmm, das waren jetzt zuviel Informationen.... ;-)
Ok, dann habe ich mein Java-Programm mit einem 2DArray.
Mein Roboter fährt dadrauf, alles gut, Hindernisse sind auch drauf, die werden auch bemerkt und umfahren. Und nun möchte ich den kürzesten weg zwischen einem Startknoten & einem Zielknoten finden, was bedeutet:
Ich brauche den Dijkstra-ALgorithmus.
Bis jetzt alles richtig???
Ok, dann habe ich mein Java-Programm mit einem 2DArray.
Mein Roboter fährt dadrauf, alles gut, Hindernisse sind auch drauf, die werden auch bemerkt und umfahren. Und nun möchte ich den kürzesten weg zwischen einem Startknoten & einem Zielknoten finden, was bedeutet:
Ich brauche den Dijkstra-ALgorithmus.
Bis jetzt alles richtig???
mic_checker
Top Contributor
Naja, streng genommen nicht, es gibt auch andere Algorithmen, z.B. Floyd Algorithmus etc. 
Aber ums nicht komplizierter zu machen: Ja, kannst es so machen.
Aber ums nicht komplizierter zu machen: Ja, kannst es so machen.
mic_checker
Top Contributor
Für eine simple Implementierung genügt die Matrix.
mic_checker
Top Contributor
Es ist prinzipiell egal ob du eine Liste oder eine Matrix holst. Von mir aus mach auch ne Liste ;-)
ok, nur wie programmiere ich es zu meinem Bsp.:
public static final int reihe = 4;
public static final int spalte = 11;
public static final int Quadrant = 20;
public static final int Spaltenlaenge = 250;
public static int Blickrichtung = 1;
public static int AktuelleReihe = 0;
public static int AktuelleSpalte = 0;
public static boolean[][] Flaeche = new boolean[reihe][spalte];
public static void main(String[] args) throws IOException, InterruptedException {
for(int i = 0; i < reihe; i++){
for(int n = 0; n < spalte; n++){
Flaeche[n]= false;
}
}
//Initalisierung des Arrays
public static final int reihe = 4;
public static final int spalte = 11;
public static final int Quadrant = 20;
public static final int Spaltenlaenge = 250;
public static int Blickrichtung = 1;
public static int AktuelleReihe = 0;
public static int AktuelleSpalte = 0;
public static boolean[][] Flaeche = new boolean[reihe][spalte];
public static void main(String[] args) throws IOException, InterruptedException {
for(int i = 0; i < reihe; i++){
for(int n = 0; n < spalte; n++){
Flaeche[n]= false;
}
}
//Initalisierung des Arrays
mic_checker
Top Contributor
du meinst wie du die repräsentation der matrix als liste hinkriegst?
Ja, wie ich den array als liste darstellen kann.
(P.s.:Muss mal kurz weg, bin in ner halben stunde wieder da, aber kanns ruhig weiter antworten, lese es dann gleich)
Ich hab schon versucht das eine liste darzustellen, aber es waren kleine Fehler da, und jetzt habe ich keine ahnung, wie ich weiter machen soll.
Bis gleich
Missy
(P.s.:Muss mal kurz weg, bin in ner halben stunde wieder da, aber kanns ruhig weiter antworten, lese es dann gleich)
Ich hab schon versucht das eine liste darzustellen, aber es waren kleine Fehler da, und jetzt habe ich keine ahnung, wie ich weiter machen soll.
Bis gleich
Missy
mic_checker
Top Contributor
Du weisst aber von der Theorie her wie man aus der Adjazenzmatrix die Liste generiert?
Glaube schon, aber ich weiß nicht, wie ich es zum Array einfügen soll.
Also das habe ich versucht:
public class Admatrix {
int anzahlknoten;
int[] [] arr;
/** Creates a new instance of Admatrix */
public Admatrix(int m) {
anzahlknoten = m;
arr = new int[m][m];
}
public void setEdge(int a, int b){
arr[a] = 1;
// arr[a] = 1;
}
public void printm(){
for(int i = 0; i < anzahlknoten; i++){
for(int z = 0; z < anzahlknoten; z++){
if(arr[z] == 1){
System.out.print("(" + i + ", " + z + "), " );
}
}
}
System.out.println();
}
public static void main(String[] args){
Admatrix ad = new Admatrix(4);
ad.setEdge(0,1);
ad.setEdge(0,2);
ad.setEdge(1,2);
ad.setEdge(1,3);
ad.printm();
Aber es funktioniert nicht.
Also das habe ich versucht:
public class Admatrix {
int anzahlknoten;
int[] [] arr;
/** Creates a new instance of Admatrix */
public Admatrix(int m) {
anzahlknoten = m;
arr = new int[m][m];
}
public void setEdge(int a, int b){
arr[a] = 1;
// arr[a] = 1;
}
public void printm(){
for(int i = 0; i < anzahlknoten; i++){
for(int z = 0; z < anzahlknoten; z++){
if(arr[z] == 1){
System.out.print("(" + i + ", " + z + "), " );
}
}
}
System.out.println();
}
public static void main(String[] args){
Admatrix ad = new Admatrix(4);
ad.setEdge(0,1);
ad.setEdge(0,2);
ad.setEdge(1,2);
ad.setEdge(1,3);
ad.printm();
Aber es funktioniert nicht.
mic_checker
Top Contributor
Sagen wir du hast folgende Matrix gegeben (hoffe die wird halbwegs korrekt formatiert dargestellt):
- 4 - - -
8 - - 7 -
- - - - 5
- 7 - - 10
- - 2 - -
- steht für keine Kante (kannst auch mit unendlich etc. markieren.
Zu lesen:
1 ist mit 2 verbunden und Kosten/Distanz = 4
2 ist mit 1 verbunden und Kosten/Distanz = 8
2 ist mit 4 verbunden und Kosten/Distanz = 7
...
5 ist mit 3 verbunden und Kosten/Distanz = 2
Denke das sollte klar sein.
Eine simple Liste sieht dazu so aus:
1 | -> 2
2 | -> 1 -> 4
3 | -> 5
4 | -> 5 -> 2
5 | -> 3
D.h. zu jedem Knoten speichert man die Menge der Nachfolgeknoten in einer Liste. Auf die einzelnen Listen kannst du über ein Array zugreifen.
Mal dir das ganze mal auf ein Blatt auf, also auch den zugehörigen Graphen und versuch erstmal die Darstellungen nachzuvollziehen.
Wenn du das verstanden hast, sollte es eig. nicht schwer sein eine gegebene Adjazenzmatrix in eine Liste umzuwandeln.
- 4 - - -
8 - - 7 -
- - - - 5
- 7 - - 10
- - 2 - -
- steht für keine Kante (kannst auch mit unendlich etc. markieren.
Zu lesen:
1 ist mit 2 verbunden und Kosten/Distanz = 4
2 ist mit 1 verbunden und Kosten/Distanz = 8
2 ist mit 4 verbunden und Kosten/Distanz = 7
...
5 ist mit 3 verbunden und Kosten/Distanz = 2
Denke das sollte klar sein.
Eine simple Liste sieht dazu so aus:
1 | -> 2
2 | -> 1 -> 4
3 | -> 5
4 | -> 5 -> 2
5 | -> 3
D.h. zu jedem Knoten speichert man die Menge der Nachfolgeknoten in einer Liste. Auf die einzelnen Listen kannst du über ein Array zugreifen.
Mal dir das ganze mal auf ein Blatt auf, also auch den zugehörigen Graphen und versuch erstmal die Darstellungen nachzuvollziehen.
Wenn du das verstanden hast, sollte es eig. nicht schwer sein eine gegebene Adjazenzmatrix in eine Liste umzuwandeln.
Ich denke eine liste ist besser:
Reihe 1, Spalte 1 : (Kante zur Reihe 1 Spalte 2) & (Kante zur Reihe 2 Spalte 1).
usw.
Aber wie gebe ich das ein??? Das ist mein Problem:
Ich weiß wie es ausschauen soll, auch eine Matrix verstehe ich, aber das zu programmieren:
Neue Kante, neuer Knoten, Verbindungen, Gewichtungen, Startknoten, Zielknoten.
Reihe 1, Spalte 1 : (Kante zur Reihe 1 Spalte 2) & (Kante zur Reihe 2 Spalte 1).
usw.
Aber wie gebe ich das ein??? Das ist mein Problem:
Ich weiß wie es ausschauen soll, auch eine Matrix verstehe ich, aber das zu programmieren:
Neue Kante, neuer Knoten, Verbindungen, Gewichtungen, Startknoten, Zielknoten.
mic_checker
Top Contributor
Du willst also nicht die klassische Darstellung, sondern alles in einer einfach verketteten Liste?
mic_checker
Top Contributor
Die Idee hinter Adjazenzlisten ist eig. nicht die, wie du sie geschildert hast. Theoretisch möglich wäre es natürlich auch.
Schau dir einfach mal obige Adjazenzliste an...ansonsten ganz einfach: Implementier es mal und guck ob du dir bei deinen Instanzen um die Performance Gedanken machen musst.
Schau dir einfach mal obige Adjazenzliste an...ansonsten ganz einfach: Implementier es mal und guck ob du dir bei deinen Instanzen um die Performance Gedanken machen musst.
Ich habe doch keine Ahnung wie ich eine Liste programmieren soll, habe dafür keine bsp gesehen, und bis jetzt habe ich programmiert und programmiert, aber es sind immer Fehler vorhanden, da ich das array nicht richtig in der liste anwende, denke ich.
Hast du kein bsp da, für eine array-darstellung als liste?
Hast du kein bsp da, für eine array-darstellung als liste?
mic_checker
Top Contributor
Wieso hast du keine symmetrische Matrix? In die Spalten / Zeilen trägst du doch deine Knoten ein...D.h. du hast bei m Knoten eine m x m Matrix.
Aaahhhh... Hm ???:L Also, vielleicht hab ich jetzt die eigentliche "Ursache" für die Frage verstanden (aber sicher bin ich mir nicht :wink: )
Ok, dann habe ich mein Java-Programm mit einem 2DArray.
Mein Roboter fährt dadrauf, alles gut, Hindernisse sind auch drauf, die werden auch bemerkt und umfahren.
Du hast eine Matrix. Die repäsentiert das Spielfeld - aber nicht die Adjazenzmatrix?! Dein Spielfeld sieht z.B. so aus:
Also, das ist das NICHT-symmetrische 6x4 Felder große Spielfeld. Und darauf soll dein Roboter jetzt z.B. von 's' nach 'z' laufen!?
Ich bin nur nicht sicher, was denn deine
public static boolean[][] Flaeche = new boolean[reihe][spalte];
sein soll - ich gehe davon aus, dass das das Spielfeld ist, und entsprechend "true" oder "false" gesetzt wird, ob das Feld frei ist oder nicht.
Wenn du dieses Spielfeld jetzt als Graphen ansehen willst, dann könntest du z.B. (mit Adjazenzlisten und allem drum und dran) für jedes Feld des Spielfeldes einen Knoten erstellen. Und jedem Knoten sagst du dann, welches seine Nachbarknoten sind (das ist dann die Adjazenzliste)
Sinngemäß (!!! Wirklich nur sinngemäß !!!):
Die Knoten-Klasse
Erstellen des Graphen:
Aber vielleicht hab ich das ja jetzt auch vollkommen falsch verstanden.... :roll:
EDIT: Damit das jetzt nicht falsch ankommt (FALLS ich es richtig verstanden habe) : Du solltest NICHT alle adjazenzen so "per Hand" wie im Beispiel oben hinschreiben, sondern ggf. automatisch aus dem gegebenen Spielfeld generieren!!!
Ok, dann habe ich mein Java-Programm mit einem 2DArray.
Mein Roboter fährt dadrauf, alles gut, Hindernisse sind auch drauf, die werden auch bemerkt und umfahren.
Du hast eine Matrix. Die repäsentiert das Spielfeld - aber nicht die Adjazenzmatrix?! Dein Spielfeld sieht z.B. so aus:
Code:
.s....
.XXX..
.X....
.X..z.Ich bin nur nicht sicher, was denn deine
public static boolean[][] Flaeche = new boolean[reihe][spalte];
sein soll - ich gehe davon aus, dass das das Spielfeld ist, und entsprechend "true" oder "false" gesetzt wird, ob das Feld frei ist oder nicht.
Wenn du dieses Spielfeld jetzt als Graphen ansehen willst, dann könntest du z.B. (mit Adjazenzlisten und allem drum und dran) für jedes Feld des Spielfeldes einen Knoten erstellen. Und jedem Knoten sagst du dann, welches seine Nachbarknoten sind (das ist dann die Adjazenzliste)
Sinngemäß (!!! Wirklich nur sinngemäß !!!):
Die Knoten-Klasse
Code:
class Node
{
int x, y; // Position
ArrayList<Node> neighbors = new ArrayList<Node>(); // Adjazenzliste
public Node(int x, int y) { this.x = x; this.y = y; }
public void addNeighbor(Node other)
{
neighbors.add(other);
}
}Erstellen des Graphen:
Code:
Node nodes[][] = new Node[reihe][spalte];
for (int r = 0; r<reihe; r++)
{
for (int s = 0; r<spalte; s++)
{
if (Fleache[r][s] == true) // Wenn das Feld frei ist
{
nodes[r][s] = new Node(r,s); // Erstelle einen Knoten für das Feld
}
}
}
// Erstelle die Adjazenzen (sinngemäß!!! für Knoten, die nicht null sind)
nodes[0][0].addNeighbor(nodes[0][1]);
nodes[0][0].addNeighbor(nodes[1][1]);
nodes[0][0].addNeighbor(nodes[1][0]);
...Aber vielleicht hab ich das ja jetzt auch vollkommen falsch verstanden.... :roll:
EDIT: Damit das jetzt nicht falsch ankommt (FALLS ich es richtig verstanden habe) : Du solltest NICHT alle adjazenzen so "per Hand" wie im Beispiel oben hinschreiben, sondern ggf. automatisch aus dem gegebenen Spielfeld generieren!!!
Marco13 & mic checker: Seid ihr ein und die selbe Person? ;-)
Falls nicht, was ich nicht glaube:
@ Mic_checker: Ich kann doch mein Feld nicht symmetrisch darstellen, da ich NUR 4 Spalten habe, aber 11 Reihen. Das Feld ist auch WIRKLICH in REAL vorhanden. Dafür habe ich das Array angewendet. Klappt bis dahin auch alles.
@ Marco13:
Langsam scheinst du mich zu verstehen :applaus:
Ja, false & true bekomme ich als Antworten, ob Hindernisse vorhanden sind oder nicht. Spielfeld ist aber 4x11 groß ;-).
Und auch mit der Liste hast du recht. Jetzt verstehst du vielleicht auch, warum ich eine liste brauche, oder?
Danke für das Programm, auch wenns noch net fertig ist, leider ;-).
Wieso kann ich denn nicht alle Knoten einzeln aufschreiben? Ist zwar mühsam und nicht der zweck der programmierung, denke ich, aber leichter für mich, denn bis ich das programm schreibe wirds dauern ;-).
Schönen Gruss
Missy
Falls nicht, was ich nicht glaube:
@ Mic_checker: Ich kann doch mein Feld nicht symmetrisch darstellen, da ich NUR 4 Spalten habe, aber 11 Reihen. Das Feld ist auch WIRKLICH in REAL vorhanden. Dafür habe ich das Array angewendet. Klappt bis dahin auch alles.
@ Marco13:
Langsam scheinst du mich zu verstehen :applaus:
Ja, false & true bekomme ich als Antworten, ob Hindernisse vorhanden sind oder nicht. Spielfeld ist aber 4x11 groß ;-).
Und auch mit der Liste hast du recht. Jetzt verstehst du vielleicht auch, warum ich eine liste brauche, oder?
Danke für das Programm, auch wenns noch net fertig ist, leider ;-).
Wieso kann ich denn nicht alle Knoten einzeln aufschreiben? Ist zwar mühsam und nicht der zweck der programmierung, denke ich, aber leichter für mich, denn bis ich das programm schreibe wirds dauern ;-).
Schönen Gruss
Missy
Also, das verbitte ich mir :noe: :wink:
Wieso kann ich denn nicht alle Knoten einzeln aufschreiben? Ist zwar mühsam und nicht der zweck der programmierung, denke ich, aber leichter für mich, denn bis ich das programm schreibe wirds dauern
Viel Programmierarbeit entsteht dadurch, dass man sich Arbeit sparen will. Wenn später die Anforderung kommt: "Beim Testieren lest ihr das Spielfeld bitteschön aus einer Datei aus", dann bist du gebeischlaft, weil dann erstmal garnichts mehr funktioniert, und du mühsam alle Verbindungen von Hand coden musst...
Wieso kann ich denn nicht alle Knoten einzeln aufschreiben? Ist zwar mühsam und nicht der zweck der programmierung, denke ich, aber leichter für mich, denn bis ich das programm schreibe wirds dauern
Viel Programmierarbeit entsteht dadurch, dass man sich Arbeit sparen will. Wenn später die Anforderung kommt: "Beim Testieren lest ihr das Spielfeld bitteschön aus einer Datei aus", dann bist du gebeischlaft, weil dann erstmal garnichts mehr funktioniert, und du mühsam alle Verbindungen von Hand coden musst...
G
Guest
Gast
Wenn ich z.b. folgendes straßennetz habe
münchen ------- nürnberg------berlin
.
.
.
salzburg-------- wien
(punkte sagen dass eine verbindung besteht - auch zwischen münchen und salzburg)
wie schreib ich das als adjazenzmatrix? die entferung spielt in diesem fall keine rolle!
vielen dank für eure antworten!
münchen ------- nürnberg------berlin
.
.
.
salzburg-------- wien
(punkte sagen dass eine verbindung besteht - auch zwischen münchen und salzburg)
wie schreib ich das als adjazenzmatrix? die entferung spielt in diesem fall keine rolle!
vielen dank für eure antworten!
Du hast 5 Orte.
Also brauchst du eine 5x5 Matrix
münchen(1) ------- nürnberg(2)------berlin(3)
.
.
.
salzburg(4)-------- wien(5)
0 : keine Verbindung
1: Verbindung
012345
101010
210100
301000
410001
500010
:?: :wink:
Also brauchst du eine 5x5 Matrix
münchen(1) ------- nürnberg(2)------berlin(3)
.
.
.
salzburg(4)-------- wien(5)
aus:http://www.tilman.de/uni/ws03/alp/adjazenz.php
0 : keine Verbindung
1: Verbindung
012345
101010
210100
301000
410001
500010
:?: :wink:
G
Guest
Gast
fast....
nur dass ich keine MATRIX sondern eine LISTE brauch!
wie würde der Code für das als adjazenzLISTE in java aussehen?
nur dass ich keine MATRIX sondern eine LISTE brauch!
wie würde der Code für das als adjazenzLISTE in java aussehen?
Die Listesieht dann so aus:
1-2-4
2-1-3
3-2
4-1-5
5-4
Allgorithmus:
DAs j ist deine Element-Nummer
Du mußt dir noch klarmachen, wie du deine "Nachbar-Elemente" erkennst. :wink:
Also:
1-2-4
2-1-3
3-2
4-1-5
5-4
Allgorithmus:
Code:
int AnzKnoten = 5;
ArrayList<Integer> liste[] = new ArrayList[AnzKnoten];
for ( int i = 0; i<5 ; i++ ){
liste[i] = new ArrayList<Integer>();
// füge alle Nachbarn in die Liste ein
for (int j = 0; j<5; j++){
if (Element[j].istNachbar(Element[i])) liste[i].add(j);
}
}Du mußt dir noch klarmachen, wie du deine "Nachbar-Elemente" erkennst. :wink:
Also:
Code:
(Element[j].istNachbar(Element[i])- Status
Ähnliche Java Themen
| Titel | Forum | Antworten | Datum | |
|---|---|---|---|---|
| N | Adjazenzliste | Java Basics - Anfänger-Themen | 13 | |
| H | Adjazenzliste - Datenstruktur aber wie? | Java Basics - Anfänger-Themen | 7 | |
| R | Adjazenzliste leer | Java Basics - Anfänger-Themen | 3 |
Ähnliche Java Themen
-
-
Adjazenzliste - Datenstruktur aber wie?
- Gestartet von huckleberry
- Antworten: 7
-
Aktuelle Jobs
-
Wafios Softwareentwickler Cloud (JAVA/Spring) m/w/d - Reutlingen- Gestartet von Java_Jobs
- Antworten: 0
-
Inek Senior Java Softwareentwickler (m/w/d) - Siegburg
- Gestartet von Java_Jobs
- Antworten: 0
-
Atos Senior Java Architekt (m/w/d) - Fürth
- Gestartet von Java_Jobs
- Antworten: 0
-
-
FCA Bank Java-Entwickler (m/w/d) (Heilbronn)
- Gestartet von Java_Jobs
- Antworten: 0
Neue Themen
-
Baumstruktur (mat-tree) nicht sichtbar
- Gestartet von Lisun4ik
- Antworten: 0
-
Github Projekt starten/anbinden in eclipse
- Gestartet von helloworld26
- Antworten: 11
-
-
Liste sortieren ohne Array und ohne vorgegebene Sortierung- Gestartet von Fynn29
- Antworten: 24
-