Einführung in Algorithmen mit Java-Suche (Tiefenprioritätssuche)

Artikelübersicht

Dies ist eine Reihe von Artikeln, die ich in meiner Studie und meinem Memo zusammengestellt habe. Dies ist eine Fortsetzung dieses Artikels. Einführung in Algorithmen mit Java-Suche (vollständige Suche, Halbierungssuche) In diesem Artikel

• Tiefe Prioritätssuche

Ich werde darüber lernen. Ich habe es in der Fortsetzung des vorherigen Artikels geschrieben.

Tiefenprioritätssuche

Von hier aus ist es so, aber fahren wir fort. Beim Lernen und Zusammenfassen. Tiefenprioritätssuche. Es scheint, dass es auch DFS (Depth-First-Search) genannt wird. Übrigens sehe ich dieses Wort oft. Die Suche nach Tiefenpriorität und die Suche nach Breitenpriorität scheinen für die Suche nach Bäumen und Diagrammen nützlich zu sein. Ich werde die Erklärung von Bäumen und Grafiken weglassen. Die Abbildung ist unten dargestellt. (Aus Wikipedia) Es ist wie bei der DFS, Bäume in dieser Reihenfolge zu durchsuchen, wobei der Tiefe Vorrang eingeräumt wird.

Für diejenigen, die sagen: "Ich weiß nicht, welche Priorität die Tiefe hat!", Ist es meiner Meinung nach ein Schuss, wenn Sie sich die Suchreihenfolge der Suche nach der Breite ansehen.

Hast du den Unterschied in Zahlen gesehen? Bei der Suche nach Tiefenpriorität wird die Suche in einer geraden Linie von der Wurzel zum Knoten ohne untergeordnete Knoten durchgeführt, und bei der Suche nach Breitenpriorität werden die Knoten mit einer Tiefe von 1 in der Reihenfolge von der Wurzel aus durchsucht.

Übrigens gibt es zwei Arten von Implementierungsmethoden.

• Verwendung des Stapels (Datenstruktur "Last In, First Out")
• Verwendung der rekursiven Funktion

Ich habe Angst, weil es verrückt ist. Sie können nicht verstehen, ohne ein Beispiel zu sehen. Wenn Sie nach einem einfachen Beispiel suchen, können Sie es nicht intuitiv finden. .. Wie in der Abbildung oben gezeigt, ist dies nur eine Möglichkeit, in dieser Reihenfolge zu suchen! Ist es so Ich werde es verstehen, wenn ich mir die Problembeispiele anschaue und sie löse. Wenn Sie es verstehen können, können Sie vielleicht ein einfaches Beispiel machen?

Beispiel: AtCoder --arc031-b "Deponie"

\(A1,1\)\(A1,2\)...\(A1,10\)
\(A2,1\)\(A2,2\)...\(A2,10\)
:
\(A10,1\)\(A10,2\)...\(A10,10\)

Ich habe studiert, indem ich mir die Quellen anderer Leute und verschiedene Blogs angesehen habe. Die Richtlinie lautet wie folgt. Vielleicht haben das viele Leute gemacht.

――In 10 * 10 Ländern suchen Sie nach einem Quadrat, das "wenn Sie dieses eine Quadrat füllen, können Sie das Ganze zu einer Insel machen". ――Zählen Sie die Anzahl der Quadrate auf der Insel anhand der Suche nach Tiefenpriorität ab dem ersten ausgewählten Quadrat. Wenn die Anzahl der zu diesem Zeitpunkt gesuchten Quadrate das Quadrat der Insel ist, das in der ersten Eingabe + 1 Quadrat empfangen wurde (wenn das Meer zurückerobert wird), ist die Bedingung erfüllt.

[Antwortbeispiel]

main.java

import java.util.Scanner;

public class Main {

	//Karte der Insel
	static char[][] islandMap;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		//Karte der Insel
		islandMap = new char[10][10];

		//Anzahl der Plätze auf der Insel
		int countIsland = 0;

		//Endgültige Ausgabe
		String ans = "NO";

