데이터 구조의 그래프: 유형, 저장 및 탐색

데이터 구조는 데이터에 쉽게 액세스하고 효과적으로 사용할 수 있도록 데이터 과학에서 데이터를 구성하는 효율적인 방법입니다. 많은 유형의 데이터베이스가 있지만 이 기사에서는 그래프가 데이터 관리에서 중요한 역할을 하는 이유에 대해 설명합니다.

스포일러 경고: 매일 데이터 구조의 그래프 를 사용하여 사무실로 가는 최적의 경로를 가져오고 점심, 영화에 대한 제안을 받고 다음 비행 경로를 최적화합니다. 흥미롭게 들린다! 그래프의 속성과 응용 프로그램에 대해 알아보겠습니다.

먼저 Graph가 무엇인지 볼까요? 노드(또는 꼭짓점)와 에지(또는 경로)로 구성된 비선형 구조의 데이터 표현입니다.

데이터 구조 에서 그래프 는 서로 연결된 여러 그룹의 에지(경로)와 꼭짓점(노드) 사이에 저장된 데이터로 구성된 데이터 구조라고 할 수 있습니다. 그래프 데이터 구조(N, E)는 노드와 에지의 집합으로 구성됩니다. 노드와 정점 모두 유한해야 합니다.

위의 그래프 표현에서 노드 집합은 N={0,1,2,3,4,5,6}이고 간선 집합은 다음과 같습니다.

G={01,12,23,34,45,05,03}

이제 그래프의 종류에 대해 알아보겠습니다.

읽기: 상위 10가지 데이터 시각화 기법

그래프의 종류

1. 가중 그래프

모서리 또는 경로에 값이 ​​있는 그래프. 에지와 관련하여 표시되는 모든 값을 가중치라고 합니다. Edge 값은 무게/비용/길이를 나타낼 수 있습니다.

값 또는 가중치는 다음을 나타낼 수도 있습니다.

• 두 지점 사이의 거리 - 예: 사무실까지의 최단 경로를 찾으려면 사무실 네트워크에서 두 워크스테이션 사이의 거리입니다.
• 네트워크 또는 대역폭에서 데이터 패킷의 속도입니다.

2. 가중치가 없는 그래프

가장자리와 관련된 값이나 가중치가 없는 경우. 기본적으로 연결된 값이 없는 한 모든 그래프에는 가중치가 적용되지 않습니다.

3. 무방향 그래프

개체 집합이 연결되어 있고 모든 가장자리가 양방향입니다. 아래 이미지는 무방향 그래프를 보여줍니다.

친구로 연결한 후 두 명의 Facebook 사용자가 연결되는 것과 같습니다. 두 사용자 모두 사진을 참조하고 공유하고 서로 의견을 나눌 수 있습니다.

4. 방향 그래프

객체 집합(N, E)이 연결되고 모든 모서리가 한 노드에서 다른 노드로 향하는 이중 그래프라고도 합니다. 위의 이미지는 방향성 그래프를 보여줍니다.

체크아웃: 복제할 수 있는 데이터 시각화 프로젝트

그래프 저장

모든 보관 방법에는 장단점이 있으며 복잡성에 따라 올바른 보관 방법이 선택됩니다. 그래프를 저장하는 데 가장 일반적으로 사용되는 두 가지 데이터 구조는 다음과 같습니다.

1. 인접 목록

여기서 노드는 1차원 배열의 인덱스로 저장되고 에지는 목록으로 저장됩니다.

2. 인접 행렬

여기에서 노드는 2차원 배열의 인덱스로 표시되고 그 뒤에 인접한 행렬의 0이 아닌 값으로 표시되는 가장자리가 표시됩니다.

행과 열 모두 노드를 보여줍니다. 전체 행렬은 true 또는 false를 나타내는 "0" 또는 "1"로 채워집니다. 0은 경로가 없음을 나타내고 1은 경로를 나타냅니다.

그래프 순회

