그래프 트래버설

Graph traversal
「그래프 검색」은, 여기서 리다이렉트 됩니다.Facebook Graph Search와 혼동하지 마세요.
그래프와 트리
검색 알고리즘
최단 경로
리스트
관련 토픽

컴퓨터 과학에서 그래프 트래버설(그래프 검색이라고도 함)은 그래프에서 각 정점을 방문(검사 및/또는 업데이트)하는 과정을 말합니다.이러한 통과는 정점이 방문하는 순서에 따라 분류됩니다.트리 트래버설은 그래프 트래버설의 특수한 경우입니다.

용장성

트리 트래버설과 달리 그래프 트래버설은 이미 탐색된 정점으로 전환하기 전에 반드시 알 수 있는 것은 아니기 때문에 일부 정점을 두 번 이상 방문해야 할 수 있습니다.그래프가 고밀도가 되면 이 용장성이 더욱 널리 보급되어 계산 시간이 길어집니다.그래프가 희박해지면 그 반대도 성립합니다.

따라서 알고리즘에 의해 어떤 정점이 이미 탐색되었는지 기억해야 하며, 가능한 한 자주 정점을 다시 방문해야 합니다(또는 최악의 경우, 무한정 횡단이 계속되는 것을 방지하기 위해).이는 트래버설 중에 그래프의 각 정점을 "색상" 또는 "방문" 상태와 연관시킴으로써 달성할 수 있습니다.이 상태는 알고리즘이 각 정점을 방문할 때 체크되고 업데이트됩니다.정점이 이미 방문되어 있으면 무시되고 경로가 더 이상 추적되지 않습니다. 그렇지 않으면 알고리즘은 정점을 확인/업데이트하고 현재 경로를 계속 진행합니다.

그래프의 몇 가지 특수한 경우는 구조의 다른 꼭지점의 방문을 의미하므로 트래버설 중에 방문을 명시적으로 기록할 필요가 없다.이것의 중요한 예로는 트리가 있습니다.트라이버설 중에 현재 정점의 모든 "고대" 정점(알고리즘에 따라 다름)이 이미 방문되었다고 가정할 수 있습니다.깊이 우선 및 너비 우선 그래프 검색은 모두 트리 기반 알고리즘의 적응으로, 주로 구조적으로 결정된 "루트" 정점의 부재와 횡단의 방문 상태를 기록하는 데이터 구조의 추가로 구별된다.

그래프 통과 알고리즘

주의: 그래프 내의 각 정점을 트리 기반 알고리즘(DFS 또는 BFS 등)으로 횡단하는 경우 알고리즘은 그래프의 연결된 각 컴포넌트에 대해 적어도 한 번 호출해야 합니다.이는 그래프의 모든 정점을 반복하여 검사 시 아직 방문되지 않은 각 정점에 대해 알고리즘을 수행함으로써 쉽게 달성할 수 있습니다.

랜덤, 깊이 우선 검색 및 폭 우선 검색의 세 가지 그래프 통과 알고리즘에 대한 비언어적 설명입니다.

깊이 우선 검색

주요 기사:깊이 우선 검색

깊이 우선 검색(DFS)은 유한 그래프를 통과하는 알고리즘입니다.DFS는 형제 정점을 방문하기 전에 자식 정점을 방문합니다. 즉, 너비를 조사하기 전에 특정 경로의 깊이를 통과합니다.스택(종종 재귀에 의한 프로그램의 콜스택)은 알고리즘을 실장할 때 사용됩니다.

알고리즘은 선택된 "루트" 정점에서 시작하여 현재 정점에서 인접하고 방문되지 않은 정점으로 반복적으로 전환되며, 현재 위치에서 전환되는 탐색되지 않은 정점을 더 이상 찾을 수 없을 때까지 계속 전환됩니다.그런 다음 알고리즘은 더 미지의 영역에 연결된 정점을 찾을 때까지 이전에 방문한 정점을 따라 역추적합니다.그런 다음 이전과 같이 새로운 경로를 따라 진행되며 막다른 골목에 부딪혔을 때 역추적되며 알고리즘이 첫 번째 단계부터 원래 "루트" 정점을 역추적했을 때만 종료됩니다.

DFS는 토폴로지 정렬 및 평탄도 테스트를 포함한 많은 그래프 관련 알고리즘의 기반입니다.

유사 코드

  • 입력: 그래프 G와 G의 정점 v.
  • 출력: v의 연결된 구성 요소에서 검출 에지 및 후면 가장자리로 표시되는 가장자리 레이블입니다.
절차 DFS(G, v)는 G.incentEdges(v)의 모든 모서리 e에 대해 탐색된 라벨 v이다. 가장자리 e가 탐색되지 않은 경우 w ← G.adjacentVertex(v, e) 정점 w가 탐색되지 않은 경우 검출된 가장자리로 라벨 e를 DFS(G, w)로 재귀적으로 호출한다.

폭 우선 검색

주요 기사: 폭 우선 검색

폭 우선 검색(BFS)은 유한 그래프를 통과하는 또 다른 기술입니다.BFS는 자 정점을 방문하기 전에 형제 정점을 방문하며 검색 프로세스에서 큐가 사용됩니다.이 알고리즘은 한 정점에서 다른 정점으로 가는 최단 경로를 찾기 위해 자주 사용됩니다.

유사 코드

  • 입력: 그래프 G와 G의 정점 v.
  • 출력: 일부 조건을 충족하는 v에 가장 가까운 정점입니다. 이러한 정점이 없는 경우 null입니다.
