Scribd
Upload
8 views4 pages

DFS and BFS Shortest Path Algorithms

1. The document describes the depth-first search (DFS) and breadth-first search (BFS) algorithms on both undirected and directed graphs. 2. For DFS on an undirected graph, it provides an example trace showing the explored, visited, and solved vertices at each iteration to find the shortest path from A to C to F. 3. For BFS on an undirected graph, it again provides an example trace showing the open and closed vertices at each iteration to find the shortest path from A to F.

Uploaded by

Trungg Quang
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
8 views4 pages

DFS and BFS Shortest Path Algorithms

1. The document describes the depth-first search (DFS) and breadth-first search (BFS) algorithms on both undirected and directed graphs. 2. For DFS on an undirected graph, it provides an example trace showing the explored, visited, and solved vertices at each iteration to find the shortest path from A to C to F. 3. For BFS on an undirected graph, it again provides an example trace showing the open and closed vertices at each iteration to find the shortest path from A to F.

Uploaded by

Trungg Quang
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

DFS Algorithm in undirected graph:

Iteration Solving vertex Explored vertex Visited vertex


0 [A] EMPTY
1 A [B,C,D] A
2 B [G,I, C,D] A,B
3 G [I,C,D] A,B,G
4 I [C,D] A,B,G,I
5 C [E,F,D] A,B,G,I,C
6 E [K,F,D] A,B,G,I,C,E
7 K [F,D] A,B,G,I,C,E,K
8 F [D] A,B,G,I,C,E,K,F
D EMPTY A,B,G,I,C,E,K,F,D
Shortest path: A → C → F

DFS In directed graph:


FIND THE SHORTEST PATH FROM A TO B BY
USING DFS SEARCH

Iteration Vertex Open Close


0 [A20] []
1 [A20] [D6,E7,C15] A20
2 [D6] [I8,F10,E7,C15] A20,D6
3 [I8] [B0,G5,F10,E7,C15] A20,D6,I8
4 [B0] [G5,F10,E7,C15] A20,D6,I8,B0

Shortest path is: A→ D→ I → B

BFS in undirected graph:


Find the shortest path from A to F by using BFS
algorithm.

Iteration Vertex Open CLose


0 [A] []
1 A [B,C,D] A
2 B [C,D,G,I] A,B
3 C [D,G,I,E,F] A,B,C
4 D [G,I,E,F] A,B,C,D
5 G [I,E,F] A,B,C,D,G
6 I [E,F] A,B,C,D,G,I
7 E [F,K] A,B,C,D,G,I,E
8 F [K] A,B,C,D,G,I,E,F
K EMPTY A,B,C,D,G,I,E,F,K

Shortest path: A → C → F
BFS in directed graph:
Find the Shortest path from A to B by using BFS

Iteration vertex Open Close


0 [A] []
1 A20 [D6,E7,C15] A20
2 D6 [E7,C15,I8,F10] A20,D6
3 E7 [C15,I8,F10,G5,K12] A20,D6,E7
4 C15 [I8,F10,G5,K12] A20,D6,E7,C15
5 I8 [F10,G5,K12,B0] A20,D6,E7,C15,I8
6 F10 [G5,K12,B0] A20,D6,E7,C15,I8,F10
7 G5 [K12,B0,H3] A20,D6,E7,C15,I8,F10,G5
8 K12 [B0,H3] A20,D6,E7,C15,I8,F10,G5,K12
9 B0 [H3] A20,D6,E7,C15,I8,F10,G5,K12,B0

Shortest path: A20, D6, I8, G5, B0

You might also like