그래프 순회는 그래프에서 노드를 검색하는 데 사용되는 방법입니다. 그래프 순회는 노드 배열에 사용되는 순서를 결정하는 데 사용됩니다. 또한 루프를 만들지 않고 가장자리를 검색합니다. 즉, 루프를 만들지 않고도 모든 노드와 가장자리를 검색할 수 있습니다.

두 가지 그래프 탐색 구조가 있습니다.

1. DFS(Depth First Search): 심층 검색 방법

DFS 검색은 첫 번째 노드에서 시작하여 대상 노드를 찾을 때까지 탐색하면서 점점 더 깊어집니다. 대상 키를 찾지 못한 경우 탐색 경로를 초기 탐색 중 탐색이 중지된 경로로 변경하고 해당 분기에 대해 동일한 절차를 반복합니다.

이 검색 결과에서 스패닝 트리가 생성됩니다. 이 트리 방법에는 루프가 없습니다. 스택 데이터 구조의 총 노드 수는 DFS 탐색을 구현하는 데 사용됩니다.

DFS 검색을 구현하기 위해 따라야 하는 단계:

1단계 – 총 노드 수에 따라 스택 크기를 정의해야 합니다.

2단계 – 횡단을 위한 초기 노드를 선택합니다. 해당 노드를 방문하여 스택으로 푸시해야 합니다.

3단계 – 이제 이전에 방문하지 않은 인접 노드를 방문하여 스택에 푸시합니다.

4단계 – 방문하지 않은 인접 노드가 없을 때까지 3단계를 반복합니다.

5단계 – 방문할 다른 노드가 없을 때 역추적과 하나의 노드를 사용합니다.

6단계 – 3,4,5단계를 반복하여 스택을 비웁니다.

7단계 – 스택이 비어 있을 때 사용하지 않는 가장자리를 제거하여 최종 스패닝 트리가 형성됩니다.

DFS의 응용 프로그램은 다음과 같습니다.

• 단 하나의 솔루션으로 퍼즐을 푸십시오.
• 그래프가 이분법인지 테스트합니다.
• 작업 및 기타 여러 일정을 예약하기 위한 토폴로지 정렬.

2. BFS(Breadth-First Search): 검색은 큐잉 방식을 사용하여 구현됩니다.

Breadth-First Search는 그래프를 광범위하게 탐색하고 경로의 끝을 만난 후 대기열을 기반으로 한 노드에서 다른 노드로 점프하는 데 활용합니다.

BFS 검색을 구현하기 위해 따라야 할 단계,

1단계 – 노드 수에 따라 대기열이 정의됩니다.

2단계 – 순회 노드에서 시작합니다. 해당 노드를 방문하여 대기열에 추가하십시오.

3단계 – 이제 Queue 앞에 있는 방문하지 않은 인접 노드를 확인하고 시작이 아닌 Queue에 추가합니다.

4단계 – 이제 방문해야 하는 가장자리가 없고 대기열에 없는 노드 삭제를 시작합니다.

5단계 – 4단계와 5단계를 반복하여 대기열을 비웁니다.

6단계 – 사용하지 않는 가장자리를 제거하고 대기열이 비어 있는 후에만 스패닝 트리를 형성합니다.

BFS의 응용 프로그램은 다음과 같습니다.

• P2P 네트워크 - Bittorrent와 마찬가지로 모든 인접 노드를 찾는 데 사용됩니다.
• 검색 엔진의 크롤러.
• 소셜 네트워킹 웹사이트 등.

데이터 구조에서 그래프의 실제 적용

그래프는 네트워크 표현(도로, 광섬유 매핑, 회로 기판 설계 등)과 같은 많은 일상적인 응용 프로그램에서 사용됩니다. 예: Facebook 데이터 네트워크에서 노드는 사용자, 사용자의 사진 또는 댓글을 나타내고 가장자리는 사진, 사진에 대한 댓글을 나타냅니다.