순서 BFS(G, v)는 Q 마크 v에 큐 Q enqueue v를 작성합니다.Q가 비어 있지 않은 동안 w가 우리가 찾고 있는 경우 w는 Q.deque()를 실행하고, x 마크가 되어 있지 않으면 G.adjacentEdges(w)의 모든 엣지 e에 대해 w를 반환합니다.울

적용들

너비 우선 검색을 사용하여 그래프 이론의 많은 문제를 해결할 수 있습니다. 예를 들어 다음과 같습니다.

그래프 탐색

그래프 탐색의 문제는 그래프 통과의 변형으로 볼 수 있다.이는 온라인상의 문제이며, 즉 그래프에 대한 정보는 알고리즘 실행 시에만 표시됩니다.공통 모델은 다음과 같다: 음이 아닌 에지 가중치를 가진 연결된 그래프 G = (V, E)가 주어지면.알고리즘은 일부 정점에서 시작하여 모든 입사 발신 에지와 이러한 에지의 끝에 있는 정점을 알고 있지만 그 이상은 알 수 없습니다.새 정점이 방문되면 모든 입사 발신 모서리와 끝의 정점이 다시 인식됩니다.목표는 모든 n개의 정점을 방문하고 시작 정점으로 돌아가는 것이지만, 둘러보기의 가중치의 합계는 가능한 한 작아야 합니다.이 문제는 영업 사원이 이동 중에 그래프를 발견해야 하는 출장 세일즈맨 문제의 특정 버전으로 이해할 수도 있습니다.

일반 그래프의 경우 무방향 그래프와 방향 그래프 모두에 대해 가장 잘 알려진 알고리즘은 다음과 같은 단순한 그리디 알고리즘입니다.

  • 무방향의 경우, 탐욕 투어는 최적 [1]투어보다 최대 O(ln n)배 길다.결정론적 온라인 알고리즘에 대해 알려진 최선의 하한은 10/[2]3입니다.
    • 단위 무게 무방향 그래프는 이미 Tadpole [4]그래프에서 엄격한 경계인 2 - [3]µ의 경쟁 비율로 탐색할 수 있다.
  • 유도된 경우, 탐욕 투어는 최적 투어보다 최대 (n - 1)배 길다.이는 n - [5]1의 하한과 일치한다. 유사한 경쟁 하한 δ(n)는 기하학적 임베딩에서 각 노드의 좌표를 아는 랜덤화 알고리즘에도 적용된다.모든 노드를 방문하는 대신 단일 "보물" 노드를 찾아야 하는 경우, 결정론적 알고리즘과 무작위 알고리즘 모두에 대해 단위 무게 지향 그래프에서 경쟁 경계가 δ2(n)이다.

유니버설 트래버설시퀀스

유니버설 트래버설시퀀스는 정점 수가 설정된 정규 그래프와 시작 정점에 대한 그래프 트래버설로 구성된 명령 시퀀스입니다.Aleliunas 등은 n개의 [6]정점이 있는 정규 그래프에 대해 O(n5)에 비례하는 명령 수를 갖는 범용 횡단 시퀀스가 존재한다는 것을 보여주기 위해 확률론적 증거를 사용했다.시퀀스에서 지정된 스텝은 절대 노드가 아닌 현재 노드에 상대적입니다.예를 들어 현재 노드가 v이고jj v에 d개의 네이버가 있는 경우 트래버설시퀀스는 v의j i네이버로서th 방문할 다음 노드 v를j+1 지정합니다(1 1 i i d ） 。

「 」를 참조해 주세요.

레퍼런스

  1. ^ Rosenkrantz, Daniel J.; Stearns, Richard E.; Lewis, II, Philip M. (1977). "An Analysis of Several Heuristics for the Traveling Salesman Problem". SIAM Journal on Computing. 6 (3): 563–581. doi:10.1137/0206041.
  2. ^ Birx, Alexander; Disser, Yann; Hopp, Alexander V.; Karousatou, Christina (May 2021). "An improved lower bound for competitive graph exploration". Theoretical Computer Science. 868: 65–86. arXiv:2002.10958. doi:10.1016/j.tcs.2021.04.003.
  3. ^ Miyazaki, Shuichi; Morimoto, Naoyuki; Okabe, Yasuo (2009). "The Online Graph Exploration Problem on Restricted Graphs". IEICE Transactions on Information and Systems. E92-D (9): 1620–1627. doi:10.1587/transinf.E92.D.1620. hdl:2433/226939.
  4. ^ Brandt, Sebastian; Foerster, Klaus-Tycho; Maurer, Jonathan; Wattenhofer, Roger (November 2020). "Online graph exploration on a restricted graph class: Optimal solutions for tadpole graphs". Theoretical Computer Science. 839: 176–185. arXiv:1903.00581. doi:10.1016/j.tcs.2020.06.007.
  5. ^ Foerster, Klaus-Tycho; Wattenhofer, Roger (December 2016). "Lower and upper competitive bounds for online directed graph exploration". Theoretical Computer Science. 655: 15–29. doi:10.1016/j.tcs.2015.11.017.
  6. ^ Aleliunas, R.; Karp, R.; Lipton, R.; Lovász, L.; Rackoff, C. (1979). "Random walks, universal traversal sequences, and the complexity of maze problems". 20th Annual Symposium on Foundations of Computer Science (SFCS 1979): 218–223. doi:10.1109/SFCS.1979.34.