맨위로가기

그래프 순회

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

그래프 순회는 그래프의 모든 정점을 체계적으로 방문하는 알고리즘이다. 트리 순회와 달리 그래프는 정점을 중복하여 방문할 수 있으며, 밀집 그래프일수록 중복 방문 가능성이 높아 계산 시간이 증가한다. 효율적인 그래프 순회를 위해 이미 탐색한 정점을 기억하여 중복 방문을 최소화한다. 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)은 대표적인 그래프 순회 알고리즘으로, DFS는 스택을, BFS는 큐를 사용하여 그래프를 탐색한다. DFS와 BFS는 연결 요소 찾기, 최단 경로 탐색, 이분 그래프 판별 등 다양한 문제 해결에 응용된다. 그래프 탐색은 그래프 순회의 변형으로, 온라인 알고리즘 문제로 간주되며, '보편적 순회 시퀀스'는 정점의 수가 정해진 모든 정규 그래프를 순회하는 명령어 시퀀스이다.

더 읽어볼만한 페이지

  • 그래프 알고리즘 - 페이지랭크
    페이지랭크는 래리 페이지와 세르게이 브린이 개발한 알고리즘으로, 하이퍼링크로 연결된 문서 집합에서 웹 페이지의 상대적 중요도를 측정하며, 링크를 투표로 간주하여 페이지 순위를 재귀적으로 결정하고, 구글 검색 엔진의 초기 핵심 알고리즘으로 활용되었으며, 다양한 분야에서 활용된다.
  • 그래프 알고리즘 - 너비 우선 탐색
    너비 우선 탐색은 그래프 탐색 알고리즘으로, 큐 자료구조를 사용하여 시작 노드에서 인접한 노드들을 우선적으로 탐색하며, 가중치가 없는 그래프에서 최단 경로를 찾는 데 유용하고 다양한 분야에 활용된다.
  • 그래프 이론 - 다이어그램
    다이어그램은 2차원 기하학적 기호를 사용하여 정보를 시각적으로 표현하는 기술로, 과학, 공학, IT, 비즈니스 등 다양한 분야에서 활용되며 정보를 간략하게 나타내고 시각적 사고를 돕는다.
  • 그래프 이론 - 쾨니히스베르크의 다리 문제
    쾨니히스베르크의 다리 문제는 프레겔 강에 놓인 7개의 다리를 한 번씩만 건너 출발점으로 되돌아올 수 있는지 묻는 문제로, 오일러에 의해 그래프 이론적으로 분석되어 해결되었으며 그래프 이론의 탄생에 기여했다.
그래프 순회

2. 그래프 순회

그래프 순회는 그래프의 모든 정점을 한 번씩 방문하는 과정을 의미한다. 트리 순회와 달리 그래프 순회에서는 중복 방문을 피하기 위해 방문 여부를 기록해야 한다.

2. 1. 중복 방문 방지

트리 순회와 달리, 그래프 순회는 일부 정점을 한 번 이상 방문할 수 있다. 그래프가 밀집될수록 중복 방문이 많아져 계산 시간이 늘어난다. 따라서 이미 탐색한 정점을 기억하여 중복 방문을 줄이는 것이 일반적이다. 최악의 경우 순회가 무한히 반복되는 것을 막을 수 있다.

이를 위해 순회 중 그래프의 각 정점에 "색상" 또는 "방문" 상태를 표시하고, 알고리즘이 각 정점을 방문할 때 이를 확인하고 업데이트한다. 이미 방문한 정점이면 무시하고, 그렇지 않으면 정점을 확인/업데이트하고 현재 경로를 계속 진행한다.

그래프의 특수한 경우, 구조 내에서 다른 정점의 방문을 암시하므로 방문을 명시적으로 기록할 필요가 없을 때도 있다. 트리가 대표적인 예시다. 순회 중 현재 정점의 모든 "조상" 정점은 이미 방문했다고 가정할 수 있다. 깊이 우선 및 너비 우선 그래프 탐색은 구조적으로 결정된 "루트" 정점이 없고, 순회의 방문 상태를 기록하기 위한 자료 구조가 추가되었다는 점을 제외하면 트리 기반 알고리즘과 유사하다.

3. 그래프 순회 알고리즘

그래프 순회에는 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS) 등 다양한 알고리즘이 사용된다. 그래프의 각 정점을 트리 기반 알고리즘(DFS 또는 BFS 등)으로 순회해야 하는 경우, 알고리즘은 그래프의 각 연결 요소에 대해 최소 한 번 이상 호출되어야 한다. 이는 그래프의 모든 정점을 반복하여 검사할 때 아직 방문하지 않은 각 정점에 대해 알고리즘을 수행함으로써 쉽게 수행할 수 있다.