		//Erhalten Sie Eingaben und vervollständigen Sie die Inselkarte. Zählen Sie die Anzahl der Inselquadrate
		for (int i = 0; i < 10; i++) {
			islandMap[i] = sc.next().toCharArray();
			for (int j = 0; j < 10; j++) {
				if (islandMap[i][j] == 'o') {
					countIsland++;
				}
			}
		}

		//Suchen Sie nach Quadraten vom oberen linken Quadrat mit einer Doppelschleife
		for (int i = 0; i < 10; i++) {
			for (int j = 0; j < 10; j++) {

				//Temporäre Variable für die Anzahl der Inseln
				int countIslandInLoop = countIsland;

				//Lassen Sie das Meer landen. Erhöhen Sie auch die Anzahl der Inseln um eins
				if (islandMap[i][j] == 'x') {
					islandMap[i][j] = 'o';
					countIslandInLoop = countIsland + 1;
				}

				/*
				 *Führen Sie eine Tiefenprioritätssuche durch.
				 *dfsCountIsland ・ ・ ・ Die Anzahl der landgestützten Inseln, die von dfs gezählt werden
				 *markiert ・ ・ ・ Beurteilung, ob das Quadrat von dfs durchsucht wurde
				 */
				dfsIslandCount = 0;
				boolean[][] checked = new boolean[10][10];

				dfs(i, j, checked);

				if (dfsIslandCount == countIslandInLoop) {
					ans = "YES";
					break;
				}

				//Setzen Sie den deponierten Platz zurück und fahren Sie mit der nächsten Schleife fort
				if (countIslandInLoop == countIsland + 1) {
					islandMap[i][j] = 'x';
				}
			}
			if ("YES".equals(ans)) {
				break;
			}
		}

		System.out.println(ans);

	}

	//Anzahl der Quadrate auf landgestützten Inseln, die derzeit von dfs gezählt werden
	static int dfsIslandCount;

	//Tiefenprioritätssuche
	static void dfs(int i, int j, boolean[][] checked) {
		//Wenn es sich jenseits des Platzes befindet, durchsucht wurde oder das Meer ist, ändern Sie die Richtung.
		if (i < 0 || i > 9 || j < 0 || j > 9 || checked[i][j] || islandMap[i][j] == 'x') {
			return;
		}

		//Wenn das gesuchte Quadrat Land ist, erhöhen Sie die Landanzahl
		if (islandMap[i][j] == 'o') {
			dfsIslandCount++;
		}

		//Machen Sie das aktuelle Quadrat durchsucht
		checked[i][j] = true;

		//Suchen Sie nach oben, unten, links und rechts
		dfs(i + 1, j, checked);
		dfs(i - 1, j, checked);
		dfs(i, j + 1, checked);
		dfs(i, j - 1, checked);

		return;

	}
}

Nein, es war wirklich schwierig. Es ist sehr schwierig, es in eine globale Variable einzufügen oder die Suche zu wiederholen.

Es spielt keine Rolle, aber AtCoder hat ein Beispiel für einen solchen Algorithmus vorbereitet. AtCoder --atc001-a "Suche nach Tiefenpriorität"

Vorerst habe ich es als Code für dieses Problem verwendet. Schauen wir uns also den dfs-Teil von oben an.

Ich frage mich, ob ich ungefähr 2 Quadrate sehen kann. Zunächst lautet die Beispieleingabe wie folgt:

xxxxxxxxxx
xoooooooxx
xxoooooxxx
xxxoooxxxx
xxxxoxxxxx
xxxxxxxxxx
xxxxoxxxxx
xxxoooxxxx
xxoooooxxx
xxxxxxxxxx

• × ist das Meer und ○ ist die Insel. Die Karte sieht zu diesem Zeitpunkt wie folgt aus. (Nun, das kann man an der Zeichenkette erkennen.)

Denken wir an die DFS für das Quadrat ① und die DFS für das Quadrat ②.

