Tiefensuche

Trainee

Friday, January 13th 2012, 4:13pm

Tiefensuche

Also wir haben in der Uni grad ein Projekt zur Erstellung von Facebook, werkeln also fleißig dran. Eine der Aufgabe war die [lexicon]Tiefensuche[/lexicon] mit einer Methode zu implementieren. Jedoch bin ich dabei auf ein idiotisches Problem gestoßen.

Das Problem ist folgendes:
Die Suche klappt wunderbar, er springt von Freundesliste zu Freundesliste und sucht nach einem Profil, dass mit dem gesuchten befreundet ist. Das Problem ist hier, dass beim letzten Schritt, als er endlich auf einem Profil ist, das mit dem gesuchten befreundet ist, gibt er mir statt dem true; aus der ersten if()-Anweisung, sondern überprüft es erst gar nicht und springt direkt zum return false; Warum das?

Source code

public boolean areConnected(PersonProfile from, PersonProfile to) {
		if(from.isBefriendedWith(to)) {
		return true;
		}
		 for (PersonProfile friend : from.getFriends()) {
		          if (!friend.getVisited()) {
			       from.setVisited(true);
				   from = friend;
                   areConnected(from, to);
					         }
									  }									  
					return false;
			}

Wasilij50

Trainee

Posts: 23

Friday, January 13th 2012, 6:06pm

Bitte um eine möglichst schnelle Antwort, bin seit 4 stunden kein bischen weiter gekommen...

Hafner

Professional

Posts: 630

Friday, January 13th 2012, 7:43pm

Warum schreibst du
from.setVisited(true);
in das if? Ich würde es eher an den Anfang der Methode schreiben.

Warum setzt du überhaut .setVisited(true) direkt an das Profil, obwohl das nur für deine kleine Suche relevant ist? Was ist wenn man danach nochmal suchen will oder zwei Suchen parallel stattfinden sollen?

Du rufst zwar
areConnected(from, to);
im if auf, machst aber rein garnichts mit dem boolean-Rückgabewert der Methode.

from = friend;
Diese Zuweisung scheint mir falsch zu sein. Das würde ich ganz schnell wegmachen und statt
areConnected(from, to);
lieber
areConnected(friend, to);
schreiben.

Wasilij50

Trainee

Posts: 23

Saturday, January 14th 2012, 3:04pm

Danke für die Hilfe.
Ich habs berücksichtigt. Habe dazu noch eine Hilfsfunktion eingefügt. Aber auf den wichtigsten Punkt, mit der var res, bin ich durch einen Freund gekommen. Aber das mag ich ja an Proggen, man hält sich selten an schwierigen Sachen auf, sondern immer an den Kleinigkeiten

Klappt jetzt wunderbar. Danke nochmals.
mfg Wasilij.

Source code

public boolean areConnected(Person p1, Person p2) {

	boolean res = false;
	if (p1 != null && p2 != null) {
	    if (areFriends(p1, p2)) {
		res = true;
	    } else {
		res = areConnectedR(getProfile(p1), getProfile(p2));
	    }
	}
	return res;
    }

    private boolean areConnectedR(PersonProfile from, PersonProfile to) {
    
    boolean res = false;
	if (from.isBefriendedWith(to)) {
	    res = true;
	} else {
	    from.setVisited(true);
	    for (PersonProfile friend : from.getFriends()) {
		if (friend.isVisited()==false) {
		    res = areConnectedR(friend, to);
		}
	    }
	}

	return res;
    }

Hafner

Professional

Posts: 630

Saturday, January 14th 2012, 5:54pm

Quoted

Aber auf den wichtigsten Punkt, mit der var res, bin ich durch einen Freund gekommen.

Was denkst du denn was ich damit gemeint habe:

Quoted

Du rufst zwar
areConnected(from, to);
im if auf, machst aber rein garnichts mit dem boolean-Rückgabewert der Methode.

Das ist nach wie vor so:

Quoted

Warum schreibst du
from.setVisited(true);
in das if? Ich würde es eher an den Anfang der Methode schreiben.

Das auch:

Quoted

Warum setzt du überhaut .setVisited(true) direkt an das Profil, obwohl das nur für deine kleine Suche relevant ist? Was ist wenn man danach nochmal suchen will oder zwei Suchen parallel stattfinden sollen?

Das hier ist immer noch falsch:

Java Quellcode

for (PersonProfile friend : from.getFriends()) 
{
	if (friend.isVisited()==false) 
	{
    		res = areConnectedR(friend, to);
	}
}

Die Vareable res wird immer wieder überschrieben somit wird nur der letzte Freund in der for-Schleife berücksichtigt.

friend.isVisited()==false schreibt man üblicherweise einfach !friend.isVisited()