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.