Adjazenzliste

regillus

Grünschnabel
Hallo,
habe da eine "kleine" Frage
Wie kann ich eine "adjazenzliste" in Java programmieren?
Denn ich muss dort einen Graph abspeichern.
Danke
 

Thomas Darimont

Erfahrenes Mitglied
Hallo!

Einen Graphen kann man beispielsweise als eine Liste / Array (A) von verketten Listen (B) darstellen. Zu jeder Position i (Knoten des Graphen) aus Liste A gibt es dann eine verkette Liste B die alle von A(i) aus erreichbaren Knoten enthält (ohne A(i) selbst).

Beispiel:
Die Ajazenzliste dazu sollte so ausschauen:
Code:
  A(0)=5,3
  A(1)=5,3,2
  A(2)=4,1
  A(3)=1,6,4,0
  A(4)=6,2,3
  A(5)=1,0
  A(6)=4,3

Gruß Tom
 

Anhänge

  • graphexample.jpg
    graphexample.jpg
    13,9 KB · Aufrufe: 149
M

Missy79

Hallo,
ich habe ein Problem:
Ich habe ein Array und den muss ich in einen Graphen umwandeln, also in eine Adjazenzliste/matrix, weiss nicht, welches besser für mein Beispiel ist.
Danach muss ich den Dijkstra Algorithmus darauf anwenden, weil ich den kürzesten Weg finden muss.
Hast du ne Ahnung, wie ich das programmieren kann?
Auf java?
Schönen Gruss
Missy
 
M

Missy79

Hi, danke fürs Antworten,
also mein Array schaut so aus:
Code:
	public static void main(String[] args) throws IOException, InterruptedException {
		for(int i = 0; i < reihe; i++){
			for(int n = 0; n < spalte; n++){
				Flaeche[i][n]= false;
			}
		}
		//Initalisierung des Arrays

Einige Sätze dazu:
Ich programmiere es für einen Lego Mindstorms Roboter, und der muss Hindernisse erkennen.
Es gibt 4 Reihen und 11 Spalten:
Code:
       public static final int reihe = 4;
        public static final int spalte = 11;

Als Ausgabe im Eingabeaufforderungsfenster bekomme ich dann auch alle "Felder" mit einer Null für kein Hinderniss und einer 1 wenn ein Hinderniss auf der Position(Reihe/Spalte) vorhanden war.
Die Ausgabe schaut dann so aus:
reihe = 1
spalte = 2
0
usw. für die anderen Felder im Array.
Und für dieses Array brauche ich eine Adjazenzliste, damit ich den Dijkstra Algorithmus darauf anwenden kann, denn mein Roboter soll den kürzesten Weg zum Hindernis/Verletzen finden, bzw. zu einer bestimmten Position im Array/Knoten.

Schönen Gruss
Missy
 

kle-ben

Erfahrenes Mitglied
Hi
nehmen wir mal an deine Matrix sieht so aus wie im angehängten Bild.
Hindernisse sind schwarz dargestellt.
Dann sollte dein Array so befüllt sein:
Code:
bool matrix[][] = {
{1,0,0},
{0,0,1},
{0,1,1}
}
Jede Zelle mit 0 in deinem Array stellt dabei einen Knoten dar.
Du musst jetzt also für jeden Knoten kontrollieren welche seiner
Nachbarfelder keine hindernisse sind.
Wenn du das gemacht hast sollte dein Adjazenslist so aussehn:
[0] = //kein knoten 0 vorhanden
[1] = {}
[2] = {3,5}
[3] = {2}
[4] = {5,7}
[5] = {4,2}
[6] = {}
[7] = {4}
[8] = {}
[9] = {}
Dein Array solltest du aber nur so groß halten wie du es brauchst.
ich hab es der Einfach heit halber mal komplett dargestellt.


Benny
 

Anhänge

  • matrix.jpg
    matrix.jpg
    2,3 KB · Aufrufe: 5.399
M

Missy79

Hi,
Und wie lautet der Programmcode für eine Adjazentliste?
Schönen Gruss
Missy
 

Proko

Mitglied
hier ist ein code den ich vor ein paar jahren in c geschrieben habe

eine adjazenzliste als matrix implementiert (liste wäre für meine aufgabe zu umfangreich geworden) => auch bei mindstorms solltest du bei der statischen matrix bleiben, listen die dynamisch erweitern werden sind da nicht empfehlenswert!

die struktur sieht in java genau so aus
die relevanten methoden für dich sind dann

addEdge(): fügt knoten hinzu
removeEdge(): löscht knoten
shortestPath(): implementierung des algorithmus von dijkstra zur ermittlung des kürzesten weges

in java legst dir also eine matrix m x n vom typ bool an, der rest ist ziemlich gleich wie in C

das was für java nicht benötigt wird, habe ich hier rausgegeben, damit es nicht verwirrend wird, z.Bsp. .toString() der Matrix, Speicherfreigabe, Tiefensuche
Code:
/* DG_ads_M.c:                        TZ, 11-11-2004
   ----------
   Abstract data structure for directed graphs with
   adjazenzmatrix.
====================================================*/

#include "WDG_ADS_M.h"
#define MAX_VERT 100 /* max number of vertices */

#include <stdio.h>

typedef enum bool {false, true} bool;
typedef bool AdjMatrix [MAX_VERT][MAX_VERT];
int n = 0; /* <= MAX_VERTICES, current number of vertices */
AdjMatrix m; /* matrix */

void AddEdge (int i, int j) {
  if ( i != j )
    if ((i-1 >= 0) && (j-1 >= 0) && (i-1 < n) && (j-1 < n))
      m[i-1][j-1] = true; 
} /* AddEdge */

void RemoveEdge (int i, int j) {
  if ( i != j )
    if ((i-1 >= 0) && (j-1 >= 0) && (i-1 < n) && (j-1 < n))
      m[i-1][j-1] = false;
} /* RemoveEdge */

int ShortestPath (int vScr, int vDest) {
  AdjMatrix temp;
  int i, j, k;
  /* init temp with m */
  for ( i = 0; i < n; i++ )  {
    for ( j = 0; j < n; j++) 
      temp[i][j]=m[i][j];    
  } /* for */  
  for ( i = 0; i < n; i++ )
    for ( j = 0; j < n; j++ )
      if (temp[j][i])
        for ( k = 0; k < n; k++ )
          if ( temp[k][j] > 0 )
            if ( (temp[k][i]==0) || (temp[j][i]+temp[k][j] < temp[k][i]) )
              temp[k][i] = temp[j][i] + temp[k][j];            
  return temp[vScr-1][vDest-1];
} /* ShortestPath */

bei ShortestPath:
gestartet wird mit shortestPath(0,0)
und anstatt >0 schreibst dann in java ==true und ==0 wird in java ==false
in c is 0 selbe wie false, 1 selbe wie true
will jetz net auf die schnelle da was ändern sonst is nachher falsch ;)

have fun
 
Zuletzt bearbeitet:
H

hugolore

Hallo,
ich muß einen Graphen in Java implementieren.
Und zwar als Adjezenzliste unter Verwendung von ArrayList.
Wie macht man so etwas?