데이터 구조 및 응용 프로그램의 그래프 유형

소개

그래프는 노드와 에지로 구성된 비선형 구조입니다. 여기에는 한 쌍의 노드를 연결하는 에지가 보유한 유한 또는 무한 노드 세트가 포함될 수 있습니다. 데이터 구조는 모든 코딩 개념의 필수 부분입니다. 따라서 데이터 구조에서 다양한 유형의 그래프를 확실히 파악하면 복잡한 실제 문제를 해결하는 데 도움이 될 수 있습니다.

오늘날의 세상에서 데이터는 힘입니다. 따라서 쉽게 액세스할 수 있도록 데이터를 효율적으로 구성하는 것은 모든 프로그래머에게 필수적입니다. 데이터 구조와 다양한 그래프에 대한 지식은 실제 문제를 대상으로 하고 솔루션을 효과적으로 제공할 수 있는 코딩 기술을 강화합니다.

경쟁자보다 우위를 점하기 위해 데이터 과학을 배우십시오.

데이터 구조에서 일반적으로 사용되는 다양한 유형의 그래프와 실생활에 어떻게 적용되는지 살펴보겠습니다.

데이터 구조의 그래프 유형

데이터 구조는 Python 그래프 데이터 구조 또는 Java 그래프 데이터 구조 와 같은 모든 언어에 대한 실용적인 데이터 저장 표준입니다 . 모든 유형의 그래프를 마스터하는 것은 데이터 구조를 연구하려는 모든 사람에게 우선 순위가 되어야 합니다. 그래프 이론은 실제 응용 프로그램이 많기 때문에 데이터 구조에서 매우 중요합니다.

데이터 구조 의 다양한 유형의 그래프는 다음과 같습니다.

1. 널 그래프

이름에서 알 수 있듯이 null 그래프는 비어 있습니다. 즉, 간선이 없는 그래프입니다. 비어 있는 에지 세트가 있는 그래프의 격리된 정점으로만 구성됩니다.

2. 유한 그래프

그래프에서 에지와 노드의 수가 유한한 수로 구성되는 경우 해당 그래프를 유한 그래프라고 합니다.

3. 무한 그래프

그래프의 노드 수와 에지 수에 유한한 숫자를 넣을 수 없는 경우 그래프를 무한 그래프라고 합니다. 무한 그래프는 셀 수 없습니다. 즉, 이 유형의 그래프에서 노드 또는 에지의 수를 셀 수 없습니다.

4. 간단한 그래프

한 쌍의 정점 사이에 단 하나의 모서리만 있는 그래프를 단순 그래프라고 합니다. 따라서 두 개의 노드는 그래프에서 하나의 에지로 연결되어 있으며, 이를 통해 이들 사이의 명확한 관계를 식별할 수 있습니다.

5. 멀티 그래프

한 쌍의 노드가 그래프의 여러 가장자리와 연결된 경우 그래프를 다중 그래프라고 합니다. 다중 그래프는 자체 루프로 구성되지 않습니다. 다중 그래프에 존재할 수 있는 간선에는 두 가지 종류가 있습니다. 그들은:

• 평행 모서리

하나의 출발지에서 동일한 목적지로 가는 두 개의 평행한 도로처럼 평행하게 달리는 가장자리를 평행 가장자리라고 합니다.

• 고리

이는 소스 및 대상 정점이 동일한 에지입니다.

US 확인 - 데이터 과학 프로그램

6. 유향 그래프

두 노드 또는 꼭짓점 사이에 존재하는 모든 가장자리에 정의된 방향이 있는 경우 그래프가 방향이 있다고 합니다. 방향 그래프는 digraph라고도 합니다. 유방향 그래프를 보면 시작 노드와 끝 노드를 결정할 수 있습니다. 유향 그래프의 모든 모서리는 유향 그래프라고 부르기 위해 방향이 지정되어야 합니다.

7. 방향성이 없는 그래프

그래프의 가장자리를 보고 시작 노드와 끝 노드를 식별하기 어려운 경우 그래프를 무방향성 그래프라고 합니다. 유향 그래프와 마찬가지로 가장자리가 무향이어야 무향 그래프라고 합니다.

8. 연결된 그래프

연결된 그래프는 모든 노드 사이에 하나 이상의 경로가 존재하는 그래프입니다. 간단히 말해서 연결된 그래프의 노드에서 시작하면 그래프에 있는 모든 노드를 방문할 수 있어야 합니다. 따라서 모든 노드에 대해 하나 이상의 경로가 있어야 합니다.

9. 연결이 끊어진 그래프

이 유형의 그래프에서는 한 쌍의 노드 또는 꼭짓점 사이에 가장자리가 없습니다. 따라서 연결된 그래프와 달리 모든 정점에서 모든 노드에 도달하는 것은 불가능합니다. 꼭지점 쌍 사이에 경로가 없는 경우 연결이 끊어진 그래프라고 합니다.

10. 완전한 그래프

그래프는 모든 노드 사이에 가장자리가 존재할 때만 완전한 것으로 간주됩니다. 즉, 가장자리가 그래프의 모든 정점을 연결한다는 의미입니다. n개의 정점에 대한 완전한 그래프는 Kn 으로 표시되고 그래프의 간선 수는 nC2 입니다.

11. 순환 그래프

순환 그래프로 간주되려면 그래프에 적어도 하나의 순환 구성요소가 있어야 합니다. 반대로 그래프에 주기가 없으면 비순환 그래프로 간주됩니다.

12. 일반 그래프

