Frage zur Tiefensuche

[Luk10]

Grüße,

Ich habe einen Graphen und brauche eine Liste der Kanten die sich direkt zwischen knotenListe[start_index] und knotenListe[end_index] befinden. Dabei ist nicht wichtig ob es der kürzeste Weg ist, sondern nur, dass es ein direkter Weg ohne "Sackgassen" ist. Die Reihenfolge ist auch wichtig.

Mein Ansatz mit der Tiefensuche:

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()) {
					
					wantedNodes.add(nodelist[i]);
					wantedEdges.add(adjacencyMatrix[start_index][i]);
					nodelist[i].setVisited(true);
					
					depthFirstSearch(i, end_index);
					
				}
			}
		}
	}

Hierbei sollten alle Knoten in wantedNodes und alle Kanten ind wantedEdeges gespeichert. Leider funktioniert dass so nicht, da auch die Sackgassen mit in die Listen aufgenommen werden.

Kann mir jemand helfen das Problem zu lösen?

Danke,
-Luk10-

 

[XHelp]

Deine Methode sollte aber auch irgendein Feedback geben (Rückgabewert), damit du weißt wann es eine Sackgasse war und wann nicht. Außerdem solltest du auch auf die möglichen Zyklen im Graphen achten.

 

[Luk10]

Hm ... damit kann ich nicht so viel anfangen. Zyklen hat mein Graph keine und mit der Instanzvariablen "visited" werden Endlosschleifen eh abgefangen.

Kannst du das vielleicht ein bisschen konrekter schreiben? Kann mir darunter schon etwas vorstellen, aber nicht wie ich das umsetzten könnte.

Danke,
-Luk10-

 

[XHelp]

boolean suchePfad(int aktuellerKnoten, int gesuchterKnoten) {
  if (aktuellerKnoten==gesuchterKnoten) {
    return true;
  } else {
    setzeBuschtStatus(aktuellerKnoten);
    if (keineKantenMehrZumUntersuchenVorhanden()) {
      return false;
    } else {
      for (int naechsterKnoten: alleZuUntersuchendeKnoten) {
        if (sechePfad(naechsterKnoten, gesuchterKnoten)) {
          markiere(aktuellerKnoten);
        }
      }
    }
  }
}

 

[Luk10]

Hm, damit kann ich überhaupt nichts anfangen. Ich kann keine Überprüfung auf Kanten erkennen, und wie ich damit eine Liste von Kanten bzw Knoten bekommen, wie ich im 1. Post erklärt habe ist mir nicht klar ... Vielleicht bin ich auch einfach nur zu blöd den Trick zu erkennen, aber ausser dem Rückgabewert, ob der Knoten gefunden wurde, sehe ich da keine Lösung für mein Problem.

Danke,
-Luk10-

 

[XHelp]

Probier es doch einfach aus. Müsste aber so ungefähr funktionieren. Den Pseudocode an dein Code anzupassen sind ja nur ein paar Minuten Arbeit.

 

[Luk10]

Was macht:

keineKantenMehrZumUntersuchenVorhanden()

Ich habe die Kanten in keiner Liste gespeichert. Was soll das machen?

-Frage immernoch offen-

Danke,
-Luk10-

 

[XHelp]

Die prüft, ob es noch Katen gibt, die man noch nicht besucht hat.

 

[Luk10]

Man besucht keine Kanten sondern Knoten ... Aber das meinst du wahrscheinlich.

Nun gut ich werde das mal testen, obwohl mir der Ablauf des Algorithmus überhaupt nicht klat ist.

 

[Luk10]

Gut:
Ich hab das jetzt so auf meine Situation angepasst:

	public boolean depthFirstSearch(int start_index, int end_index) {
		
		if (start_index == end_index) {
			return true;
		}
		else {
			nodelist[start_index].setVisited(true);
			
			boolean nodesleft = false;
			for (Node n : nodelist) {
				if (!n.isVisited()) {
					nodesleft = true;
				}
			}
			if (!nodesleft) {
				return false;
			}
			else {
				for (int i = 0; i < nodelist.length; i++) {
					if (depthFirstSearch(i, end_index)) {
						nodelist[i].setNextNode(nodelist[start_index]);
					}
				}
			}
		}
	}

1. Lässt sich nicht kompilieren, da nicht in allen Fällen ein wert zurückgegeben wird.

 

[XHelp]

Stell mal ein KSKB rein

 

[Luk10]