3. 1. 깊이 우선 탐색 (Depth-First Search, DFS)

'''깊이 우선 탐색'''(Depth-First Search, DFS)은 그래프 순회 알고리즘의 한 종류이다. DFS는 형제 정점을 방문하기 전에 자식 정점을 먼저 방문한다. 즉, 그래프의 너비를 탐색하기 전에 특정 경로의 깊이를 끝까지 탐색하는 방식이다.

일반적으로 DFS 알고리즘을 구현할 때는 스택(종종 재귀를 통한 프로그램의 호출 스택)을 사용한다. 알고리즘은 선택된 "루트" 정점에서 시작하여, 현재 정점에서 인접하고 아직 방문하지 않은 정점으로 반복해서 이동한다. 더 이상 탐색할 정점이 없으면, 이전에 방문한 정점을 따라 백트래킹하여 아직 탐색하지 않은 영역으로 연결된 정점을 찾는다. 이러한 과정을 반복하다가 첫 "루트" 정점으로 되돌아오면 탐색이 종료된다.

DFS는 위상 정렬, 평면성 검사 등 다양한 그래프 관련 알고리즘의 기반이 된다.[1]

3. 1. 1. DFS 의사 코드

'''입력''': 그래프 ''G''와 ''G''의 정점 ''v''.

'''출력''': ''v''의 연결 요소 내 간선들을 발견 간선 및 역방향 간선으로 레이블링.

'''절차''' DFS(''G'', ''v'') '''는'''

: ''v''를 탐색됨으로 레이블링

