폭 우선 검색에서 경로를 추적하는 방법은 무엇입니까?

폭 우선 검색에서 경로를 추적하는 방법은 무엇입니까?

다음 예와 같이 폭 우선 검색의 경로를 추적하는 방법은 무엇입니까?

키를 검색하는 경우111에서 11을 연결하는 가장 짧은 목록을 반환합니다.

[1, 4, 7, 11]

당신은 먼저 http://en.wikipedia.org/wiki/Breadth-first_search 을 살펴봤어야 합니다.

---

아래는 빠른 구현으로, 목록을 사용하여 경로 대기열을 나타냅니다.

# graph is in adjacent list representation
graph = {
        '1': ['2', '3', '4'],
        '2': ['5', '6'],
        '5': ['9', '10'],
        '4': ['7', '8'],
        '7': ['11', '12']
        }

def bfs(graph, start, end):
    # maintain a queue of paths
    queue = []
    # push the first path into the queue
    queue.append([start])
    while queue:
        # get the first path from the queue
        path = queue.pop(0)
        # get the last node from the path
        node = path[-1]
        # path found
        if node == end:
            return path
        # enumerate all adjacent nodes, construct a 
        # new path and push it into the queue
        for adjacent in graph.get(node, []):
            new_path = list(path)
            new_path.append(adjacent)
            queue.append(new_path)

print bfs(graph, '1', '11')

인쇄할 내용:['1', '4', '7', '11']

---

또 다른 방법은 각 노드에서 상위 노드로의 매핑을 유지 관리하고 인접 노드를 검사할 때 상위 노드를 기록하는 것입니다.검색이 완료되면 상위 매핑에 따라 역추적하기만 하면 됩니다.

graph = {
        '1': ['2', '3', '4'],
        '2': ['5', '6'],
        '5': ['9', '10'],
        '4': ['7', '8'],
        '7': ['11', '12']
        }

def backtrace(parent, start, end):
    path = [end]
    while path[-1] != start:
        path.append(parent[path[-1]])
    path.reverse()
    return path
        

def bfs(graph, start, end):
    parent = {}
    queue = []
    queue.append(start)
    while queue:
        node = queue.pop(0)
        if node == end:
            return backtrace(parent, start, end)
        for adjacent in graph.get(node, []):
            if node not in queue :
                parent[adjacent] = node # <<<<< record its parent 
                queue.append(adjacent)

print bfs(graph, '1', '11')

위의 코드는 주기가 없다는 가정에 근거합니다.

아주 쉬운 코드.노드를 검색할 때마다 경로를 계속 추가합니다.

graph = {
         'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])
         }
def retunShortestPath(graph, start, end):

    queue = [(start,[start])]
    visited = set()

    while queue:
        vertex, path = queue.pop(0)
        visited.add(vertex)
        for node in graph[vertex]:
            if node == end:
                return path + [end]
            else:
                if node not in visited:
                    visited.add(node)
                    queue.append((node, path + [node]))

저는 Qiao의 첫 번째 대답이 매우 좋았습니다!여기서 유일하게 누락된 것은 꼭짓점을 방문한 것으로 표시하는 것입니다.

왜 우리가 그것을 해야 합니까?
노드 11에서 연결된 노드 13번이 있다고 가정해 보겠습니다.이제 우리의 목표는 노드 13을 찾는 것입니다.
약간의 실행 후 대기열은 다음과 같습니다.

[[1, 2, 6], [1, 3, 10], [1, 4, 7], [1, 4, 8], [1, 2, 5, 9], [1, 2, 5, 10]]

끝에 노드 번호 10이 있는 두 개의 경로가 있습니다.
즉, 노드 번호 10의 경로가 두 번 확인됩니다.이 경우 노드 번호 10에는 아이가 없기 때문에 그렇게 나쁘지 않아 보입니다.하지만 정말 나쁠 수 있습니다(여기서도 우리는 이유 없이 그 노드를 두 번 확인할 것입니다...).)
노드 번호 13이 해당 경로에 없으므로 마지막에 노드 번호 10이 있는 두 번째 경로에 도달하기 전에 프로그램이 반환되지 않습니다.그리고 우리는 그것을 다시 확인할 것입니다.

우리가 놓치고 있는 것은 방문한 노드를 표시하고 다시 확인하지 않는 세트입니다.
다음은 수정 후 qiao의 코드입니다.

graph = {
    1: [2, 3, 4],
    2: [5, 6],
    3: [10],
    4: [7, 8],
    5: [9, 10],
    7: [11, 12],
    11: [13]
}


def bfs(graph_to_search, start, end):
    queue = [[start]]
    visited = set()

    while queue:
        # Gets the first path in the queue
        path = queue.pop(0)

        # Gets the last node in the path
        vertex = path[-1]

        # Checks if we got to the end
        if vertex == end:
            return path
        # We check if the current node is already in the visited nodes set in order not to recheck it
        elif vertex not in visited:
            # enumerate all adjacent nodes, construct a new path and push it into the queue
            for current_neighbour in graph_to_search.get(vertex, []):
                new_path = list(path)
                new_path.append(current_neighbour)
                queue.append(new_path)

            # Mark the vertex as visited
            visited.add(vertex)


print bfs(graph, 1, 13)

프로그램의 출력은 다음과 같습니다.

[1, 4, 7, 11, 13]

불필요한 재점검 없이는..

