사전 범위 우선 검색

그래프 및 트리쉬 알고리즘
α–β A* B* 역추적 빔 벨먼-포드 베스트 퍼스트 양방향 보르슈프카 분기 & 바운드 BFS 대영 박물관 D* DFS 디크스트라 에드먼즈 플로이드-워셜 프린지 검색 힐 클라이밍 IDA* 반복적 심화 존슨 점프 포인트 크루스칼 사전 BFS LPA* 프라이머리 SMA*
목록
그래프 알고리즘 검색 알고리즘 그래프 알고리즘 목록
관련 항목
동적 프로그래밍 그래프 통과 나무횡단 검색 게임 그래프 컬러링
v t

컴퓨터 과학에서 어휘 범위 우선 검색 또는 Lex-BFS는 그래프의 정점을 정렬하기 위한 선형 시간 알고리즘이다.알고리즘은 폭 우선 검색과 다르지만 폭 우선 검색과 일치하는 주문을 생산한다.

사전 편찬 폭 우선 검색 알고리즘은 파티션 미세화 아이디어를 기반으로 하며, 도널드 J. 로즈, 로버트 E가 처음 개발했다. 타르잔, 그리고 조지 S.루케르(1976년).이 주제에 대한 보다 자세한 조사는 코르네일(2004)이 발표한다.코드 그래프의 인식과 거리 계통 그래프의 최적 색상을 포함한 다른 그래프 알고리즘에서 서브루틴으로 사용되어 왔다.

배경

폭 우선 검색 알고리즘은 일반적으로 다음 프로세스에 의해 정의된다.

• 그래프의 시작 정점을 큐의 유일한 요소로 하여 그래프 정점의 큐를 초기화하십시오.
• 대기열이 비어 있지 않은 동안 큐에서 꼭지점 v를 제거하고(대기열에서) 이전 단계에서 아직 추가되지 않은 v에서 에지로 도달할 수 있는 다른 모든 정점을 대기열에 추가(대기열)하십시오.

그러나 큐의 디큐 연산에 의해 생성된 정점처럼 각 단계에서 반드시 선택해야 하는 정점을 정의하기보다는, 이러한 정점의 속성에 의해 선언적으로 정점의 동일한 순서를 정의할 수 있다.즉, 표준 범위 우선 검색은 이 규칙을 반복적으로 적용한 결과일 뿐이다.

• 각 단계에서 정점 v를 반복적으로 출력하고, 출력 초기에 이전 버전(v에 에지가 있는 정점)이 있는 정점 v를 선택한다.

어떤 경우에는 전임자의 출력 위치에 의한 정점의 순서는 동점을 가질 수 있다. 즉, 다른 두 정점은 동일한 초기 정점을 갖는다.이 경우, 그 두 꼭지점이 선택되는 순서는 임의적일 수 있다.사전 편찬 범위 우선 검색의 산출물은 그러한 관계를 끊기 위한 일관된 규칙을 갖는다는 점에서 표준 범위 우선 검색과 다르다.사전 편찬 범위 우선 검색에서 출력 순서는 규칙에 의해 생성되는 순서다.

• 각 단계에서 이미 선택되지 않은 정점 v를 선택하고 사전순으로 가능한 한 작은 전체 사전 출력 이전 버전의 정점 v를 선택한 정점 v를 반복적으로 출력하십시오.

따라서 두 꼭지점 v와 w가 다른 어떤 언초젠 꼭지점보다 먼저 동일한 초기 전위점을 가질 때 표준 너비 우선 검색 알고리즘이 임의로 이들을 명령할 것이다.대신, 이 경우, LexBFS 알고리즘은 두 번째로 어린 이전 모델의 출력 순서에 따라 v와 w 중 하나를 선택할 것이다.그 중 한 명만 이미 생산한 차상위 전임자가 있다면 그 전임자가 선택된다.v와 w 모두 같은 2위 전임자가 있다면 3위 전임자를 고려하는 등 동점이 깨진다.

이 규칙에 따라 정점을 비교하여 이 규칙을 직접 적용하면 알고리즘이 비효율적일 수 있다.대신 사전 편찬 범위 우선 검색은 표준 범위 우선 검색이 대기열 데이터 구조를 사용하여 주문을 효율적으로 생성하는 것처럼 동일한 주문을 보다 효율적으로 생성하기 위해 설정된 분할 데이터 구조를 사용한다.