데이터 구조의 그래프 에는 광범위한 응용 프로그램이 있습니다. 주목할만한 것은 다음과 같습니다.

• 소셜 그래프 API – Facebook 소셜 미디어 플랫폼 안팎에서 데이터가 전달되는 기본 방법입니다. 프로그래밍 방식으로 데이터를 쿼리하고, 사진과 비디오를 업로드하고, 새로운 스토리를 만들고, 기타 여러 작업을 수행하는 데 사용되는 HTTP 기반 API입니다. 노드, 에지 및 필드로 구성됩니다. 쿼리하려면 특정 개체 노드가 사용됩니다. 단일 객체의 대상이 되는 객체 그룹에 대한 에지 및 필드는 그룹 내 각 객체에 대한 데이터를 가져오는 데 사용됩니다.
• Yelp의 GraphQL API – Yelp 플랫폼에서 특정 데이터를 가져오는 데 사용되는 추천 엔진입니다. 여기에서 주문은 가장자리를 찾는 데 사용되며 그 후에 정확한 결과를 가져오기 위해 특정 노드가 쿼리됩니다. 이렇게 하면 검색 프로세스가 빨라집니다.

Yelp 플랫폼에서 노드는 id, name, is_closed 및 기타 여러 그래프 속성을 포함하는 비즈니스를 나타냅니다.

• 경로 최적화 알고리즘 - 속도, 안전, 연료 등의 기준에 맞는 최상의 연결을 찾는 데 사용됩니다. 이 알고리즘에는 BFS가 사용됩니다. 가장 좋은 예는 Google Maps Platform(Maps, Routes API)입니다.
• Flight Networks - 비행 네트워크에서 그래프 데이터 구조 에 맞는 최적화된 경로를 찾는 데 사용됩니다 . 이는 또한 모델을 지원하고 공항 절차를 효율적으로 최적화합니다.

읽어보기: 데이터 시각화의 이점

결론

이 기사에서는 먼저 데이터 구조에서 그래프와 그래프 의 정의에 대해 논의한 다음 속성이 있는 그래프 유형에 대해 배웠습니다. 나중에 우리는 그래프 저장에 일반적으로 사용되는 방법에 대해 배웠고 그래프에서 사용되는 중요한 주제 검색 방법인 그래프 순회에 대해 배웠습니다. 마지막으로 그래프 데이터 구조의 실제 적용에 대해 논의했습니다.

이 기사 는 데이터 구조의 그래프에 대한 통찰력을 제공했습니다 . 이에 대한 지식은 그래프 데이터베이스, 검색 알고리즘 구현, 프로그래밍 등에 대한 기본적인 이해에 매우 중요합니다. 업계 전문가에게 배워야 합니다.

upGrad와 함께 코스를 선택하는 이유는 무엇 입니까?

upGrad에서 호스팅되는 IIIT Bangalore가 제공하는 데이터 과학의 Executive PG 프로그램 을 선택하는 것이 좋습니다 . 여기에서 코스 강사와 1-1로 쿼리를 얻을 수 있기 때문입니다. 이론 학습에 중점을 둘 뿐만 아니라 학습자가 실제 프로젝트에 직면할 준비를 하고 데이터 과학 분야에서 고임금 직업을 얻는 데 도움이 되는 인도 최초의 NASSCOM 인증서를 제공하는 데 필수적인 실용적인 기반 지식을 중요시합니다.

작품 인용

수학/CS학과 – 홈 , www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/11-Graph/data-stru.html.

"수학 통찰력." 방향성 그래프 정의 – 수학 통찰력 , mathinsight.org/definition/directed_graph.

싱, 암리팔. "그래프 데이터 구조." Medium , Medium, 2020년 3월 29일, medium.com/@singhamritpal49/graph-data-structure-49427c81b3b3.

독주. "당신이 알아야 할 그래프 데이터 구조의 실생활 응용." 그래프 데이터 및 GraphQL API Development-Leap Graph , jumpgraph.com/graph-data-structures-applications.