程序代写代做代考 algorithm data structure PowerPoint Presentation

‹#›
16

We know found nodes are reachable from s because we have traced out a path.
If a node has been handled,
then all of its neighbors
have been found.
Graph Search

Exit

a
c
h
k
f
i
m
j
e
b
g
d

l

All found nodes are handled.

Exit

Found nodes are reachable from s.
Reachable nodes have been found. :

‹#›
17

We know found nodes are reachable from s because we have traced out a path.
If a node has been handled,
then all of its neighbors
have been found.
Graph Search

Exit

a
c
h
k
f
i
m
j
e
b
g
d

l

All found nodes are handled.

Exit

Reachable nodes have been Found. :

Found = handled

handled
notfound

[A  B] = [B  A]
notFound nodes not reachable.

‹#›
18

Graph Search
Specification of Reachability-from-single-source s :
The input is a graph G
(either directed or undirected)
and a source node s. :
Output all the nodes u that are
reachable by a path in G from s.
Ending
Initial Conditions
Make Progress
Maintain Loop Inv
Define Exit Condition
Define Step
Define Measure of Progress
Define Loop Invariants
Define Problem

79 km
to school

Exit

Exit

79 km

75 km

Exit

Exit

0 km

Exit

‹#›
19

Graph Search

# of handled nodes.
Handle some foundNotHandled node

Time =
O(n)

f

u

j
O(n) iterations,
but iteration takes more than O(1)

O(n) neighbors
= O(n2)
Could be fewer?
Each edge visited, times.
2
= O(E)
Size =
O(E)
Linear time.

‹#›
20

Graph Search
Which foundNotHandled node do we handle?