일반 그래프에서는 모든 정점의 차수가 같아야 합니다. 노드의 차수는 연결된 노드의 수로 정의할 수 있습니다. 따라서 일반 그래프에서는 모든 노드가 같은 수의 노드에 연결되어야 합니다.

13. 이분 그래프

이분 그래프가 되려면 다음 기준을 충족해야 합니다.

• 그래프는 꼭짓점 집합으로 나누어야 합니다.
• 가장자리는 한 그룹의 노드와 다른 쪽 노드 사이에서만 형성되어야 합니다. 이 규칙은 동일한 노드 집합의 두 꼭지점 간의 연결을 방지합니다.
• 두 그룹 사이에 공통 정점이 없어야 합니다.

위의 모든 규칙을 따르는 그래프는 이분 그래프로 간주되어야 합니다.

14. 레이블이 있는 그래프

그래프의 가장자리에 가중치를 부여할 수 있습니다. 가장자리와 관련된 가중치는 해당 가장자리를 통과하는 비용으로 이해할 수 있습니다. 이러한 값은 고정 매개변수를 기반으로 할 수 있으며 그래프 간에 변경될 수 있습니다. 이제 모든 에지가 그들과 관련된 가중치를 유지한다면 해당 그래프를 레이블이 있는 그래프라고 할 수 있습니다.

15. 방향성 비순환 그래프

방향성 비순환 그래프는 그래프의 방향성 에지가 어떤 형태의 주기도 만들지 않는 방향성 및 비순환성 그래프의 조합입니다. 반대로 방향성 순환 그래프는 순환을 형성하는 방향성 간선이 있는 그래프입니다.

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

컴퓨터 과학에서 그래프의 가장 두드러진 적용은 계산 흐름의 표현입니다. 그래프의 다른 유명한 사용 사례는 다음과 같습니다.

1. 구글 지도

Google Maps에서 그래프 데이터 구조는 운송 시스템을 정의하고 계산합니다. 도로가 다른 도로와 만나 교차점을 형성하면 노드로 간주되며 이러한 두 노드 사이의 도로는 가장자리로 처리됩니다. 따라서 Google 지도는 그래프 데이터 구조를 사용하여 목적지까지 가장 짧고 빠른 길을 찾습니다.

2. 페이스북

Facebook은 무향 그래프를 사용하여 사용자와 사용자의 친구를 식별합니다. 모든 사용자는 꼭짓점으로 취급되며 이들을 친구로 연결하는 연결은 네트워크의 가장자리입니다. 페이스북은 그래프 데이터 구조를 기반으로 한 알고리즘을 통해 '알 수도 있는 사람'을 추천하고 '상호 친구'를 보여줍니다.

3. 월드 와이드 웹

World Wide Web은 유방향 그래프의 한 예입니다. 또한 Google 순위 시스템의 기본 아이디어이기도 합니다. World Wide Web 시스템에서 모든 웹 사이트와 웹 앱은 노드 또는 정점으로 취급되며 한 웹 사이트에서 다른 웹 사이트로의 링크는 에지로 간주됩니다.

4. 운영 체제

운영 체제는 모든 프로세스와 리소스를 노드 또는 정점으로 사용하는 리소스 할당 그래프의 널리 사용되는 사례입니다. Edge는 리소스에서 할당된 프로세스로 또는 요청 프로세스에서 요청된 리소스로 발생합니다. 때로는 이 주기가 무한 루프를 형성하여 교착 상태를 초기화할 수 있습니다.

5. 매핑 시스템

GPS는 이 기술의 도움으로 검색하기로 선택한 근처 레스토랑, 상점 및 장소를 찾기 위해 널리 사용되는 그래프 사례입니다.

6. 마이크로소프트 엑셀

Directed Acyclic Graphs 또는 DAG는 Microsoft Excel에서 사용됩니다.

7. 다익스트라 알고리즘

Dijkstra 알고리즘은 그래프 데이터 구조를 사용하여 2개 또는 경우에 따라 2개 이상의 노드 사이의 최단 경로를 식별합니다.

8. 비행 네트워크:

최적화된 비행 네트워크를 계산하는 것은 그래프 데이터 구조의 또 다른 실제 응용 프로그램입니다. 공항을 노드로, 경로를 가장자리로 생각하면 데이터가 그래프의 기준에 완벽하게 맞습니다. 그렇기 때문에 다양한 향상된 알고리즘의 도움으로 두 공항 또는 노드 사이의 최상의 경로가 결정됩니다.

이들은 데이터 구조의 다양한 그래프 응용 프로그램으로 , 원활한 기능을 구성하고 유지하기 위해 다양한 응용 프로그램 및 시스템에서 전 세계적으로 사용됩니다.

데이터 과학자로서의 여정 시작하기

데이터 사이언티스트가 되어 우리가 배운 다양한 그래프를 활용해 데이터를 재치 있게 다루고 싶다면 upGrad에서 다양한 데이터 사이언스 과정을 확인하세요. 가장 인기 있는 과정 중 하나는 데이터 과학에 대한 PG-IIITB 과정으로 , 데이터 과학자를 꿈꾸고 신진 데이터 과학자가 시작하는 데 탁월한 과정입니다!

코스에서 제공하는 내용은 다음과 같습니다.

• 업계 전문가 및 멘토의 360도 경력 지원
• 정기적인 진행 상황을 측정하기 위한 산업 프로젝트 및 자세한 사례 연구에 대한 실습 경험
• 전 세계 모든 분야의 데이터 과학 전문가와 네트워킹

데이터 과학 에 대한 다른 모든 upGrad 과정 도 확인할 수 있습니다 .