# Adjazenzliste



## Missy (7. Mai 2007)

Hallo, 
ich möchte eine Adjazenzliste zu meinem 2d Array erstellen,
kann mir da jemand ein bsp, bzw. ein programmcode schicken???
Schönen Gruss
Missy


----------



## JPKI (7. Mai 2007)

*Was* bitteschön ist eine Adjazenzliste??? Noch nie gehört ???:L ...


----------



## mic_checker (7. Mai 2007)

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.


----------



## Missy (7. Mai 2007)

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


----------



## mic_checker (7. Mai 2007)

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.


----------



## Guest (7. Mai 2007)

???
Also brauche ich doch keine Adjazenzliste???


----------



## mic_checker (7. Mai 2007)

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.


----------



## Marco13 (7. Mai 2007)

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.


----------



## Missy (7. Mai 2007)

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???


----------



## mic_checker (7. Mai 2007)

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.


----------



## Missy (7. Mai 2007)

Nicht zu vergessen den A -Algorithmus, bzw. den Bellmann Ford-Alg. ;-)
Also brauche ich doch keine Adjazenzliste???
Ich nehme an DOCH.


----------



## mic_checker (7. Mai 2007)

Für eine simple Implementierung genügt die Matrix.


----------



## Missy (7. Mai 2007)

Ich habe aber gelesen, dass für mein Bsp die Liste besser passt???


----------



## mic_checker (7. Mai 2007)

Es ist prinzipiell egal ob du eine Liste oder eine Matrix holst. Von mir aus mach auch ne Liste ;-)


----------



## Missy (7. Mai 2007)

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_


----------



## mic_checker (7. Mai 2007)

du meinst wie du die repräsentation der matrix als liste hinkriegst?


----------



## Missy (7. Mai 2007)

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


----------



## mic_checker (7. Mai 2007)

Du weisst aber von der Theorie her wie man aus der Adjazenzmatrix die Liste generiert?


----------



## Missy (7. Mai 2007)

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.*


----------



## Missy (7. Mai 2007)

Sorry, nein, habe die Frage falsch verstanden:
Ich weiß nicht, wie man eine Matrix, geschweige Liste erstellt. Habe keinen Schimmer. Deshalb meine Fragen hier ;-).


----------



## mic_checker (7. Mai 2007)

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.


----------



## Missy (7. Mai 2007)

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.


----------



## mic_checker (7. Mai 2007)

Du willst also nicht die klassische Darstellung, sondern alles in einer einfach verketteten Liste?


----------



## Missy (7. Mai 2007)

Bis jetzt bin ich der Meinung, ja. 
Aber:
Meinst du, dass für mein Beispiel, wo ich 44 Felder habe, es ok ist, eine Matrix zu nehmen???
Ich guck mal, wo ich gelesen habe, dass für mein Bsp. mit start & Zielknoten und Verbindungen zwischen Knoten eine liste besser ist.


----------



## mic_checker (7. Mai 2007)

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.


----------



## Missy (7. Mai 2007)

Achja, der Grund, warum ich ne Liste haben möchte:
Habe gelesen, dass Matrizen syymetrisch ausschauen, und meine ist definitiv nicht symmetrisch:

  1   2    3    4 (Spalten) 

  1.   1.    1.    1. Reihe
  2.   2.    2.    2. Reihe
  3      etc. ................
  4
  5
  6
  7
  8
  9
10
11


----------



## Missy (7. Mai 2007)

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?


----------



## mic_checker (7. Mai 2007)

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.


----------



## Marco13 (7. Mai 2007)

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:

```
.s....
.XXX..
.X....
.X..z.
```
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

```
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:


```
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!!!


----------



## Missy (8. Mai 2007)

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


----------



## Marco13 (8. Mai 2007)

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...


----------



## Missy (8. Mai 2007)

:!:  Ja hast ja recht!!!
Ich dachte, dass ich das noch umgeben kann, und außerdem tippe ich gerne ;-).


----------



## Guest (21. Aug 2007)

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!


----------



## jPat (21. Aug 2007)

Du hast 5 Orte.
Also brauchst du eine 5x5 Matrix
münchen(1) ------- nürnberg(2)------berlin(3)
.
.
.
salzburg(4)-------- wien(5) 



> Insbesondere bei sehr vielen Kanten ist eine Speicherung der Verbindung als nxn-Matrix sinnvoll, wobei n = Knotenanzahl |V|. Eine derartige Matrix wird als Adjazenzmatrix bezeichnet.
> Gibt es eine Kante von Knoten a zu Knoten b, wird in der Matrix in der a-ten Zeile an der b-ten Stelle ein True bzw. eine 1 eingetragen.


 aus:http://www.tilman.de/uni/ws03/alp/adjazenz.php


0 : keine Verbindung
1: Verbindung

012345
101010
210100
301000
410001
500010

 :?:  :wink:


----------



## Guest (21. Aug 2007)

fast....
nur dass ich keine MATRIX sondern eine LISTE brauch!

wie würde der Code für das als adjazenzLISTE in java aussehen?


----------



## jPat (21. Aug 2007)

Die Listesieht dann so aus:
1-2-4
2-1-3
3-2
4-1-5
5-4

Allgorithmus:

```
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);
			}	
		}
```
DAs j ist deine Element-Nummer
Du mußt dir noch klarmachen, wie du deine "Nachbar-Elemente" erkennst. :wink: 
Also:

```
(Element[j].istNachbar(Element[i])
```


----------