재미로 코드를 작성해 볼까 생각했습니다.

graph = {
        '1': ['2', '3', '4'],
        '2': ['5', '6'],
        '5': ['9', '10'],
        '4': ['7', '8'],
        '7': ['11', '12']
        }

def bfs(graph, forefront, end):
    # assumes no cycles

    next_forefront = [(node, path + ',' + node) for i, path in forefront if i in graph for node in graph[i]]

    for node,path in next_forefront:
        if node==end:
            return path
    else:
        return bfs(graph,next_forefront,end)

print bfs(graph,[('1','1')],'11')

# >>>
# 1, 4, 7, 11

주기를 원하는 경우 다음을 추가할 수 있습니다.

for i, j in for_front: # allow cycles, add this code
    if i in graph:
        del graph[i]

저는 @Qiao 첫 번째 답변과 @Or의 추가를 모두 좋아합니다.조금 덜 처리하기 위해 Or의 답변에 추가하고 싶습니다.

In @Or의 답변은 방문한 노드를 추적하는 것이 좋습니다.프로그램이 현재보다 빨리 종료되도록 할 수도 있습니다.포 루프의 어느 지점에서current_neighbour그것이 되어야 할 것입니다.end가장 짧은 경로가 발견되고 프로그램이 돌아올 수 있습니다.

다음과 같이 방법을 수정하여 for 루프에 주의를 기울이겠습니다.

graph = {
1: [2, 3, 4],
2: [5, 6],
3: [10],
4: [7, 8],
5: [9, 10],
7: [11, 12],
11: [13]
}


    def bfs(graph_to_search, start, end):
        queue = [[start]]
        visited = set()

    while queue:
        # Gets the first path in the queue
        path = queue.pop(0)

        # Gets the last node in the path
        vertex = path[-1]

        # Checks if we got to the end
        if vertex == end:
            return path
        # We check if the current node is already in the visited nodes set in order not to recheck it
        elif vertex not in visited:
            # enumerate all adjacent nodes, construct a new path and push it into the queue
            for current_neighbour in graph_to_search.get(vertex, []):
                new_path = list(path)
                new_path.append(current_neighbour)
                queue.append(new_path)

                #No need to visit other neighbour. Return at once
                if current_neighbour == end
                    return new_path;

            # Mark the vertex as visited
            visited.add(vertex)


print bfs(graph, 1, 13)

출력과 다른 모든 것은 동일합니다.그러나 코드를 처리하는 데 시간이 더 적게 걸립니다.이 기능은 특히 큰 그래프에서 유용합니다.나는 이것이 미래에 누군가에게 도움이 되길 바랍니다.

그래프에 사이클이 포함되어 있으면 이와 같은 것이 더 잘 작동하지 않을까요?

from collections import deque

graph = {
    1: [2, 3, 4],
    2: [5, 6, 3],
    3: [10],
    4: [7, 8],
    5: [9, 10],
    7: [11, 12],
   11: [13]
}


def bfs1(graph_to_search, start, end):
    queue = deque([start])
    visited = {start}
    trace = {}

    while queue:
        # Gets the first path in the queue
        vertex = queue.popleft()
        # Checks if we got to the end
        if vertex == end:
            break

        for neighbour in graph_to_search.get(vertex, []):
            # We check if the current neighbour is already in the visited nodes set in order not to re-add it
            if neighbour not in visited:
            # Mark the vertex as visited
                visited.add(neighbour)
                trace[neighbour] = vertex
                queue.append(neighbour)

path = [end]
while path[-1] != start:
    last_node = path[-1]
    next_node = trace[last_node]
    path.append(next_node)

return path[::-1]

print(bfs1(graph,1, 13))

이렇게 하면 새 노드만 방문하고 주기를 피할 수 있습니다.

Javascript 버전 및 먼저/모든 경로 검색...

PS, 원기둥이 있는 그래프는 잘 작동합니다.

의 깡통convertpython 일이야, ㅠㅠ

function search_path(graph, start, end, exhausted=true, method='bfs') {
    // note. Javascript Set is ordered set...
    const queue = [[start, new Set([start])]]
    const visited = new Set()
    const allpaths = []
    const hashPath = (path) => [...path].join(',') // any path hashing method
    while (queue.length) {
        const [node, path] = queue.shift()
        // visited node and its path instant. do not modify it others place
        visited.add(node)
        visited.add(hashPath(path))
        for (let _node of graph.get(node) || []) {
            // the paths already has the node, loops mean nothing though.
            if (path.has(_node))
                continue;
            // now new path has no repeated nodes.
            let newpath = new Set([...path, _node])
            if (_node == end){
                allpaths.push(newpath)
                if(!exhausted) return allpaths; // found and return 
            }
            else {
                if (!visited.has(_node) || // new node till now
                   // note: search all possible including the longest path
                   visited.has(_node) && !visited.has(hashPath(newpath))
                ) { 
                    if(method == 'bfs')
                       queue.push([_node, newpath])
                    else{
                       queue.unshift([_node, newpath])
                    }
                }
            }
        }
    }
    return allpaths
}

이렇게 출력합니다.

[
    [ 'A', 'C' ],
    [ 'A', 'E', 'C'],
    [ 'A', 'E', 'F', 'C' ] // including F in `A -> C`
]

언급URL : https://stackoverflow.com/questions/8922060/how-to-trace-the-path-in-a-breadth-first-search