Musterlösung Tiefensuche

Die Tiefensuche gliedert sich auf in ein Startskript und eine Funktion, die dann rekursiv aufgerufen wird.

tiefensuche.m

%% Tiefensuche
 % Die Tiefensuche schreit nach einer rekursiven Programmierung.
 
 clc
 global Gefunden
 
 % Parameter definieren
 StartID = 1; % Startpunkt
 SucheObj = 'N'; % Was wird gesucht
 
 Gefunden = false;
 
 TiefensucheFkt(StartID,SucheObj);
 
 %% Finale Ausgabe
 if Gefunden
 disp('Suche erfolgreich')
 else
 disp('Suche nicht erfolgreich')
 end

Rekursive Funktion:

tiefensucheFkt.m

function tiefensucheFkt(AktKnoten,SucheObj)
 %% Rekursiver Teil der Tiefensuche
 % 
 
 global Graph Gefunden SchonBesucht
 
 disp(['Jetzt bei ' num2str(AktKnoten) ' => ' Graph(AktKnoten).Name ])
 SchonBesucht = [SchonBesucht AktKnoten];
 
 if strcmp(Graph(AktKnoten).Name,SucheObj)
 Gefunden = true;
 disp('Gefunden !!!')
 end
 
 %% Visualisierung
 figure(1)
 hold on
 ph = plot(Graph(AktKnoten).x,Graph(AktKnoten).y,'ro');
 set(ph,'MarkerSize',22)
 hold off
 waitforbuttonpress
 
 
 %% Zugriff auf die verschiedenen Nachbarn unter div Bedingungen
 % 1. Ist das Objekt schon gefunden?
 % 2. Sind schon alle Nachbarn abgearbeitet?
 % 3. Ist der nächste Knoten schon besucht worden?
 jj = 1;
 while ( ~Gefunden && length(Graph(AktKnoten).Nachbarn) >= jj ) 
 if ~(any(SchonBesucht == Graph(AktKnoten).NachbarnID(jj)))
 disp([' von ' Graph(AktKnoten).Name ' nach ' Graph(AktKnoten).Nachbarn(jj)]) 
 tiefensucheFkt(Graph(AktKnoten).NachbarnID(jj),SucheObj)
 end
 jj = jj+1;
 end

Der Aufruf in MatLab erfolgt mit:

>> makegraph >> tiefensuche % mehrmals die Eingabetaste betätigen, um den Ablauf der Tiefensuche vom Knoten A zum Knoten N zu visualisieren!!!

bzw.:

>> makegraph >> tiefensucheFKT(startID z.B. 1, Zielbuchstabe als String z.B. 'J') % mehrmals die Eingabetaste betätigen, um den Ablauf zu visualisieren!!!

Viel Erfolg beim Ausprobieren.

« Vorheriges