Musterlösung Breitensuche

breitensuche.m
% Breitensuche
%
% Die Breitensuche startet an einem Punkt. Es muss überprüft werden, ob der
% Punkt bereits das gesuchte Objekt ist. Ist dies nicht der Fall, so werden
% die Nachbarn dieses Punktes in einen Zwischenspeicher geschrieben, welcher
% alle Punkte enthält, die noch besucht werden müssen. Dies geschieht aber
% nur dann, wenn der neu erfasste Nachbarpunkt noch nicht in der Liste
% aufgetaucht ist.
%
% Anschliessend wird der nächste Punkt im Zwischenspeicher/Puffer
% ZuBesuchen untersucht.
%
global Graph
% Parameter definieren
StartID = 1; % Startpunkt
SucheObj = 'G'; % Was wird gesucht

ZuBesuchen = [StartID];

Gefunden = false;
AktKnoten = StartID;

%% Suche Starten
% In dieser Sektion wird die eigentliche Suche ausgeführt. Die Reihenfolge,
% in der die Knoten besucht werden, ergibt sich aus den Nachbarn der schon
% besuchten Knoten. Am Anfang befindet sich nur der Startknoten in der
% Suchliste ZuBesuchen.
jj = 1;
while ~Gefunden
% Gefunden?
if strcmp(Graph(AktKnoten).Name,SucheObj)
break
end

% Wenn Nachbarknoten noch nicht auf der Suchliste, dann hinzufügen
for ii = 1:length(Graph(AktKnoten).Nachbarn)
if ~(any(ZuBesuchen == Graph(AktKnoten).NachbarnID(ii)))
ZuBesuchen = [ZuBesuchen Graph(AktKnoten).NachbarnID(ii)];
end
end

% Visualisierung
figure(1)
hold on
ph = plot([Graph(AktKnoten).x Graph(ZuBesuchen(jj)).x],[Graph(AktKnoten).y Graph(ZuBesuchen(jj)).y], ...
'ro ');
set(ph,'MarkerSize',22)
hold off
waitforbuttonpress

%nächster Knoten
AktKnoten = ZuBesuchen(jj);
disp(['Jetzt zu ' Graph(AktKnoten).Name])
jj = jj+1;
end

%% Abschluss
disp('Suchobjekt gefunden')


Der Aufruf in MatLab erfolgt mit:

>> makegraph
>> breitensuche % mehrmals die Eingabetaste betätigen, um den Ablauf der Breitensuche vom Knoten A zum Knoten G zu visualisieren!!!

Auch die Breitensuche hätte rekursiv programmiert werden können, worauf wir hier aber verzichten.