1 of 17

1

2

3

4

5

6

7

8

0

s

t

connected(s, t):

  • Mark s.
  • Does s == t? If so, return true.
  • Otherwise, if connected(v, t) for any unmarked neighbor v of s, return true.
  • Return false.

s-t Connectivity

2 of 17

1

2

3

4

5

6

7

8

0

s

t

mark(0).

Is 0 == 7? No.

​

isMarked(1)? No.

  • Check connected(1, 7).

*

connected(s, t):

  • Mark s.
  • Does s == t? If so, return true.
  • Otherwise, if connected(v, t) for any unmarked neighbor v of s, return true.
  • Return false.

s-t Connectivity

3 of 17

1

2

3

4

5

6

7

8

0

s

t

mark(1).

Is 1 == 7? No.

​

isMarked(0)? Yes.

isMarked(2)?

  • Check connected(2, 7).

*

connected(s, t):

  • Mark s.
  • Does s == t? If so, return true.
  • Otherwise, if connected(v, t) for any unmarked neighbor v of s, return true.
  • Return false.

s-t Connectivity

4 of 17

1

2

3

4

5

6

7

8

0

s

t

mark(2).

Is 2 == 7? No.

​

isMarked(1)? Yes.

isMarked(5)?

  • Check connected(5, 7).

*

connected(s, t):

  • Mark s.
  • Does s == t? If so, return true.
  • Otherwise, if connected(v, t) for any unmarked neighbor v of s, return true.
  • Return false.

s-t Connectivity

5 of 17

1

2

3

4

5

6

7

8

0

s

t

mark(5).

Is 5 == 7? No.

​

isMarked(2)? Yes.

isMarked(4)?

  • Check connected(4, 7).

*

connected(s, t):

  • Mark s.
  • Does s == t? If so, return true.
  • Otherwise, if connected(v, t) for any unmarked neighbor v of s, return true.
  • Return false.

s-t Connectivity

6 of 17

1

2

3

4

5

6

7

8

0

s

t

mark(4).

Is 4 == 7? No.

​

isMarked(1)? Yes.

​

isMarked(3)? No.

  • Check connected(3, 7).

*

connected(s, t):

  • Mark s.
  • Does s == t? If so, return true.
  • Otherwise, if connected(v, t) for any unmarked neighbor v of s, return true.
  • Return false.

s-t Connectivity

7 of 17

1

2

3

4

5

6

7

8

0

s

t

mark(3).

Is 3 == 7? No.

​

isMarked(4)? Yes.

​

No more neighbors! Return false.

*

connected(s, t):

  • Mark s.
  • Does s == t? If so, return true.
  • Otherwise, if connected(v, t) for any unmarked neighbor v of s, return true.
  • Return false.

s-t Connectivity

8 of 17

1

2

3

4

5

6

7

8

0

s

t

mark(4).

Is 4 == 7? No.

​

isMarked(1)? Yes.

​

isMarked(3)? No.

  • Check connected(3, 7). Answer was false.

isMarked(5)? Yes.

No more neighbors, so return false.

*

connected(s, t):

  • Mark s.
  • Does s == t? If so, return true.
  • Otherwise, if connected(v, t) for any unmarked neighbor v of s, return true.
  • Return false.

s-t Connectivity

9 of 17

1

2

3

4

5

6

7

8

0

s

t

mark(5).

Is 5 == 7? No.

​

isMarked(2)? Yes.

isMarked(4)?

  • Check connected(4, 7). Answer was false, so keep checking neighbors.

​

isMarked(6)?

  • Check connected(6, 7).

*

connected(s, t):

  • Mark s.
  • Does s == t? If so, return true.
  • Otherwise, if connected(v, t) for any unmarked neighbor v of s, return true.
  • Return false.

s-t Connectivity

10 of 17

1

2

3

4

5

6

7

8

0

s

t

mark(6).

Is 6 == 7? No.

​

isMarked(5)? Yes.

isMarked(7)? No.

  • Check connected(7, 7).

*

connected(s, t):

  • Mark s.
  • Does s == t? If so, return true.
  • Otherwise, if connected(v, t) for any unmarked neighbor v of s, return true.
  • Return false.

s-t Connectivity

11 of 17

1

2

3

4

5

6

7

8

0

s

t

mark(7).

Is 7 == 7? Yes. Return true!

*

connected(s, t):

  • Mark s.
  • Does s == t? If so, return true.
  • Otherwise, if connected(v, t) for any unmarked neighbor v of s, return true.
  • Return false.

s-t Connectivity

12 of 17

1

2

3

4

5

6

7

8

0

s

t

mark(6).

Is 6 == 7? No.

​

isMarked(5)? Yes.

isMarked(7)? No.

  • Check connected(7, 7). Answer was true, so return true.

*

connected(s, t):

  • Mark s.
  • Does s == t? If so, return true.
  • Otherwise, if connected(v, t) for any unmarked neighbor v of s, return true.
  • Return false.

s-t Connectivity

13 of 17

1

2

3

4

5

6

7

8

0

s

t

mark(5).

Is 5 == 7? No.

​

isMarked(2)? Yes.

isMarked(4)?

  • Check connected(4, 7). Answer was false, so keep checking neighbors.

isMarked(5)? Yes.

isMarked(6)?

  • Check connected(6, 7): Return true!

*

connected(s, t):

  • Mark s.
  • Does s == t? If so, return true.
  • Otherwise, if connected(v, t) for any unmarked neighbor v of s, return true.
  • Return false.

s-t Connectivity

14 of 17

1

2

3

4

5

6

7

8

0

s

t

mark(2).

Is 2 == 7? No.

​

isMarked(1)? Yes.

isMarked(5)?

  • Check connected(5, 7). Answer was true, so return true!

*

connected(s, t):

  • Mark s.
  • Does s == t? If so, return true.
  • Otherwise, if connected(v, t) for any unmarked neighbor v of s, return true.
  • Return false.

s-t Connectivity

15 of 17

1

2

3

4

5

6

7

8

0

s

t

mark(1).

Is 1 == 7? No.

​

isMarked(0)? Yes.

isMarked(2)?

  • Check connected(2, 7). Answer was true, so return true!

*

connected(s, t):

  • Mark s.
  • Does s == t? If so, return true.
  • Otherwise, if connected(v, t) for any unmarked neighbor v of s, return true.
  • Return false.

s-t Connectivity

16 of 17

1

2

3

4

5

6

7

8

0

s

t

mark(0).

Is 0 == 7? No.

​

isMarked(1)? No.

  • Check connected(1, 7). Answer was true, so return true!

*

connected(s, t):

  • Mark s.
  • Does s == t? If so, return true.
  • Otherwise, if connected(v, t) for any unmarked neighbor v of s, return true.
  • Return false.

s-t Connectivity

17 of 17

1

2

3

4

5

6

7

8

0

s

t

mark(0).

Is 0 == 7? No.

​

isMarked(1)? No.

  • Check connected(1, 7). Answer was true, so return true!

*

connected(s, t):

  • Mark s.
  • Does s == t? If so, return true.
  • Otherwise, if connected(v, t) for any unmarked neighbor v of s, return true.
  • Return false.

s-t Connectivity