Queue:
Handle node
Found longest ago
Likely closest to s (in # of edges).
Breadth-First Search
Priority Queue:
Handle node that seems to be closest to s (weighted).
Dijkstra’s Shortest-Weighted Paths
Stack:
Handle node
Found most recently
Likely farthest from s.
Depth-First Search

‹#›
21

Graph Search
Which foundNotHandled node do we handle?

Queue:
Handle node
Found longest ago
Likely closest to s (in # of edges).
Breadth-First Search

So far, the nodes have been found in order of length from s.

‹#›
22

BFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

Found
Not Handled
Queue

‹#›
23

BFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

Found
Not Handled
Queue

s

d=0

d=0

‹#›
24

BFS

Found
Not Handled
Queue

d=0
a
b
g
d

d=1

s
a
c
h
k
f
i
l
m
j
e
b
g
d

d=0
d=1

‹#›
25

BFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

Found
Not Handled
Queue

a
b
g
d

d=0
d=1

d=1

‹#›
26

BFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

Found
Not Handled
Queue

b
g
d

c
f

d=0
d=1
d=2

d=1
d=2

‹#›
27

BFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

Found
Not Handled
Queue

b
g

c
f

m
e

d=0
d=1
d=2

d=1
d=2

‹#›
28

BFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

Found
Not Handled
Queue

d=0
d=1
d=2

b
j
c
f
m
e

d=1
d=2

‹#›
29

BFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

Found
Not Handled
Queue

d=0
d=1
d=2

j
c
f
m
e

d=1
d=2

‹#›
30

BFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

Found
Not Handled
Queue

c
f

m
e

j

d=0
d=1
d=2

d=2

‹#›
31

BFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

Found
Not Handled
Queue

f

m
e

j

h
i

d=0
d=1
d=2
d=3

d=2
d=3

‹#›
32

BFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

Found
Not Handled
Queue

m
e

j

h
i

d=0
d=1
d=2
d=3

d=2
d=3

‹#›
33

BFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

Found
Not Handled
Queue

e

j

h
i

l

d=0
d=1
d=2
d=3

d=2
d=3

‹#›
34

BFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

Found
Not Handled
Queue

j

h
i

l

d=0
d=1
d=2
d=3

d=2
d=3

‹#›
35

BFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

Found
Not Handled
Queue

h
i

l

d=0
d=1
d=2
d=3

d=2
d=3

‹#›
36

BFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

Found
Not Handled
Queue

h

d=0
d=1
d=2
d=3

i
l
d=3

‹#›
37

BFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

Found
Not Handled
Queue

i

l
k

d=0
d=1
d=2
d=3
d=4

d=3
d=4

‹#›
38

BFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

Found
Not Handled
Queue

l
k

d=0
d=1
d=2
d=3
d=4

d=3
d=4

‹#›
39

BFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

Found
Not Handled
Queue

k

d=0
d=1
d=2
d=3
d=4

d=3
d=4

‹#›
40

BFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

Found
Not Handled
Queue

k

d=0
d=1
d=2
d=3
d=4

d=4

‹#›
41

BFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

Found
Not Handled
Queue

d=0
d=1
d=2
d=3
d=4

d=4
d=5

‹#›
42

BFS

So far, the nodes have been found in order of length from s.

‹#›
43

BFS

So far, the nodes have been found in order of length from s. :
Finds a shortest path from s
to each node v and its length.

When we find v, we know
there isn’t a shorter path to it because ?
Otherwise, we would have found it already.

‹#›
44

BFS
Data structure for storing a path to each node:
For each node v, store (v) to be parent of v.

‹#›
45

Basic Steps:

s
u

The shortest path to u
has length d

v
& there is an edge
from u to v
There is a path to v with length d+1.
BFS
Parent of v is
(v) = u.

‹#›
46

‹#›
47

Graph Search
Which foundNotHandled node do we handle?

Queue:
Handle node
Found longest ago
Likely closest to s (in # of edges).
Breadth-First Search
Priority Queue:
Handle node that seems to be closest to s (weighted).
Dijkstra’s Shortest-Weighted Paths
Stack:
Handle node
Found most recently
Likely farthest from s.
Depth-First Search

‹#›
48

Dijkstra’s Shortest-Weighted Paths
Specification: Dijkstra’s Shortest-Weighted Paths
Reachability-from-single-source s :
The input is a graph G
(either directed or undirected)
with positive edge weights
and a source node s. :
Finds a shortest weighted path from s
to each node v and its length.

‹#›
49

Dijkstra’s Shortest-Weighted Paths
The king wanted to know the shortest path from his castle s to each node (home) v.
So that people could come and go quickly
and so that he could guard these home and paths.

s
D( ) = length = 8.

5
3
( ) = previous node in path

‹#›

Dijkstra’s Shortest-Weighted Paths
Rome was not built in a day.
He decided to handle the nodes in terms of their distance from s.
He put a wall around these handled nodes.

s

‹#›

Dijkstra’s Shortest-Weighted Paths

We have the answer for handled nodes
(i.e. closest)
i.e. D(u) and (u)
give shortest path from s to u.

Exit

When all the nodes
are handled, done!
s

‹#›

Dijkstra’s Shortest-Weighted Paths

When a node has
been handled:
He put a knight on each handled node to guard all edges (roads) leading out of the node.
An edge is handled if it comes out of a handled node.
i.e. all edges in
and leaving city.

s

‹#›

Dijkstra’s Shortest-Weighted Paths

Unhandled edges
are unguarded, so
we don’t want to travel along them,
even if they make a shorter path.

s

‹#›

Dijkstra’s Shortest-Weighted Paths

s
A path is handled if has handled edges.
i.e. path travels from s
between the handled nodes within the walls and then one last edge out at gate.
For unhandled nodes, (u) and d(u) values give the shortest
handled path from s.

d( )=8.

d( )=20.

d( )=



‹#›

Dijkstra’s Shortest-Weighted Paths

s

d( )=8.

5
d( ) + w( , )
= 8 + 5
= 13

This red path to
has length

This is better but unhandled and
hence unguarded.
d( )=20.

‹#›

Dijkstra’s Shortest-Weighted Paths

s

d( )=8.

5
Theorem: If has the smallest d value, then its shortest path from s is handled.

Proof: Any unhandled
path must leave at a different gate, and hence already has gone further than d( ).

d( )=20.

D

‹#›

Dijkstra’s Shortest-Weighted Paths

s

D( )=8.

5

Consider the unhandled node
with the smallest
d( ).

d( )=20.

Priority Queue
(FoundNotHandled):
Handle node that
seems to be closest
to s.

‹#›

Dijkstra’s Shortest-Weighted Paths

s

D( )=8.

5

Consider the unhandled node
with the smallest
d( ).

Handled it.
Handle out going edges.
Update its neighbor’s
d values.
d( )=20.

‹#›

Dijkstra’s Shortest-Weighted Paths

s

D( )=8.

5
d( ) + w( , )
= 8 + 5
= 13

This red path to
has length

This is better but
was unhandled .
d( )=20.

But with handled, this edge is now handled so we are good.

‹#›

Dijkstra’s Shortest-Weighted Paths

s

D( )=8.

5
d( ) + w( , )
= 8 + 5
= 13

This red path to
has length

d( )=20.

But with handled, this edge is now handled so we are good.

13
( )

This is better but
was unhandled .

‹#›

Dijkstra’s Shortest-Weighted Paths

s

D( )=8.

5
d( )=13.

( )

We have the answer for handled nodes
(i.e. closest)
i.e. D(u) and (u)
give shortest path from s to u.
Done!

‹#›

Dijkstra’s Shortest-Weighted Paths

s

D( )=8.

5
d( )=13.

( )

Done!
For unhandled nodes, (u) and d(u) values give the shortest
handled path from s.

‹#›

Dijkstra’s Shortest-Weighted Paths

s

D( )=8.

5
d( )=13.

( )

Ending
Initial Conditions
Make Progress
Maintain Loop Inv
Define Exit Condition
Define Step
Define Measure of Progress
Define Loop Invariants
Define Problem

79 km
to school

Exit

Exit

79 km

75 km

Exit

Exit

0 km

Exit

Done!

‹#›

‹#›
65

Dijkstra’s

u

v

s

Handled nodes
Found nodes
Handled Edges?
Definition of handled paths and d(v)

‹#›
66

Dijkstra’s

u

v

s

Handled nodes

Found nodes
Handled Edges
Handled Paths?
Definition of handled paths and d(v)

‹#›
67

Dijkstra’s

u

v

s

Handled nodes

Found nodes
Definition of handled paths and d(v)

Handled Edges
Handled Paths?

‹#›
68

Dijkstra’s

u

v

s

Handled nodes

d(v) is the length of the
shortest handled paths to v.
For handled u,
d(u) is the length of the
shortest paths to u.

NotFound
d(v’)=


Definition of handled paths and d(v)

‹#›
69

u

The shortest of handled paths
to u has length d(u)
Dijkstra’s

& there is an edge
from u to v
w

v

s

The shortest of handled paths
to v has length d(v)
The shortest handled path to v has length
min( d(v), d(u)+w ).
Handle node that “seems” to be closest to s.
Basic Steps:

‹#›
70

s
c
b

Dijkstra’s

a

d

f

i

j

h

e

g

40
1
10
2
15
1
2
6
8
1
2
30
3

d=
d=
d=
d=
d=
d=
d=
d=0
d=
d=
d=

30
1
2

3
3

Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level

‹#›
71

s
c
b

Dijkstra’s

a

d

f

i

j

h

e

g

40
1
10
2
1
6
8
1
2
30
3

d=1
d=
d=
d=
d=
d=10
d=0
d=40
d=
d=30

30
1
15
2
2

3
d=
3

Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level

‹#›
72

s
c
b

Dijkstra’s

a

d

f

i

j

h

e

g

40
1
10
2
1
1
6
8
1
2
30
3

d=1
d=3
d=
d=
d=
d=
d=10
d=0
d=31
d=
d=30

30
15
2
2

3
3

Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level

‹#›
73

s
c
b

Dijkstra’s

a

d
f

i

j

h

e

g

40
1
10
2
1
1
6
8
1
2
30
3

d=1
d=3
d=
d=
d=
d=
d=10
d=0
d=31
d=4
d=18

30

15
2
2

3
3

Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level

‹#›
74

s
c
b

Dijkstra’s

a

d
f

i

j

h

e

g

40
1
10
2
1
1
6
8
1
2
30
3

d=1
d=3
d=
d=
d=10
d=
d=10
d=0
d=6
d=4
d=5

30

1
15
2

3
3

Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level

‹#›
75

s
c
b

Dijkstra’s

a
d
f

i

j

h

e

g

40
1
10
2
1
1
6
8
1
2
30
3

d=1
d=3
d=
d=
d=7
d=
d=10
d=0
d=6
d=4
d=5

30

1
15
2

3
3

Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level

‹#›
76

s
c
b

Dijkstra’s

a
d
f

i

j

h

e

g

40
1
10
2
1
1
6
8
1
2
30
3

d=1
d=3
d=
d=
d=7
d=
d=9
d=0
d=6
d=4
d=5

30

1
15
2

3

3

Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level

‹#›
77

s
c
b

Dijkstra’s

a
d
f

i

j
h

e

g

40
1
10
2
1
1
6
8
1
2
30
3

d=1
d=3
d=
d=
d=7
d=15
d=8
d=0
d=6
d=4
d=5

30

1
15
2

3

3

Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level

‹#›
78

s
c
b

Dijkstra’s

a
d
f

i

j
h

e

g

40
1
10
2
1
1
6
8
1
2
30
3

d=1
d=3
d=
d=
d=7
d=10
d=8
d=0
d=6
d=4
d=5

30

1
15
2

3

3

Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level

‹#›
79

s
c
b

Dijkstra’s

a
d
f

i

j
h

e

g

40
1
10
2
1
1
6
8
1
2
30
3

d=1
d=3
d=
d=
d=7
d=10
d=8
d=0
d=6
d=4
d=5

30

1
15
2

3

3

Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level

‹#›
80

s
c
b

Dijkstra’s

a
d
f
i

j
h

e

g

40
1
10
2
1
1
6
8
1
2
30
3

d=1
d=3
d=
d=
d=7
d=10
d=8
d=0
d=6
d=4
d=5

30

1
15
2

3

3

Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level

‹#›
81

s
c
b

Dijkstra’s

a
d
f
i

j
h

e

g

40
1
10
2
1
1
6
8
1
2
30
3

d=1
d=3
d=
d=
d=7
d=10
d=8
d=0
d=6
d=4
d=5

30

1
15
2

3

DONE
3

Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level

‹#›
82

Time = O(E)
Each edge visited, times.
2
?
Dijkstra’s
This number of times following an edge.
Must update Priority Queue.
Takes time O(log(n))
Time = O(E log(n))
For each update,
d(v) = min( d(v), d(u)+w ).
Heap

‹#›
83

Dijkstra’s
0
13
16
17
20
∞
Handle c

19
37
Π(h) =c
Π(e) =c

‹#›
84

Adaptable Heap
Pop/Push/Changes
But now it is not a heap!
The 10 “bubbles” down or up until it finds its spot.
Suppose some outside user
knows about
some data item c
and remembers where
it is in the heap.
And changes its priority
from 21 to 10

21
c

21
10
10

15

2

‹#›

85

Adaptable Heap
Pop/Push/Changes
But now it is not a heap!
The 10 “bubbles” down or up until it finds its spot.
Suppose some outside user
also knows about
data item f and its location
in the heap just changed.
The Heap must be able
to find this outside user
and tell him it moved.

21
c
15
10

10

15
f

Time = O(log n)
2

‹#›

86

Heap Implementation
A location-aware heap entry is an object storing
key
value
position of the entry in the underlying heap
In turn, each heap position stores an entry
Back pointers are updated during entry swaps
Last Update: Oct 23, 2014
Andy
87

4
a

2
d

6
b

8
g

5
e

9
c

‹#›

Dijkstra’s

‹#›
88

Dijkstra’s

‹#›
89

Graph Search
Which foundNotHandled node do we handle?

Queue:
Handle node
Found longest ago
Likely closest to s (in # of edges).
Breadth-First Search
Priority Queue:
Handle node that seems to be closest to s (weighted).
Dijkstra’s Shortest-Weighted Paths
Stack:
Handle node
Found most recently
Likely farthest from s.
Depth-First Search

‹#›
90

DFS

Breadth first search makes a lot of sense for dating in general actually. It suggests dating a bunch of people casually before getting serious rather than having a series of five year relationships.

‹#›
91

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

Found
Not Handled
Stack

‹#›
92

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

Found
Not Handled
Stack

s

‹#›
93

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

Found
Not Handled
Stack

a
b
g
d

‹#›
94

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

Found
Not Handled
Stack

a
m
g
d

e

‹#›
95

DFS

‹#›
96

DFS

The nodes in the stack form a path starting at s.

‹#›
97

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

Found
Not Handled
Stack

‹#›
98

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

Found
Not Handled
Stack

s,0

‹#›
99

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,1

Found
Not Handled
Stack

a,0

‹#›
100

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,1

Found
Not Handled
Stack

a,1
c,0

‹#›
101

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,1

Found
Not Handled
Stack

a,1
c,1

h,0

‹#›
102

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,1

Found
Not Handled
Stack

a,1
c,1

h,1

k,0

‹#›
103

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,1

Found
Not Handled
Stack

a,1
c,1

h,1

Tree Edge
Path on Stack

‹#›
104

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,1

Found
Not Handled
Stack

a,1
c,1

‹#›
105

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,1

Found
Not Handled
Stack

a,1
c,2

i,0

‹#›
106

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,1

Found
Not Handled
Stack

a,1
c,2

i,1

Cross Edge
to handled node

‹#›
107

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,1

Found
Not Handled
Stack

a,1
c,2

i,2

‹#›
108

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,1

Found
Not Handled
Stack

a,1
c,2

i,3

l,0

‹#›
109

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,1

Found
Not Handled
Stack

a,1
c,2

i,3

l,1

‹#›
110

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,1

Found
Not Handled
Stack

a,1
c,2

i,3

‹#›
111

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,1

Found
Not Handled
Stack

a,1
c,2

i,4

g,0

‹#›
112

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,1

Found
Not Handled
Stack

a,1
c,2

i,4

g,1

j,0

‹#›
113

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,1

Found
Not Handled
Stack

a,1
c,2

i,4

g,1

j,1

Back Edge
to node on Stack
Forms a cycle

‹#›
114

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,1

Found
Not Handled
Stack

a,1
c,2

i,4

g,1

j,2

m,0

‹#›
115

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,1

Found
Not Handled
Stack

a,1
c,2

i,4

g,1

j,2

m,1

‹#›
116

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,1

Found
Not Handled
Stack

a,1
c,2

i,4

g,1

j,2

‹#›
117

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,1

Found
Not Handled
Stack

a,1
c,2

i,4

g,1

‹#›
118

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,1

Found
Not Handled
Stack

a,1
c,2

i,4

‹#›
119

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,1

Found
Not Handled
Stack

a,1
c,2

i,5

f,0

‹#›
120

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,1

Found
Not Handled
Stack

a,1
c,2

i,5

f,1

‹#›
121

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,1

Found
Not Handled
Stack

a,1
c,2

i,5

‹#›
122

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,1

Found
Not Handled
Stack

a,1
c,2

‹#›
123

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,1

Found
Not Handled
Stack

a,1
c,3

‹#›
124

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,1

Found
Not Handled
Stack

a,1

‹#›
125

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,1

Found
Not Handled
Stack

a,2

‹#›
126

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,1

Found
Not Handled
Stack

‹#›
127

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,2

Found
Not Handled
Stack

d,1

‹#›
128

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,2

Found
Not Handled
Stack

d,2

‹#›
129

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,2

Found
Not Handled
Stack

d,3

e,0

‹#›
130

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,2

Found
Not Handled
Stack

d,3

e,1

‹#›
131

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,2

Found
Not Handled
Stack

d,3

‹#›
132

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,2

Found
Not Handled
Stack

‹#›
133

DFS

s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,3

Found
Not Handled
Stack

‹#›
134

DFS
s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,4

Found
Not Handled
Stack

b,0

‹#›
135

DFS
s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,4

Found
Not Handled
Stack

b,1

‹#›
136

DFS
s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,4

Found
Not Handled
Stack

b,2

‹#›
137

DFS
s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,4

Found
Not Handled
Stack

b,3

‹#›
138

DFS
s
a
c
h
k
f
i
l
m
j
e
b
g
d

s,4

Found
Not Handled
Stack

‹#›
139

DFS
s
a
c
h
k
f
i
l
m
j
e
b
g
d

Found
Not Handled
Stack

done

‹#›
140

‹#›
141

Recursive
Depth First
Search
Get help from
friends

‹#›
142

‹#›
143

Linear Order

underwear
pants
socks

shoes

underwear
pants
socks
shoes

socks
underwear
pants
shoes

‹#›
144

Linear Order

underwear
pants
socks

shoes
?

‹#›
145

Linear Order

a

b
h

c
i

d
j

e
k

f
l

g