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

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 :

1 2 3 4 5 6 7

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

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

Hallo,

dann zeig doch mal her, wie dein Array ausschaut...

Gruß Tom

Hi, danke fürs Antworten,
also mein Array schaut so aus:

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

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 :

1 2 3 4 5

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

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

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

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

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

schau dir mal die klasse AdjacencyList an, dort wird das ganze mit hilfe von einer ArrayList gelöst

lg

hi
also ich wollte fragen wie man in java diese adjazenzlisten (graphen) zeichnen kann, hab mit google sehr viel gesucht aber leider nichts konkretes gefunden

also nehmen wir zum beispiel die liste von thomas
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

was brauche ich nun um einen graphen daraus zu zeichnen