Frage zu Graph Tiefensuche

Luk10

Luk10

Top Contributor
Grüße,

Ich habe einen Graphen mit, wie üblich, einer Knotenliste als
Code:
Knoten[]
.
Nun habe ich folgende Aufgabe / Problem:

Ich soll eine
Code:
ArrayList<Knoten>
ausgeben, welche die Knoten eines möglichen Weges (Also nicht der kürzeste) von
Code:
start_index
bis
Code:
ziel_index
in richtiger Reihenfolge enthält.

Ich würde dazu gerne die Tiefensuche verwenden, da ich die verstanden habe und auch umsetzten kann. Nur wie mache ich das am besten mit den Knoten speichern, die ich durchlaufen habe?

Wie kann ich die Knoten speichern, wenn die Methode rekursiv aufgerufen wird? Mit einer Instanzvariablen? Das finde ich aber nicht besonders "schön" da ich ja eigentlich nur per Methode die Liste zurückgeben will.

Kann mir jemand einen Denkanstoß / Tipps geben wie ich sowas lösen kann?

Hier meine Tiefensuche:

Java:
public void depthFirstSearch(int start_index, int end_index) {
		
		if (start_index != end_index) {
			
			for(int i = 0; i < nodelist.length; i++) {
				if (adjacencyMatrix[start_index][i] != null && !nodelist[i].isVisited()) {
					//Do something
					depthFirstSearch(i, end_index);
				}
			}
		}
	}

P.S. Falls jemand "unschöne" englische Bezeichnungen auffallen, bitte bescheid geben :oops:

Danke,
-Luk-
 
S

SlaterB

Gast
die einzigen beiden Alternativen zu einem Instanzattribut sind offensichtlich ein statisches Attribut oder ein Methodenparameter, der rekursiv übergeben wird,

Instanzattribut ist übrigens gar nicht so schlimm, bei einer derart komplizierten Aufgabe mit vielleicht hunderten bis tausenden Aufrufen darf gerne das ganze Objekt nur dem einzigen Zweck einer einzelnen Suche dienen,

da ist z.B. die Objekterzeugung überhaupt kein nennenswerter Aufwand,
vielleicht die Übertragung/ doppelte Datenhaltung der adjacencyMatrix/ nodelist usw. ein Hinderungsgrund

bedenke auch immer dass du mehrere Methoden nutzen kannst:

Java:
public Result search() {
   init parameter
   searchIntern(parameter);
   return result
}

private void searchIntern(parameter) {
  ..
}
 
Luk10

Luk10

Top Contributor
Okay, danke schonmal!

Was meinst du mit
vielleicht die Übertragung/ doppelte Datenhaltung der adjacencyMatrix/ nodelist usw. ein Hinderungsgrund
?

Ich denke ich werde dann doch die meiner Meinung nach einfachsten weg über eine Instanzvariable nehmen ... wenn das also doch in Ordnung ist ;)

-Luk10-
 
S

SlaterB

Gast
ich meine: wenn ein spezielles Objekt/ Klasse für die Suche, wie von mir genannt,
dann müssen dorthin die Netz-Daten, die bisher ja irgendwo vorhanden sind, übertragen werden,
damit auch auch als Instanzattribute verfügbar
 
Luk10

Luk10

Top Contributor
Achso. Nun gut ich denke ich nehme der Einfachheit halber, gleich die Klasse Graph, in der sich auch die Tiefensuche befindet.

