2、根据这个标记顺序,会有且仅有0-1,1-3,3-2,3-5,5-6,6-4被选中。
3、在访问其中一个顶点时,将它标记为已访问,递归的访问它所有没有被标记的相邻顶点。
4、运行看结果。Python由荷兰数学和计算机科学研究学会的吉多·范罗苏姆于1990年代初设计,作为一门叫做ABC语言的替代品。
大树满足条件的和 等于 每个子树满足条件的数的和之和
result = 0 + 10 + 15 + 18
深度优先搜索必然会使用到 递归
必须使用到辅助队列,用于判断
找到共同的祖先
对相同像素的相邻位置进行渲染
给定一个包含了一些 0 和 1 的非空二维数组 grid 。
一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合,这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0(代表水)包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿,则返回面积为 0 。)
graph=
{'A':
['B',
'C'],
'B':
['C',
'D'],
'C':
['D'],
'D':
['C','G','H'],
'E':
['F'],
'F':
['C']}
#从图中找出任意一条从起始顶点到终止顶点的路径
def
find_path(graph,
start,
end,
path=[]):
if
start
==
end:
"path",
path
return
True
if
not
graph.get(start):
path.pop()
return
False
for
v
in
graph[start]:
if
v
not
in
path:
path.append(v)
if
find_path(graph,v,end,path):
return
True
return
False
path
=
[]
if
find_path(graph,
'A',
'C',
path=path):
print(path)
else:
print(1)
#从图中找出从起始顶点到终止顶点的所有路径
import
copy
def
find_path_all(curr,
end,
path):
'''
:param
curr:
当前顶点
:param
end:
要到达的顶点
:param
path:
当前顶点的一条父路径
:return:
'''
if
curr
==
end:
path_tmp
=
copy.deepcopy(path)
path_all.append(path_tmp)
return
if
not
graph.get(curr):
return
for
v
in
graph[curr]:
#一个顶点在当前递归路径中只能出现一次,否则会陷入死循环。
if
v
in
path:
print("v
%s
in
path
%s"
%(v,
path))
continue
#构造下次递归的父路径
path.append(v)
find_path_all(v,end,path)
path.pop()
path_all
=
[]
find_path_all('A',
'G',path=['A'])
path_all
#遍历图中所有顶点,按照遍历顺序将顶点添加到列表中
vertex
=
[]
def
dfs(v):
if
v
not
in
graph:
return
for
vv
in
graph[v]:
if
vv
not
in
vertex:
vertex.append(vv)
dfs(vv)
for
v
in
graph:
if
v
not
in
vertex:
vertex.append(v)
dfs(v)
print(vertex)