알고리즘.

사전 편찬 폭 우선 검색 알고리즘은 표준 폭 우선 검색의 정점 대기열을 정점 집합 순서의 순서에 따라 대체한다.시퀀스의 세트는 나머지 정점의 파티션을 형성한다.각 단계에서 시퀀스에 포함된 첫 번째 세트의 꼭지점 v는 해당 세트에서 제거되며, 이 제거로 인해 세트가 비어 있으면 세트에서 시퀀스가 제거된다.그런 다음 시퀀스에 포함된 각 세트는 v의 이웃과 v의 이웃인 두 개의 하위 집합으로 대체된다.이웃집합은 이웃집합보다 더 빨리 배열된다.유사코드에서는 알고리즘을 다음과 같이 표현할 수 있다.

• 모든 정점을 포함하는 단일 집합을 포함하려면 집합의 순서 sequence을 초기화한다.
• 비워 둘 정점의 출력 시퀀스를 초기화하십시오.
• σ이 비어 있지 않은 경우:
  • σ의 첫 번째 세트에서 꼭지점 v 찾기 및 제거
  • 현재 in의 첫 번째 세트가 비어 있으면 σ에서 제거하십시오.
  • 출력 시퀀스의 끝에 v를 추가하십시오.
  • 각 에지에 대해 w가 여전히 σ의 집합 S에 속하도록 v-w:
    • v를 처리하는 동안 w가 포함된 세트 S가 아직 교체되지 않은 경우, 빈 교체 세트 T를 새로 생성하여 시퀀스에서 S보다 앞에 배치하고, 그렇지 않으면 T를 S보다 먼저 설정하십시오.
    • w를 S에서 T로 이동하고, S가 비어 있는 경우 σ에서 S를 제거한다.

각 꼭지점은 한 번 처리되며, 각 가장자리는 두 끝점이 처리될 때만 검사되며, (항상 시간 내에 한 세트에서 다른 세트로 항목을 이동할 수 있는 σ의 세트에 대한 적절한 표현을 사용하여) 내부 루프의 각 반복은 일정한 시간만 소요된다.따라서 폭 우선 검색, 깊이 첫 번째 검색과 같은 단순한 그래프 검색 알고리즘처럼 이 알고리즘은 선형 시간이 걸린다.

알고리즘을 사전 범위 우선 검색이라고 하는데, 그 순서가 범위 우선 검색에 의해서도 생성될 수 있는 순서이기 때문이다. 그리고 순서가 그래프의 인접 행렬의 행과 열을 색인화하는 데 사용된다면 알고리즘은 행과 열을 사전순으로 정렬하기 때문이다.

적용들

화음 그래프

그래프 G는 그 정점이 완벽한 제거 순서를 가진 경우, 순서에서 나중에 발생하는 정점 v에 대해 이웃들이 집단으로 형성되는 순서인 화음으로 정의된다.화음 그래프에서 사전 순서의 역순은 항상 완벽한 제거 순서다.따라서 다음과 같은 알고리즘을 통해 선형 시간에 그래프가 화음인지 여부를 검정할 수 있다.

• 사전 편찬 범위 우선 검색을 사용하여 G의 사전 편찬 순서 찾기
• 각 꼭지점 v:
  • 가능한 한 순서에서 v에 가까운 v 이전에 발생한 v의 인접자가 w가 되도록 한다.
    • (이러한 w가 없는 경우 다음 꼭지점 v로 계속 진행)
  • v(w 자체 제외)의 이전 인접 집합이 w의 이전 인접 집합 집합의 하위 집합이 아닌 경우 그래프는 화음이 아니다.
• 그래프가 화음이 아니라는 것을 표시하지 않고 루프가 종료되면 화음이 된다.

이 애플리케이션은 로즈, 타르잔 & 루케르(1976)가 사전 편찬 폭 첫 번째 검색 알고리즘을 개발하게 된 최초의 동기였다.^[1]

그래프 컬러링

G 그래프는 G의 유도 하위 그래프의 경우 유도 시퀀스 순서에서 정점을 색칠하는 탐욕스러운 색소 알고리즘이 최적의 색소를 생성하도록 보장되는 속성을 가진 정점 순서가 있는 경우 완벽하게 정렬할 수 있다고 한다.

