GraphSearchAndConnectivity

Question 1

Non-exhaustive

Answer 1

I’m going to give you a highly non-exhaustive list on this slide.

Question 2

Hop

Answer 2

跳

Question 3

Ubiquitous

Answer 3

无所不在的

so this refers to the fairly ubiquitous actor Kevin Bacon.

Question 4

Intermediate

Answer 4

中间的 中级的 媒介的

You need one intermediate point

Question 5

Purported

Answer 5

传说的
谣传 声称
I’m going to call end endpoints of this purported edge U and W, where U is the explored one and W is the unexplored one.

Question 6

Colloquial

Answer 6

白话的 通俗的

So the first specific search strategy we’re gonna study is the breadth first search, colloquially known as BFS.

Question 7

Constitute

Answer 7

组成 构成

The neighbors of S will constitute layer-0.

Question 8

Tentative

Answer 8

试验性的

You can think of this as a fairly cautious and tentative exploration of the graph.

Question 9

Plunge

Answer 9

跳入

It’s a much more aggressive search, where you immediately try to plunge as deep as you can.

Question 10

Backtrack

Answer 10

回溯 原路返回
It’s very much in the spirit of how you might explore a maze, where you go as deeply as you can only backtracking when absolutely necessary.