그래프 데이터 구조 가이드

효과적인 프로그래머는 데이터 구조와 알고리즘에 대한 확실한 이해가 필요합니다. 기술 인터뷰는 종종 문제 해결 및 비판적 사고 능력을 테스트합니다.

그래프는 프로그래밍에서 많은 중요한 데이터 구조 중 하나입니다. 대부분의 경우 그래프를 이해하고 그래프 기반 문제를 해결하는 것은 쉽지 않습니다.

MAKEUSEOF 오늘의 비디오

그래프란 무엇이며 그래프에 대해 알아야 할 사항은 무엇입니까?

그래프란?

그래프는 노드(또는 꼭짓점)를 연결하는 간선이 있는 비선형 데이터 구조입니다. 모든 나무는 그래프의 하위 유형이지만 모든 그래프가 나무는 아니며 그래프는 나무가 시작된 데이터 구조입니다.

당신이 할 수 있지만 JavaScript로 데이터 구조 구축 및 기타 언어를 사용하여 다양한 방법으로 그래프를 구현할 수 있습니다. 가장 인기 있는 접근 방식은 에지 목록 , 인접 목록 , 그리고 인접 행렬 .

그만큼 그래프 표현을 위한 칸아카데미 가이드 그래프를 표현하는 방법을 배우기에 좋은 자료입니다.

다양한 종류의 그래프가 있습니다. 한 가지 일반적인 차이점은 다음과 같습니다. 지시 그리고 무향 그래프; 이러한 문제는 코딩 문제와 실제 사용에서 많이 나타납니다.

그래프의 종류

유향 그래프: 모든 간선이 방향을 갖는 그래프로 라고도 합니다. 다이그래프.
무방향 그래프: 무방향 그래프는 양방향 그래프라고도 합니다. 무방향 그래프에서 간선의 방향은 중요하지 않으며 순회는 모든 방향으로 갈 수 있습니다.
가중 그래프: 가중 그래프는 노드와 간선에 연관된 값이 있는 그래프입니다. 대부분의 경우 이 값은 해당 노드 또는 에지를 탐색하는 비용을 나타냅니다.
유한 그래프: 유한한 수의 노드와 간선이 있는 그래프입니다.
무한 그래프: 무한한 양의 노드와 간선이 있는 그래프.
사소한 그래프: 노드가 하나만 있고 간선이 없는 그래프입니다.
간단한 그래프: 그래프의 각 노드 쌍을 연결하는 간선이 하나만 있는 경우 이를 단순 그래프라고 합니다.
널 그래프: 널 그래프는 노드를 연결하는 간선이 없는 그래프입니다.
멀티그래프: 다중 그래프에서 적어도 한 쌍의 노드에는 두 개 이상의 간선이 연결되어 있습니다. 다중 그래프에는 자체 루프가 없습니다.
완전한 그래프: 완전한 그래프는 모든 노드가 그래프의 다른 모든 노드에 연결되는 그래프입니다. 로도 알려져 있습니다. 전체 그래프 .
의사 그래프: 다른 그래프 가장자리와 별도로 자체 루프가 있는 그래프를 의사 그래프라고 합니다.
일반 그래프: 일반 그래프는 모든 노드의 차수가 동일한 그래프입니다. 즉, 모든 노드에는 동일한 수의 이웃이 있습니다.
연결된 그래프: 연결된 그래프는 단순히 두 노드가 연결된 모든 그래프입니다. 즉, 그래프의 모든 두 노드 사이에 하나 이상의 경로가 있는 그래프입니다.
연결이 끊긴 그래프: 연결이 끊긴 그래프는 연결된 그래프의 정반대입니다. 연결이 끊긴 그래프에는 다음과 같이 그래프의 노드를 연결하는 모서리가 없습니다. 없는 그래프.
순환 그래프: 순환 그래프는 하나 이상의 그래프 주기(시작 위치에서 끝나는 경로)를 포함하는 그래프입니다.
비순환 그래프: 비순환 그래프는 순환이 전혀 없는 그래프입니다. 그것은 지시되거나 지시되지 않을 수 있습니다.
하위 그래프: 하위 그래프는 파생 그래프입니다. 다른 그래프의 부분집합인 노드와 간선으로 구성된 그래프입니다.