화음 그래프의 경우, 완벽한 제거 순서는 완벽한 순서다: 정점에 사용되는 색의 수는 그것과 그 이전의 이웃에 의해 형성된 클릭의 크기이므로, 사용되는 색의 최대 수는 그래프에서 가장 큰 클릭의 크기와 같으며, 어떤 컬러도 더 적은 색상을 사용할 수 없다.코드 그래프의 유도 하위 그래프는 코드이고 완벽한 제거 순서의 유도 하위 그래프는 서브그래프의 완벽한 제거 순서가므로 코드 그래프를 완벽하게 정렬할 수 있으며 사전 범위 우선 검색을 사용하여 최적의 색상을 지정할 수 있다.

그 같은 속성의 그래프를 더 큰 클래스,distance-hereditary 그래프:distance-hereditary 그래프 완벽하게 완벽한 순서는 사전 편찬 상의 순서의 반대에 의해 주어지므로 사전 편찬 상의breadth-first 검색 탐욕 채색 알고리즘과 함께 최적 선형 시간에 그들에 색을 사용할 수 있는 명령할 수 있는 것은 사실이다.[2]

기타 응용 프로그램

브레츠허 외 (2008) 입력 그래프의 보완 그래프를 사용하여 추가 동점을 깨는 사전 편찬 범위 우선 검색의 확장을 설명한다.그들이 보여주듯이, 이것은 선형적인 시간에 cograph를 인식하는데 사용될 수 있다.하빕 외 (2000) 비교가능성 그래프와 구간 그래프의 인식을 포함하여 사전 편찬 범위 우선 검색의 추가 적용을 설명한다.

렉스BFS 주문

그래프의 정점을 열거하면 이 그래프에 대한 LexBFS의 적용 가능한 출력일 경우 LexBFS 순서가 된다고 한다.

$G{\displaystyle }$=${\displaystyle }$( ${\displaystyle V}$, ${\displaystyle E}$) ${\displaystyle G=(V,E)}$은(는) $정점$이 n$${\$displaystyle$ n$}$인 그래프가 되도록$$ 한다.$N{\displaystyle (v}$) ${\displaystyle N(v)}$이(가) v ${\displaystyle v}$의 인접 집합임을 상기하십시오.$$$\sigma {\displaystyle }$=${\displaystyle }$( v ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle }$… ,${\displaystyle v_{}}$ n${\displaystyle {}_{}}$) ${\displaysty \sigma =(v_{1},\dots,v_{n}}})$는 V$${\$displaystystystylean V}$의 정점의 열거입니다$.$나는 < 모두 1≤. 만약, j<>v와 나는 N(vkm그리고 4.9초 만)∖ N(vj){\displaystyle v_{나는}\in N(v_{k})\setminus N(v_{j})}∈ k≤ n{\displaystyle 1\leq i<, j<,k\leq n}열거형 σ{\displaystyle \sigma}은 LexBFS( 넣어 소스 v1{\displaystyle v_{1}})를 주문하고, m개체, 나는{\display 존재한다.스타일 m<, 나는}이해당 v m${\displaystyle }$that N (${\displaystyle v_{}}$ j${\displaystyle {}_{}}$) ${\displaystyle \setminus }$ ${\displaystyle N}$(${\displaystyle v_{}}$ ${\displaystyle {}_{}{}_{}}$) ${\displaystyle v_{m}\in N(v_{j})\setminus N$$v_{k})$ .

메모들

참조

• Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X.
• Bretscher, Anna; Corneil, Derek; Habib, Michel; Paul, Christophe (2008), "A simple linear time LexBFS cograph recognition algorithm", SIAM Journal on Discrete Mathematics, 22 (4): 1277–1296, CiteSeerX 10.1.1.188.5016, doi:10.1137/060664690.
• Corneil, Derek G. (2004), "Lexicographic breadth first search – a survey", Graph-Theoretic Methods in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers, Lecture Notes in Computer Science, vol. 3353, Springer-Verlag, pp. 1–19, doi:10.1007/978-3-540-30559-0_1.
• Habib, Michel; McConnell, Ross; Paul, Christophe; Viennot, Laurent (2000), "Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing", Theoretical Computer Science, 234 (1–2): 59–84, doi:10.1016/S0304-3975(97)00241-7.
• Rose, D. J.; Tarjan, R. E.; Lueker, G. S. (1976), "Algorithmic aspects of vertex elimination on graphs", SIAM Journal on Computing, 5 (2): 266–283, doi:10.1137/0205021.