data-structures
그래프 순회

소개

깊이 우선 검색

그래프의 Depth First Traversal (또는 Search)은 트리의 Depth First Traversal과 유사합니다. 여기서 유일한 잡목은 나무와는 달리 그래프에 사이클이 포함될 수 있기 때문에 동일한 노드로 다시 올 수 있습니다. 노드를 두 번 이상 처리하지 않으려면 부울 방문 배열을 사용합니다.

아래의 알고리즘은 DFS를 사용한 그래프 탐색을위한 단계를 제공합니다.

알고리즘 DFS (v);

입력 : 그래프의 정점 v

출력 : 가장자리를 "발견"가장자리 및 "뒤"로 표시

for each edge e incident on v do

    if edge e is unexplored then

    let w be the other endpoint of e
    if vertex w is unexplored then
        label e as a discovery edge
        recursively call DFS(w)
    else
    label e as a backedge

폭스 퍼스트 검색

알고리즘 BFS (G)

입력 그래프 G

G 의 꼭지점의 가장자리와 구획의 출력 라벨링

    for all u ∈ G.vertices()
        setLabel(u, UNEXPLORED)
    for all e ∈ G.edges()
    setLabel
    (e, UNEXPLORED)
    for all v ∈ G.vertices()
        if getLabel(v) = UNEXPLORED
            BFS(G, v)