figure











Breadth-first search




















Mango seller problem







[Python]

Plain text view
Copy the code

?
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
from
collections
import
deque
def
do_map():

""" Implementation Diagram ""

graph
=
dict
(a)

graph[
"you"
]
=
[
"zhangsan"
.
"lisi"
.
"wangwu"
]

graph[
"zhangsan"
]
=
[
"xiaoming"
.
"xiaohong"
]

graph[
"lisi"
]
=
[
"liniu"
.
"you"
]

graph[
"wangwu"
]
=
[
"wangniu"
.
"mango"
]

graph[
"xiaoming"
]
=
[]

graph[
"xiaohong"
]
=
[]

graph[
"liniu"
]
=
[]

graph[
"wangniu"
]
=
[]

graph[
"mango"
]
=
[]

return
graph
def
check_person(person):

""" Check if you are a seller. ""

if
person
=
=
'mango'
:
# Give a simple condition, as long as the name of mango is the seller

return
True

return
False
def
search(name, graph):

""" Breadth-first Search - Vendors """

search_queue
=
deque()
Create queue

search_queue
+
=
graph[name]
# queue the degree relationship

searched
=
[]
Prepare a list of vendors that have already searched

As long as the queue is not empty,

while
search_queue:

person
=
search_queue.popleft()
# Take out the first person

# Determine if the person has been checked

if
person
not
in
searched:

Determine if this data is a vendor to search for

if
check_person(person):

print
(
'%s is a mango seller'
%
person)

return
True

else
:

# No, queue the person's friends, i.e., second-degree relationships

search_queue
+
=
graph[person]

# Mark this person as checked out

searched.append(person)

# If the queue is not checked, it is not found

return
False
if
__name__
=
=
'__main__'
:

graph
=
do_map()

print
(search(
'you'
, graph))


For more technical information: Gzitcast