-Luk10-
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
Zrebna Frage zum "Referenzen-konzept" in Java Java Basics - Anfänger-Themen 7
JD_1998 Array-Position aus einer Methode in einer anderen ausgeben (Kurze Frage) Java Basics - Anfänger-Themen 2
marcooooo Frage zu bestimmten Beispiel Java Basics - Anfänger-Themen 31
NeoLexx equals()-Methode Verständnis Frage anhand Code Beispiel Java Basics - Anfänger-Themen 22
N Input/Output Eine Frage über system.out.println. Java Basics - Anfänger-Themen 10
B Erste Schritte Learning Coding (!) Frage an erfahrene Programmierer. Java Basics - Anfänger-Themen 23
M konzeptuelle Frage: In welcher Klasse definiert man am Besten Methoden, die die Kommunikation mit dem User regeln? Java Basics - Anfänger-Themen 8
B Frage zum Code verständnis im Resultat Java Basics - Anfänger-Themen 10
C Exception-Frage Java Basics - Anfänger-Themen 3
J Eine Frage zur Schreibweise == ? : Java Basics - Anfänger-Themen 3
S Frage des Designs Java Basics - Anfänger-Themen 1
JavaTalksToMe Extends/Implements Frage Java Basics - Anfänger-Themen 3
pkm Frage zu Servletfunktion Java Basics - Anfänger-Themen 0
B Frage zur Währungsumrechnung Java Basics - Anfänger-Themen 3
S Allgemeine Frage über Generics und Vererbungen Java Basics - Anfänger-Themen 5
Kirby_Sike Frage zur Verwendung von Interfaces Java Basics - Anfänger-Themen 6
D Frage zu Strings einer Exception Java Basics - Anfänger-Themen 4
L Wie frage ich ab, ob in einem Array, Werte doppelt vorkommen? Java Basics - Anfänger-Themen 4
D Frage zur IDE IntelliJ IDEA Java Basics - Anfänger-Themen 6
H Frage zum 2d Array Java Basics - Anfänger-Themen 1
N Frage zum Newton-Fraktal Java Basics - Anfänger-Themen 1
H Frage zu interfaces Java Basics - Anfänger-Themen 1
J Frage dazu Variablen klassenübergreifend zu verändern Java Basics - Anfänger-Themen 22
I Frage zu SkipList Java Basics - Anfänger-Themen 4
G Frage zu JScrollPane Java Basics - Anfänger-Themen 12
Kirby_Sike Allgemeine Frage Java Basics - Anfänger-Themen 3
W Frage zu anonymen Klassen Java Basics - Anfänger-Themen 4
J Kleine Frage zu OOP Java Basics - Anfänger-Themen 371
S Frage Klasse und Objekte Java Basics - Anfänger-Themen 2
F Frage zu Iteratoren Java Basics - Anfänger-Themen 2
C Erste Schritte Frage zur ArrayList Java Basics - Anfänger-Themen 15
J Frage zur Vererbung Java Basics - Anfänger-Themen 1
H Frage zur ermittlung eines doppelte Paars aus Sotieralgorithmus Java Basics - Anfänger-Themen 4
H Frage zum Array Java Basics - Anfänger-Themen 17
G Schach -Frage 2- Maussteuerung Java Basics - Anfänger-Themen 7
G Schach in Java - Allgemeine Frage zur Architektur Java Basics - Anfänger-Themen 7
B Fachliche Frage bei Rechnungen Java Basics - Anfänger-Themen 16
B Frage zu: String... strings -> Ungleiche Anzahl an Parameter? Java Basics - Anfänger-Themen 4
B Frage zu Datenbank Design - Rechnungen, Angebote... und deren Positionen Java Basics - Anfänger-Themen 4
H Frage zu Parameter einer Methode Java Basics - Anfänger-Themen 2
H Einfache Frage zur Punktnotation objektname.methode(wert) Java Basics - Anfänger-Themen 2
H Frage zu Parameter einer Methode Java Basics - Anfänger-Themen 3
H Frage zur if-Bedingung bzw switch case Java Basics - Anfänger-Themen 6
H Frage um Eingbeaufforderung zu realisieren Java Basics - Anfänger-Themen 4
H Frage zu Methoden/Funktionen Java Basics - Anfänger-Themen 3
X Frage zur einer ArrayList in einer ArrayList Java Basics - Anfänger-Themen 5
S Frage zu Scanner Java Basics - Anfänger-Themen 3
M Rationale Zahl erkennen - Kurze Frage zum Restwert nach Division Java Basics - Anfänger-Themen 3
D Komplizierte Frage zum Writer Java Basics - Anfänger-Themen 4
I Frage zu Generics und Wildcards Java Basics - Anfänger-Themen 2
G Frage an die Experten Java Basics - Anfänger-Themen 39
H Frage zu fehler Java Basics - Anfänger-Themen 24
F Konstruktor richtig implementiert? Frage zu Benutzereingaben... Java Basics - Anfänger-Themen 9
B Frage zu Arrays Java Basics - Anfänger-Themen 3
O Bedingter Operator eine Frage! Java Basics - Anfänger-Themen 10
B Threads Thread sleep() Method einfache Frage Java Basics - Anfänger-Themen 8
W Stream Array List - Frage Java Basics - Anfänger-Themen 5
B Verständnis Frage zu der Aufgabe Java Basics - Anfänger-Themen 30
Koookie Kleines Frage - Antwort Programm (Anfänger) Java Basics - Anfänger-Themen 5
O Ganz einfache Frage - Array Java Basics - Anfänger-Themen 5
F Erste Schritte Frage zu simplem Taschenrechner(switch) Java Basics - Anfänger-Themen 16
D Frage zu Exceptions Java Basics - Anfänger-Themen 8
H Frage um den Code bildlich darzustellen Java Basics - Anfänger-Themen 2
D regex Aufbau Frage Java Basics - Anfänger-Themen 4
J Frage zu Pfaden Java Basics - Anfänger-Themen 1
J Frage zur Darstellung Java Basics - Anfänger-Themen 2
D Wie frage ich ab ob die Linke maus Taste gedrückt wurde? Java Basics - Anfänger-Themen 3
J Float Frage Java Basics - Anfänger-Themen 1
H Frage zu Übungsaufgabe, Array Java Basics - Anfänger-Themen 7
ralfb1105 Frage zu Thread Synchronisation mit wait() und notify() Java Basics - Anfänger-Themen 3
D Doofe Frage... Java Basics - Anfänger-Themen 2
M Frage, wie dieser Code funktioniert, bzw. weshab er bei mir nicht funktioniert Java Basics - Anfänger-Themen 4
L Frage zu LibGDX Java Basics - Anfänger-Themen 2
O boolean Array Frage! Java Basics - Anfänger-Themen 4
A Frage zur Aufgabe Uhrzeit einstellen mit Objekten Java Basics - Anfänger-Themen 18
S Frage zu Rekursion... Java Basics - Anfänger-Themen 15
S Noch eine Frage zur Rekursion... Java Basics - Anfänger-Themen 11
S Frage zu einer Rekursion Java Basics - Anfänger-Themen 15
S Sudoku Checker Frage Java Basics - Anfänger-Themen 1
pkm Frage wegen möglichem grouping-hack Java Basics - Anfänger-Themen 22
S Erste Schritte Berechnung des Paketportos - Problem/Frage Java Basics - Anfänger-Themen 52
K Operatoren Frage zu Vergleichsoperatoren Java Basics - Anfänger-Themen 3
R Input/Output Frage zu System.out.println Java Basics - Anfänger-Themen 5
J Frage zu: public static void main (String[]args) Java Basics - Anfänger-Themen 1
S Kleine Frage zu Threads Java Basics - Anfänger-Themen 3
N Frage zu this, super und return Java Basics - Anfänger-Themen 13
N Frage zu Streams Java Basics - Anfänger-Themen 3
L Frage zu IntStream (Java 8) Java Basics - Anfänger-Themen 6
N Frage zum dynamischen Polymorphismus Java Basics - Anfänger-Themen 1
J Einfache Frage zu "null" Java Basics - Anfänger-Themen 2
T Erste Schritte Frage zur Initialisierung eines Mehrdimensionalen Arrays Java Basics - Anfänger-Themen 3
D Frage Threads Java Basics - Anfänger-Themen 6
D Frage zu Kreisdiagramm Java Basics - Anfänger-Themen 2
L Threads Frage zu ReentrantLock Java Basics - Anfänger-Themen 3
D Frage Boyer-Moore Algorithmus Java Basics - Anfänger-Themen 7
L Threads Frage zu ThreadPool Java Basics - Anfänger-Themen 2
E Frage zum Programm Java Basics - Anfänger-Themen 2
JavaTalksToMe Erste Schritte Println-Frage (Verständnisfrage) Java Basics - Anfänger-Themen 1
JavaTalksToMe Kapselung Setter Frage Java Basics - Anfänger-Themen 15
L Kurze Frage... Java Basics - Anfänger-Themen 2

Ähnliche Java Themen

Anzeige

Neue Themen


Oben