수정 된 깊이 우선 검색 파이썬

그래프를 통해 DFS를 수행하여 특정 방식으로 연결된 노드를 찾고 있습니다.수정 된 깊이 우선 검색 파이썬

graphed = { 
    1: [25, 30], 2: [11], 3: [13], 4: [17], 5: [17], 
    6: [26], 7: [11, 12], 8: [10, 13], 9: [14, 26], 
    10: [8, 11, 15], 11: [2, 7, 10], 12: [7, 16, 17], 
    13: [3, 8, 14], 14: [9, 13, 20], 15: [10, 19], 
    16: [12, 18], 17: [4, 5, 12], 18: [16, 21, 22], 
    19: [15, 28, 29], 20: [14, 25], 21: [18, 23], 
    22: [18, 24], 23: [21, 27], 24: [22, 27], 25: [1, 20], 
    26: [6, 9], 27: [23, 24], 28: [19], 29: [19], 30: [1] 
} 

letters = { 
    'S': [1], 
    'C': [10, [11], [12], [13], [14], [15], [16], [17], 
       [18], [19], [20], [21], [22], [23], [24], 
       [25], [26], [27], [28], [29], [30] ], 
    'O': [2, [3], [4], [5], [6]], 
    'N': [7, [8], [9]]} 


some_string = 'CO' 

def dfs(graph, start, num, visited = None): 
    # depth first search for connected nodes 
    k = some_string[num] 
    y = some_string[(num+1)] 
    if visited is None: 
     visited = [] 

    if start in visited: 
     return 

    visited.append(start) 
    # if start corresponds to first letter of string, continue 
    if start in letters.get(k): 
     # find all nodes that it is connected too 
     for each in [x for x in graph[start] if x not in visited]: 
      # if any of the connected nodes correspond to 
      # the next letter of string, continue... 
      if [each] in letters.get(y): 
       dfs(graph, each, (num+1), visited) #recursion 

    return visited 

lst1 = [] 
for i in range(1,len(graphed)): 
    lst1.append(dfs(graphed, i, 0)) 
print(lst1)

현재 DFS 함수에 의해 반환되는 모든 것은 범위 내 i에 대한 원래 시작 값입니다.

[[1], [2], [3], [4], [5], [6], [7], [8], [9], [10], 
[11, 2], [12], [13,3], [14], [15], [16], [17,4], [17,5], 
[18], [19], [20], [21], [22], [23], [24], [25], [26,6], 
[27], [28], [29]]

가 명확히 :

[[1], [2], [3], [4], [5], [6], [7], [8], [9], [10], 
[11], [12], [13], [14], [15], [16], [17], [18], [19], [20], 
[21], [22], [23], [24], [25], [26], [27], [28], [29]]

나는이 기대 내가 DFS 기능을 실행할 수있는 프로그램을 기대; 시작 값이 'C'값이면 연결된 모든 노드를 찾고 'O'에 있는지 확인하십시오. 그렇다면 dfs를 그들과 함께하십시오; 일치하지 않으면 단일 값을 리턴하십시오.

이 기능이 정상적으로 작동하지 않을 것으로 생각됩니다. 감사합니다. 감사합니다.

출처

2017-03-17 Laurie Williams

이 코드에는 몇 가지 문제점이 있습니다. 처음부터 다시 시작하여 점진적 프로그래밍을 사용하는 것이 좋습니다. 몇 줄의 코드를 작성하고 디버깅하고 원하는대로 작동 할 때까지 계속하지 않는 것이 좋습니다. 당신은 당신의 코멘트가 가정하는 기능을 얻지 못하고 있습니다.

방문한 노드 목록이 원하는대로 작동하는지 확신하지 못합니다. 주 프로그램의 루프에 대해 으로 돌아올 때마다 재설정됩니다.

주 프로그램이 마지막 노드 30에 도달하지 않습니다.

주된 문제는 노드 표기법으로 판단됩니다. [7, [8], [9]]과 같은 목록으로 어떤 항목을 만들지는 모르겠지만 노드 번호는 다른 중첩 수준에 있습니다. 그러나 논리에 중첩이 없다고 가정하는 것 같습니다. 예를 들어 이라는 요소를 [10, [11], [12], ...] - 이쪽에서 인 인 것으로 검색했기 때문에 일부 항목을 찾을 수 없습니다. [11]은 후자의 목록의 요소이지만 은 없습니다.

이 아름다운 debug 블로그를 참조하십시오.

일부 변수 이름을 좀 더 의미있는 것으로 변경하는 것을 포함하여 약간의 디버깅을 수행했습니다. 여기 제가 지금 당장 가지고있는 것, 정확히 말하면 첨단 기술 진술서입니다.