: '''G''에 있는 모든'' 간선 ''e'' '''에 대해'''.incidentEdges(''v'') '''을 수행한다'''

:: '''만약''' 간선 ''e''가 아직 탐색되지 않았다면 '''그때'''

::: ''w'' ← ''G''.adjacentVertex(''v'', ''e'')

::: '''만약''' 정점 ''w''가 아직 탐색되지 않았다면 '''그때'''

:::: ''e''를 발견 간선으로 레이블링

:::: DFS(''G'', ''w'')를 재귀적으로 호출

::: '''그렇지 않으면'''

:::: ''e''를 역방향 간선으로 레이블링

3. 2. 너비 우선 탐색 (Breadth-First Search, BFS)

너비 우선 탐색(BFS)은 그래프를 순회하는 방법 중 하나로, 자식 정점을 방문하기 전에 형제 정점을 먼저 방문한다. 이 과정에서 큐를 사용하며,[1] 한 정점에서 다른 정점까지의 최단 경로를 찾는 데 자주 사용된다.[1]

3. 2. 1. BFS 의사 코드

'''입력''': 그래프 ''G''와 ''G''의 정점 ''v''.

'''출력''': 어떤 조건을 만족하는 ''v''에 가장 가까운 정점, 또는 그런 정점이 없으면 null.

'''절차''' 너비 우선 탐색(''G'', ''v'') '''는'''

  • 큐 ''Q''를 생성
  • ''v''를 ''Q''에 삽입
  • ''v''를 표시
  • '''while''' ''Q''가 비어 있지 않음 '''do'''
  • ''w'' ← ''Q''.dequeue()
  • '''if''' ''w''가 우리가 찾고 있는 것이면 '''then'''
  • '''return''' ''w''
  • '''for all''' 간선 ''e'' in ''G''.adjacentEdges(''w'') '''do'''
  • ''x'' ← ''G''.adjacentVertex(''w'', ''e'')
  • '''if''' ''x''가 표시되지 않았으면 '''then'''
  • ''x''를 표시
  • ''x''를 ''Q''에 삽입
  • '''return''' null

4. 그래프 순회 알고리즘의 응용

너비 우선 탐색은 그래프 이론에서 여러 문제를 해결하는 데 사용된다. 예를 들어 다음과 같다.


  • 하나의 연결 요소 내의 모든 정점을 찾는다.[1]
  • 체니의 알고리즘
  • 커틸–매키 알고리즘
  • 포드-풀커슨 알고리즘을 이용한 유량 네트워크의 최대 유량 문제 계산
  • 이진 트리의 직렬화/역직렬화
  • 미로 생성 알고리즘
  • 홍수 채우기 알고리즘
  • 네트워크 및 관계 분석

4. 1. 최단 경로 찾기

너비 우선 탐색은 그래프 이론에서 두 정점 사이의 최단 경로를 찾는 데 사용될 수 있다.[1]

4. 2. 이분 그래프 판별

너비 우선 탐색은 그래프가 이분 그래프인지 판별하는 데 사용될 수 있다.

4. 3. 기타 응용

그래프 순회는 그래프 이론의 여러 문제를 해결하는 데 응용된다.

  • 체니의 알고리즘
  • 커틸–매키 알고리즘
  • 포드-풀커슨 알고리즘을 이용한 유량 네트워크의 최대 유량 문제 계산
  • 이진 트리의 직렬화/역직렬화
  • 미로 생성 알고리즘
  • 홍수 채우기 알고리즘
  • 네트워크 및 관계 분석

5. 그래프 탐색 (Graph Exploration)

그래프 탐색은 그래프 순회의 변형으로, 온라인 알고리즘 문제로 간주된다. 이는 알고리즘 실행 중에만 그래프 정보가 공개되는 상황에서, 음이 아닌 가중치를 가진 연결 그래프 G|지영어 = (''V'', ''E'')의 모든 ''n''개 정점을 방문하고 시작점으로 돌아오는 최단 경로를 찾는 문제이다. 이 문제는 영업사원이 가면서 그래프를 발견해야 하는 외판원 문제의 특정 버전으로도 이해할 수 있다.

일반적인 그래프에서, 무방향 그래프의 경우, 단위 가중치 무방향 그래프는 경쟁 비율 2 - ''ε'' 로 탐색할 수 있다.[3] 방향 그래프의 경우, 모든 노드를 방문하는 대신 단일 "보물" 노드만 찾아야 하는 경우, 결정적 및 임의 알고리즘 모두에 대해 단위 가중치 방향 그래프에서 경쟁 경계는 ''Θ''(''n''2)이다.

5. 1. 탐욕 알고리즘 (Greedy Algorithm)

온라인 알고리즘 문제인 그래프 탐색은 그래프 순회의 변형으로 볼 수 있다. 일반적인 그래프의 경우, 무방향 및 방향 그래프 모두에 대해 가장 잘 알려진 알고리즘은 간단한 탐욕 알고리즘이다.

  • 무방향 그래프의 경우, 탐욕 경로는 최적 경로보다 최대 O|오영어(ln ''n'')배 더 길다.[1] 임의의 결정적 온라인 알고리즘에 대해 알려진 최상의 하한은 10/3이다.[2]
  • 단위 가중치 무방향 그래프는 경쟁 비율 2 - ''ε''로 탐색할 수 있으며,[3] 이는 이미 올챙이 그래프에 대한 타이트한 경계이다.[4]
  • 방향 그래프의 경우, 탐욕 경로는 최적 경로보다 최대 (''n'' − 1)배 더 길다. 이는 ''n'' − 1의 하한과 일치한다.[5] 각 노드의 좌표를 기하학적으로 임베딩한 것을 알고 있는 임의 알고리즘에도 유사한 경쟁 하한 ''Ω''(''n'')이 적용된다. 모든 노드를 방문하는 대신 단일 "보물" 노드만 찾아야 하는 경우, 결정적 및 임의 알고리즘 모두에 대해 단위 가중치 방향 그래프에서 경쟁 경계는 ''Θ''(''n''2)이다.

6. 보편적 순회 시퀀스 (Universal Traversal Sequences)

'보편적 순회 시퀀스'는 정점의 수가 정해진 모든 정규 그래프와 임의의 시작 정점에 대해 그래프 순회를 수행하는 일련의 명령어이다. Aleliunas et al.은 확률적 증명을 사용하여, n개의 정점을 가진 임의의 정규 그래프에 대해 ''O''(''n''5)에 비례하는 명령어 수를 갖는 보편적 순회 시퀀스가 존재함을 보였다.[6] 시퀀스에 지정된 단계는 절대적인 것이 아니라 현재 노드를 기준으로 한다. 예를 들어, 현재 노드가 ''v''''j''이고 ''v''''j''가 ''d''개의 이웃을 가지고 있다면, 순회 시퀀스는 방문할 다음 노드 ''v''''j''+1을 ''v''''j''의 ''i''번째 이웃으로 지정하며, 여기서 1 ≤ ''i'' ≤ ''d''이다.

참조

[1] 논문 An Analysis of Several Heuristics for the Traveling Salesman Problem
[2] 논문 An improved lower bound for competitive graph exploration 2021-05
[3] 논문 The Online Graph Exploration Problem on Restricted Graphs 2009
[4] 논문 Online graph exploration on a restricted graph class: Optimal solutions for tadpole graphs 2020-11
[5] 논문 Lower and upper competitive bounds for online directed graph exploration https://zenodo.org/r[...] 2016-12
[6] 논문 Random walks, universal traversal sequences, and the complexity of maze problems 1979


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com