24.02.2011

Bachelor Algorithmen und Datenstrukturen
21

Meine Loesung kann mir jemand sagen ob es stimmt ?
public static boolean allReachable(boolean[][] ug, int node){
return countNeighbours(ug, node, 0) == (ug.length - 1);
}

public static int countNeighbours(boolean[][] ug, int node, int neighbour){
	int result = 0;
	if(neighbour == ug.length){
		return result;
	}
	if(ug[node][neighbour]){
		result += 1 + countNeighbours(ug, node, neighbour + 1);
	}else{
		result += countNeighbours(ug, node, neighbour + 1);
	}
	return result;
}
22

Wenn ich mich nicht täusche, zählst du damit nur, mit wievielen Knoten ein Knoten direkt verbunden ist. Es geht in der Aufgabe aber darum, welche Knoten von einem Knoten aus erreichbar sind.

Ist ein Knoten [m]A[/m] bspw. mit einem Knoten [m]B[/m] verbunden und [m]B[/m] mit einem Knoten [m]C[/m], so ist C von durchaus erreichbar, obwohl keine direkte Verbindung besteht.