graphed = { 1: [25, 30], 2: [11], 3: [13], 4: [17], 5: [17], 6: [26], 7: [11, 12], 8: [10, 13], 9: [14, 26], 10: [8, 11, 15], 11: [2, 7, 10], 12: [7, 16, 17], 13: [3, 8, 14], 14: [9, 13, 20], 15: [10, 19], 16: [12, 18], 17: [4, 5, 12], 18: [16, 21, 22], 19: [15, 28, 29], 20: [14, 25], 21: [18, 23], 22: [18, 24], 23: [21, 27], 24: [22, 27], 25: [1, 20], 26: [6, 9], 27: [23, 24], 28: [19], 29: [19], 30: [1] } letters = { 'S': [1], 'C': [10, [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30] ], 'O': [2, [3], [4], [5], [6]], 'N': [7, [8], [9]]} node_path = 'CO' def dfs(graph, start, num, visited = None): print("ENTER dfs", start, num, visited) # depth first search for connected nodes start_ltr = node_path[num] end_ltr = node_path[(num+1)] if visited is None: visited = [] if start in visited: return visited.append(start) # if start corresponds to first letter of string, continue print(" search for start node", start, "in list", start_ltr, letters.get(start_ltr)) if start in letters.get(start_ltr): # find all nodes that it is connected too for each in [x for x in graph[start] if x not in visited]: print(" found", each, "in", graph[start]) print(" search in list", end_ltr, letters.get(end_ltr)) # if any of the connected nodes correspond to # the next letter of string, continue... if [each] in letters.get(end_ltr): dfs(graph, each, (num+1), visited) #recursion print("LEAVE dfs", visited) return visited lst1 = [] for i in range(1,15): # I cut back the list for less output. lst1.append(dfs(graphed, i, 0)) print(lst1)

출력 : 당신이 이동 얻을

$ python3 so.py ENTER dfs 1 0 None search for start node 1 in list C [10, [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30]] LEAVE dfs [1] ENTER dfs 2 0 None search for start node 2 in list C [10, [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30]] LEAVE dfs [2] ENTER dfs 3 0 None search for start node 3 in list C [10, [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30]] LEAVE dfs [3] ENTER dfs 4 0 None search for start node 4 in list C [10, [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30]] LEAVE dfs [4] ENTER dfs 5 0 None search for start node 5 in list C [10, [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30]] LEAVE dfs [5] ENTER dfs 6 0 None search for start node 6 in list C [10, [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30]] LEAVE dfs [6] ENTER dfs 7 0 None search for start node 7 in list C [10, [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30]] LEAVE dfs [7] ENTER dfs 8 0 None search for start node 8 in list C [10, [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30]] LEAVE dfs [8] ENTER dfs 9 0 None search for start node 9 in list C [10, [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30]] LEAVE dfs [9] ENTER dfs 10 0 None search for start node 10 in list C [10, [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30]] found 8 in [8, 11, 15] search in list O [2, [3], [4], [5], [6]] found 11 in [8, 11, 15] search in list O [2, [3], [4], [5], [6]] found 15 in [8, 11, 15] search in list O [2, [3], [4], [5], [6]] LEAVE dfs [10] ENTER dfs 11 0 None search for start node 11 in list C [10, [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30]] LEAVE dfs [11] ENTER dfs 12 0 None search for start node 12 in list C [10, [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30]] LEAVE dfs [12] ENTER dfs 13 0 None search for start node 13 in list C [10, [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30]] LEAVE dfs [13] ENTER dfs 14 0 None search for start node 14 in list C [10, [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30]] LEAVE dfs [14] [[1], [2], [3], [4], [5], [6], [7], [8], [9], [10], [11], [12], [13], [14]]

합니까?

출처

2017-03-17 23:38:43 Prune

letters 사전의 형식이 잘못되었습니다. 각 문자의 첫 번째 숫자는 최상위 목록에 직접이지만, 다른 모든 항목이 자체적으로 하위 목록에 얼마나

'C': [10, [11], [12], [13], [14], [15], [16], [17], 
      [18], [19], [20], [21], [22], [23], [24], 
      [25], [26], [27], [28], [29], [30] ], 
'O': [2, [3], [4], [5], [6]], 
'N': [7, [8], [9]]}

참고. 결과적으로 if start in letters.get(k)은 잠재적으로 O에 연결된 모든 C 노드에서 false가됩니다.에,

if each in letters.get(y):

또한

if [each] in letters.get(y):

사람 :

letters = { 
    'S': [1], 
    'C': [10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30], 
    'O': [2, 3, 4, 5, 6], 
    'N': [7, 8, 9]}

당신은 이에 따라이 줄을 변경해야합니다 :

>>> 10 in letters.get("C") 
True 
>>> 11 in letters.get("C") 
False

그래서 나는이에 대한 사전 변경 각 재귀 호출의 결과를 some_string 모두가 발견되었을 때의 방법의 상단에 특별한 경우를 추가,

return dfs(graph, each, (num+1), visited) #recursion

마지막으로

dfs(graph, each, (num+1), visited) #recursion

하려면 : 실제로 백업 전달,이 줄을 변경했다

def dfs(graph, start, num, visited = None): 
    # depth first search for connected nodes 
    if (num+1 == len(some_string)): 
     return visited + [start]

이 시점에서 검색에 성공 했으므로 검색 할 편지가 더 이상 없습니다.

출처

2017-03-17 23:39:32 Junuxx

수정 된 깊이 우선 검색 파이썬

답변

관련 문제