알고리즘 학습

7장. 그래프: 연결만!

이 작품은 AI를 사용하여 번역되었습니다. 여러분의 피드백과 의견을 환영합니다: [e-mail]

이 장에서는 학습 내용을 살펴봅니다:

• 스택 추상 데이터 유형입니다.

• 이 책에 포함된 최종 데이터 유형인 인덱싱된 최소 우선순위 큐 데이터 유형입니다.

• 노드와 가장자리를 사용하여 그래프를 모델링하는 방법. 방향 그래프에서 가장자리에는 방향이 있습니다. 가중 그래프에서 가장자리에는 연결된 숫자 값이 있습니다.

• 깊이 우선 검색이 스택을 사용하여 그래프에서 검색을 구성하는 방법.

• 범위 우선 검색이 대기열을 사용해 그래프를 검색하는 방법. 소스 노드와 대상 노드 사이에 경로가 존재하는 경우, 범위 우선 검색은 존재하는 최단 경로를 반환합니다.

• 방향성 그래프에 사이클(특정 노드에서 시작하여 특정 노드로 끝나는 일련의 가장자리)이 포함되어 있는지 감지하는 방법.

• 방향성 그래프에서 토폴로지 정렬을 사용하여 방향성 그래프의 모든 종속성과 호환되는 노드의 선형 순서를 생성하는 방법을 알아보세요.

• 한 노드에서 다른 모든 노드까지 가중치 그래프에서 최단 누적 경로를 결정하는 방법.

• 두 노드 사이의 가중치 그래프에서 최단 누적 경로를 구하는 방법.

유용한 정보를 효율적으로 저장하는 그래프

지금까지 데이터 저장 및 처리와 관련된 정보 시스템의 일반적인 문제를 해결하기 위한 알고리즘에 대해 살펴봤습니다. 이러한 알고리즘은 이러한 문제를 제대로 모델링할 수만 있다면 무수히 많은 실제 문제를 해결할 수 있습니다. 여기서는 그래프를 사용하여 이러한 문제 세 가지를 해결해 보겠습니다:

• 미로는 다른 방으로 통하는 출입구가 있는 방으로 구성되어 있습니다. 입구에서 출구까지 최단 경로를 찾으세요.

• 프로젝트는 작업 모음으로 정의되지만 일부 작업은 시작하기 전에 다른 작업을 완료해야 하는 경우도 있습니다. 프로젝트를 완료하기 위해 작업을 수행할 수 있는 순서를 설명하는 선형 일정을 짜세요.

• 지도에는 마일 단위의 길이를 포함한 고속도로 구간 모음이 포함되어 있습니다. 지도에서 두 위치 사이의 최단 이동 거리를 찾습니다.

이러한 각 문제는 수세기 동안 수학자들이 연구해 온 기본 개념인 그래프를 사용하여 효과적으로 모델링할 수 있습니다. 데이터 간의 관계를 모델링하는 것은 데이터 값 자체만큼이나 중요한 경우가 많습니다. 그래프는 정보를 에지로 연결된 노드로 모델링합니다. 그림 7-1에서 볼 수 있듯이 그래프는 다양한 애플리케이션 영역의 개념을 모델링할 수 있으며, 노드 u와 v 사이의 관계를 나타내기 위해 임의의 수의 에지(e =(u, v))가 존재할 수 있습니다. 방향이 없는 그래프는 프로판 분자의 탄소 원자와 수소 원자 사이의 구조적 관계를 모델링할 수 있습니다. 모바일 앱은 일방통행 도로의 방향을 방향성 그래프로 표현하여 뉴욕시에서 운전 경로를 제공할 수 있습니다. 운전자용 도로 지도는 뉴잉글랜드 주 수도 사이의 주행 거리를 가중치 그래프로 나타낼 수 있습니다. 약간의 ...