DMA DFS/ BFS tree

Problem 1: Using Depth-First-Search’s algorithm, show visiting process and the final level graph with starting vertex is A in the Figure 1(a).

Problem 2: Using Depth-First-Search’s algorithm, show visiting process and the final level graph with starting vertex is A in the Figure 1(b).

Problem 3: Using Breadth-First-Search’s algorithm, show visiting process and the final level graph with starting vertex is A in the Figure 1(a).

Problem 4: Using Breadth-First-Search’s algorithm, show visiting process and the final level graph with starting vertex is A in the Figure 1(a).

Point

DFS深さ優先探索

Stack : LIFO 　
深さを先に左から順に行っていく。

BFSは幅優先探索

Queue : FIFO
近い距離から順に行っていく。

以下は、DFSとBFSの探索過程を表形式で示したものです。

---

Problem 1: DFS on Figure 1(a)

Step	Current Vertex	Open Stack (左がtop)	Close List
0	—	[A]	[]
1	A	[B, G]	[A]
2	B	[C, E, G]	[A, B]
3	C	[D, F, E, G]	[A, B, C]
4	D	[F, E, G]	[A, B, C, D]
5	F	[E, G]	[A, B, C, D, F]
6	E	[G]	[A, B, C, D, F, E]
7	G	[H]	[A, B, C, D, F, E, G]
8	H	[K, L]	[A, B, C, D, F, E, G, H]
9	K	[L]	[A, B, C, D, F, E, G, H, K]
10	L	[]	[A, B, C, D, F, E, G, H, K, L]

最終訪問順: A → B → C → D → F → E → G → H → K → L

---

Problem 2: DFS on Figure 1(b)

Step	Current Vertex	Open Stack (左がtop)	Close List
0	—	[A]	[]
1	A	[B, E, G]	[A]
2	B	[C, E, G]	[A, B]
3	C	[D, F, E, G]	[A, B, C]
4	D	[F, E, G]	[A, B, C, D]
5	F	[E, G]	[A, B, C, D, F]
6	E	[K, G]	[A, B, C, D, F, E]
7	K	[G]	[A, B, C, D, F, E, K]
8	G	[H]	[A, B, C, D, F, E, K, G]
9	H	[L]	[A, B, C, D, F, E, K, G, H]
10	L	[]	[A, B, C, D, F, E, K, G, H, L]

最終訪問順: A → B → C → D → F → E → K → G → H → L

---

Problem 3: BFS on Figure 1(a)

Step	Current Vertex	Open Queue (左がfront)	Close List
0	—	[A]	[]
1	A	[B, G]	[A]
2	B	[G, C, E]	[A, B]
3	G	[C, E, H]	[A, B, G]
4	C	[E, H, D, F]	[A, B, G, C]
5	E	[H, D, F]	[A, B, G, C, E]
6	H	[D, F, K, L]	[A, B, G, C, E, H]
7	D	[F, K, L]	[A, B, G, C, E, H, D]
8	F	[K, L]	[A, B, G, C, E, H, D, F]
9	K	[L]	[A, B, G, C, E, H, D, F, K]
10	L	[]	[A, B, G, C, E, H, D, F, K, L]

最終訪問順: A → B → G → C → E → H → D → F → K → L

---

Problem 4: BFS on Figure 1(b) (修正版)

Step	Current Vertex	Open Queue (左がfront)	Close List
0	—	[A]	[]
1	A	[B, E, G]	[A]
2	B	[E, G, C]	[A, B]
3	E	[G, C, K]	[A, B, E]
4	G	[C, K, H]	[A, B, E, G]
5	C	[K, H, D, F]	[A, B, E, G, C]
6	K	[H, D, F]	[A, B, E, G, C, K]
7	H	[D, F, L]	[A, B, E, G, C, K, H]
8	D	[F, L]	[A, B, E, G, C, K, H, D]
9	F	[L]	[A, B, E, G, C, K, H, D, F]
10	L	[]	[A, B, E, G, C, K, H, D, F, L]

最終訪問順: A → B → E → G → C → K → H → D → F → L

---