In der dfs-Methode des obigen Codes zur Verdeutlichung Der erste Prozess ist die if-Anweisung von "// Wenn es das Quadrat überschreitet, gesucht wurde und wenn es das Meer ist, ändern Sie die Richtung." Der zweite Prozess ist "// Wenn die Zelle, nach der Sie suchen, Land ist, wird die Landanzahl erhöht", Der Prozess von Nr. 3 ist "// Das aktuelle Quadrat durchsuchen lassen", Der 4. Prozess ist der Prozess von "// Suche nach Quadraten oben, unten, links und rechts". (Ich werde jedes Mal erklären, welches aufgerufen wird.)

DFS bei ①

Folgen wir der Quelle. Ich werde hauptsächlich erklären, wie man die Masse mit dfs bewegt.

Hier ist die Figur, in der das Quadrat von ① durch den zweiten Prozess ausgefüllt wurde.

Ich habe auch die Werte von i und j hinzugefügt. Dann ist es DFS. Nachdem Sie die aktuelle Zelle vom 3. Prozess durchsucht haben, fahren Sie mit dem 4. Prozess fort. Das erste, was genannt werden muss dfs(i + 1, j, checked); ist. i = 0, j = 0 dfs(1, 0, checked); nicht wahr. Damit bin ich zum Quadrat von i = 1, j = 0 gegangen, aber da das Ziel das Meer ist, werde ich im ersten Prozess von der if-Anweisung erfasst. Wird zurückgegeben.

Fahren Sie als nächstes mit der zweiten Zeile des 4. Prozesses fort. dfs(i - 1, j, checked); Speziell dfs(-1, 0, checked); nicht wahr. Es bewegt sich zum Quadrat von i = -1, j = 0 (außerhalb der Karte) und wird im ersten Prozess zurückgegeben.

Gleiches gilt für die 3. und 4. Zeile. Damit ist die Suche nach Zelle ① abgeschlossen. Es ist schwer zu verstehen, weil es noch nicht rekursiv ist. Ich denke jedoch, es wäre gut, an einem so leicht verständlichen Beispiel zu denken.

DFS bei ②

Hier ist ein Beispiel für die Antwort. Seien wir begeistert und DFS. Hier ist ein Diagramm der Deponie mit i- und j-Nummern.

Nach dem ersten Aufruf wird der rote Teil aufgerufen, die Bewegungen werden programmgesteuert eingerückt und der Reihe nach geschrieben. Mit Einrückung fühlt es sich wie eine Wiederholung an. Wir werden mit dem vierten Prozess des ersten dfs-Aufrufs beginnen. ** Lass uns alles geben! !! ** ** ** Derzeit ist (i, j) = (5,4). Die Reihenfolge, in der sie aufgerufen werden, einschließlich rekursiv, ist wie folgt:

1. dfs(6, 4, checked);
2. dfs(7, 4, checked);
3. dfs(8, 4, checked);
4. dfs (9, 4, geprüft); ← Weil es das Meer ist, endet es
5. dfs (7, 4, markiert); ← Beendet, weil es bereits in der 02. Zeile gesucht wurde
6. dfs(8, 5, checked);
7. dfs (9, 5, geprüft); ← Weil es das Meer ist, endet es
8. dfs(7, 5, checked);
9. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
10. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
11. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
12. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
13. dfs(8, 6, checked);
14. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
15. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
16. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
17. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
18. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
19. dfs(8, 3, checked);
20. dfs (9, 3, geprüft); ← Weil es das Meer ist, endet es
21. dfs(7, 3, checked);
22. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
23. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
24. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
25. dfs (7, 2, geprüft); ← Weil es das Meer ist, endet es
26. dfs(8, 2, checked);
27. dfs (9, 2, geprüft); ← Weil es das Meer ist, endet es
28. dfs (7, 2, geprüft); ← Weil es das Meer ist, endet es
29. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
30. dfs (8, 1, geprüft); ← Weil es das Meer ist, endet es
31. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
32. dfs (6, 4, markiert); ← Beendet, weil in der 01. Zeile gesucht wurde
33. dfs (7, 5, markiert); ← Beendet, weil in der 08. Zeile gesucht wurde
34. dfs (7, 3, markiert); ← Beendet, weil in der 21. Zeile gesucht wurde
35. dfs (5, 4, markiert); ← Ende, weil zuerst gesucht wurde
36. dfs (6, 5, geprüft); ← Weil es das Meer ist, endet es
37. dfs (6, 3, geprüft); ← Weil es das Meer ist, endet es
38. dfs(4, 4, checked);
39. dfs (5, 4, markiert); ← Beenden, weil es zuerst gesucht wurde
40. dfs(3, 4, checked);
41. dfs (4, 4, markiert); ← Beendet, weil in der 38. Zeile gesucht wurde
42. dfs(2, 4, checked);
43. dfs (3, 4, markiert); ← Beendet, weil in der 40. Zeile gesucht wurde
44. dfs(1, 4, checked);
45. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
46. dfs (0, 4, geprüft); ← Weil es das Meer ist, endet es
47. dfs(1, 5, checked);
48. dfs(2, 5, checked);
49. dfs(3, 5, checked);
50. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
51. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
52. 3. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
53. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
54. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
55. dfs(2, 6, checked);
56. 7. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
57. dfs(1, 6, checked);
58. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
59. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
60. dfs(1, 7, checked);
61. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
62. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
63. 4. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
64. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
65. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
66. 7. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
67. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
68. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
69. dfs (0, 5, geprüft); ← Weil es das Meer ist, endet es
70. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
71. 2. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
72. dfs(1, 3, checked);
73. dfs(2, 3, checked);
74. dfs(3, 3, checked);
75. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
76. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
77. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
78. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
79. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
80. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
81. dfs(2, 2, checked);
82. 3. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
83. dfs(1, 2, checked);
84. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
85. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
86. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
87. dfs(1, 1, checked);
88. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
89. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
90. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
91. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
92. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
93. 4. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
94. 5. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
95. 6. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
96. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
97. dfs (2, 5, markiert); ← Beendet, weil in der 42. Zeile gesucht wurde
98. dfs (2, 3, markiert); ← Beendet, weil es in der 74. Zeile gesucht wurde
99. dfs (3, 5, markiert); ← Beendet, weil in der 50. Zeile gesucht wurde
100. dfs (3, 3, markiert); ← Beendet, weil in der 75. Zeile gesucht wurde
101. dfs (4, 5, geprüft); ← Weil es das Meer ist, endet es
102. dfs (4, 3, geprüft); ← Weil es das Meer ist, endet es
103. dfs (5, 5, geprüft); ← Weil es das Meer ist, endet es
104. dfs (5, 3, geprüft); ← Weil es das Meer ist, endet es

** Oh ... es ist vorbei ... ** Ich bin super müde Es war nichts, was die Leute von Hand machen würden. Nun, ich habe es so oft gemacht, also lasst uns überprüfen, nach welcher Art von Bewegung gesucht wurde. Ich habe versucht, die Suchreihenfolge in weißen Buchstaben auszudrücken.

Sie können es sehen, indem Sie die Figur betrachten, und Sie können es sehen, indem Sie das Gefühl der Schleife betrachten, aber DFS ist wie "Wenn Sie nicht zum Punkt kommen, ändern Sie die Richtung."

Ich denke auch, dass das Wort "Stapel" herauskam, aber es scheint, dass diese rekursive Methode genau die Reihenfolge der First-In- und Last-Out-Stapel ist. Selbst wenn Sie die als Stack bezeichnete Datenstruktur nicht verwenden, können Sie feststellen, dass die Implementierung beim rekursiven Schreiben wie ein Stapel verarbeitet wird.

Haben Sie die Tiefenprioritätssuche verstanden? Ich konnte ein wenig verstehen. (Oh, ich bin müde ...)

Es ist lange her, daher werde ich das nächste Mal die Suche nach der Breite der Priorität noch einmal erläutern. Nächstes Mal freuen wir uns! !!