public class Graph {

	
	private Knoten[] knotenliste;
	private Kante[][] adjazenzMatrix;
	
	
	public Graph() {
		
		knotenliste = new Knoten[6];
		adjazenzMatrix = new Kante[6][6];
		
		baueGraph();
		
	}
	
	
	private void baueGraph() {
		
		knotenliste[0] = new Knoten();
		knotenliste[1] = new Knoten();
		knotenliste[2] = new Knoten();
		knotenliste[3] = new Knoten();
		knotenliste[4] = new Knoten();
		knotenliste[5] = new Knoten();
		
		adjazenzMatrix[0][1] = new Kante();
		adjazenzMatrix[1][0] = new Kante();
		
		adjazenzMatrix[1][2] = new Kante();
		adjazenzMatrix[2][1] = new Kante();
		
		adjazenzMatrix[2][3] = new Kante();
		adjazenzMatrix[3][2] = new Kante();
		
		adjazenzMatrix[3][4] = new Kante();
		adjazenzMatrix[4][3] = new Kante();
		
		//Verzweigung
		adjazenzMatrix[2][5] = new Kante();
		adjazenzMatrix[5][2] = new Kante();
		
	}
	
}

Graph sieht ca so aus:

0 - 1 - 2 - 3 - 4
        |          
        5

public class Knoten {

	
	private boolean besucht;
	private int liegtAufPfad; //int: Reihenfolge der Knoten
	
	
	public Knoten() {
		
		setBesucht(false);
		setLiegtAufPfad(-1);
		
	}
	//Getter und Setter


	public void setLiegtAufPfad(int liegtAufPfad) {
		this.liegtAufPfad = liegtAufPfad;
	}


	public int getLiegtAufPfad() {
		return liegtAufPfad;
	}


	public void setBesucht(boolean besucht) {
		this.besucht = besucht;
	}


	public boolean isBesucht() {
		return besucht;
	}

public class Kante {
	
	
	public Kante() {
		
	}

}

Jetzt brauche ich eine Methode, die mir einen Pfad zwischen zwei Knoten gibt, der keine Sackgassen hat! (Liste der Knoten oder Kanten auf dem Weg in Richtiger Reihenfolge)
Dazu könnte man z.B 1 als Start und 5 als Ziel nehmen

Danke,
-Luk10-

 

[XHelp]

Moment, EIN Pfad, oder Liste aller Kanten, die in allen Pfaden vorkommen?

 

[Luk10]

Eine Liste aller Kanten, die zwischen Knotenliste[start_index] und Knotenliste[end_index] liegen.
Somit ein Pfad durch den Graphen
Ohne Sackgassen, d.h. eine direkte Verbindung!

Wie lange der Weg ist, ist nicht von Bedeutung

 

[Luk10]

Kann nochmal eine Idee von mir bieten, die aber noch nicht vollständig ist:

	public boolean depthFirstSearch(int start_index, int end_index) {
		
		if (start_index == end_index) {
			
			return true;
		
		}
		else {
			
			for (int i = 0; i < nodelist.length; i++) {
				if (adjacencyMatrix[start_index][i] != null && !nodelist[i].isVisited()) {
					
					if (depthFirstSearch(i, end_index) {
						nodelist[start_index].setNext(i);
					}
				}
			}
		}

Was mir Probleme bereitet ist, dass ich
a)

return depthFirstSearch(...)

aufrufen möchte um mir, bei der Abbruchfunktion das true Rückwerts durchzugeben und somit den Sackgassen-freien Weg

und

b) Auf

if(depthFirstSearch(...)

prüfen will, weil ich irgendwie auf den Wert prüfen muss


Wie kann man das machen ohne die Methode 2 Mal rekursiv aufzurufen und damit totalen Mist zu bauen?

-Luk10-

 

[XHelp]

Ja, aber was ist, wenn es x verschiedene Pfade existieren?

   B - C - D - E
S -┤           ├-T
   F - G - H - I 
           |
           K - M

Was erwartest du bei Eingabe von S und T?

 

[Luk10]

Einen möglichen.

Er darf nur keine Sackgassen haben

 

[Marco13]

Nur schnell hingschrieben, ungefähr so könnt's gehen (backtracking quasi), könnte man geschickter machen.... Aber wichtig: Bei Zyklen haut's ihn so glaubich raus (vielleicht auch nicht ? Egal....)

import java.util.*;




public class GraphTest {

     public static void main(String args[])
     {
         GraphTest gt = new GraphTest();
         gt.depthFirstSearch(1,5);
     }

    public boolean depthFirstSearch(int start_index, int end_index)
    {
        List<Knoten> list = new ArrayList<Knoten>();
        depthFirstSearch(start_index, end_index, list);
        System.out.println("Result "+list);
        return true;
    }
    public boolean depthFirstSearch(int start_index, int end_index, List<Knoten> list)
    {
        System.out.println("From "+start_index+" to "+end_index+", currrent "+list);

        if (start_index == end_index) {

            return true;

        }
        else {

            for (int i = 0; i < knotenliste.length; i++) {
                if (adjazenzMatrix[start_index][i] != null && !knotenliste[i].isBesucht()) {

                    knotenliste[i].setBesucht(true);
                    list.add(knotenliste[i]);
                    boolean found = depthFirstSearch(i, end_index, list);
                    if (!found)
                    {
                        list.remove(knotenliste[i]);
                        knotenliste[i].setBesucht(false);
                    }
                    else
                    {
                        return true;
                    }
                }
            }
        }
        return false;
    }


    private Knoten[] knotenliste;
    private Kante[][] adjazenzMatrix;


    public GraphTest() {

        knotenliste = new Knoten[6];
        adjazenzMatrix = new Kante[6][6];

        baueGraph();

    }


    private void baueGraph() {

        knotenliste[0] = new Knoten(0);
        knotenliste[1] = new Knoten(1);
        knotenliste[2] = new Knoten(2);
        knotenliste[3] = new Knoten(3);
        knotenliste[4] = new Knoten(4);
        knotenliste[5] = new Knoten(5);

        adjazenzMatrix[0][1] = new Kante();
        adjazenzMatrix[1][0] = new Kante();

        adjazenzMatrix[1][2] = new Kante();
        adjazenzMatrix[2][1] = new Kante();

        adjazenzMatrix[2][3] = new Kante();
        adjazenzMatrix[3][2] = new Kante();

        adjazenzMatrix[3][4] = new Kante();
        adjazenzMatrix[4][3] = new Kante();

        //Verzweigung
        adjazenzMatrix[2][5] = new Kante();
        adjazenzMatrix[5][2] = new Kante();

    }

}





class Knoten {


    private boolean besucht;
    private int liegtAufPfad; //int: Reihenfolge der Knoten
    private int index;

    public Knoten(int index) {

        this.index = index;
        setBesucht(false);
        setLiegtAufPfad(-1);

    }
    //Getter und Setter


    public void setLiegtAufPfad(int liegtAufPfad) {
        this.liegtAufPfad = liegtAufPfad;
    }


    public int getLiegtAufPfad() {
        return liegtAufPfad;
    }


    public void setBesucht(boolean besucht) {
        this.besucht = besucht;
    }


    public boolean isBesucht() {
        return besucht;
    }

    public String toString()
    {
        return String.valueOf(index);
    }

}



class Kante {


    public Kante() {

    }

}

 

[Luk10]

Wieso sind in deinem Beispiel, danke dafür, 4 Knoten in der Liste, obwohl nur 3 dir sind sollten?

Danke, Luk10

Edit: Genauer: 0 ist auch noch dabei ....

 

[Marco13]

Oh ja, sorry, das hat noch nicht ganz gestimmt: Erstens muss man den startknoten auf "besucht" setzen, und zweitens was das "Rückgängigmachen" noch falsch

    public boolean depthFirstSearch(int start_index, int end_index)
    {
        List<Knoten> list = new ArrayList<Knoten>();
        list.add(knotenliste[start_index]);
        knotenliste[start_index].setBesucht(true);
        depthFirstSearch(start_index, end_index, list);
        System.out.println("Result "+list);
        return true;
    }
    public boolean depthFirstSearch(int start_index, int end_index, List<Knoten> list)
    {
        //System.out.println("From "+start_index+" to "+end_index+", currrent "+list);

        if (start_index == end_index) {

            //System.out.println("DONE");
            return true;

        }
        else {

            for (int i = 0; i < knotenliste.length; i++) {
                if (adjazenzMatrix[start_index][i] != null && !knotenliste[i].isBesucht()) {

                    knotenliste[i].setBesucht(true);
                    list.add(knotenliste[i]);
                    //System.out.println("Adding "+knotenliste[i]);
                    boolean found = depthFirstSearch(i, end_index, list);
                    if (found)
                    {
                        return true;
                    }
                    //System.out.println("Removing "+knotenliste[i]);
                    list.remove(knotenliste[i]);
                    knotenliste[i].setBesucht(false);
                }
            }
        }
        return false;
    }

Vermutlich sollte ich lieber doppelt so lange überlegen, und dann gleich was richtiges posten Aber ... nicht, dass dir noch langweilig wird

EDIT: Ich weiß nicht, ob das so stimmt. Vielleicht schaffe ich es, morgen nochmal ausführlicher zu überlegen und zu schauen.

 

[Luk10]

Finally!

Es ist geschafft.
Vielen Dank, Marco13 und XHelp.

P.S Marco ich habs praktisch "gefixed". Funktioniert jetzt einwandfrei bei mir, vielen Dank