비선형 데이터 구조는 평면 상에 분포 된 요소들의 집합으로 구성되며, 이는 선형 데이터 구조에 존재하는 요소들 사이에 그러한 시퀀스가 없다는 것을 의미합니다.
비교 차트
| 비교 근거 | 나무 | 그래프 |
|---|---|---|
| 통로 | 두 꼭지점 사이에 하나만 있습니다. | 둘 이상의 경로가 허용됩니다. |
| 루트 노드 | 정확히 하나의 루트 노드를 가지고 있습니다. | 그래프에 루트 노드가 없습니다. |
| 루프 | 루프는 허용되지 않습니다. | 그래프는 루프를 가질 수 있습니다. |
| 복잡성 | 덜 복잡한 | 비교적 복잡한 |
| 탐색 기법 | 선주문, 선주문 및 후순위 | 너비 우선 검색과 깊이 우선 검색. |
| 모서리 수 | n-1 (n은 노드의 수) | 정의되지 않음 |
| 모델 유형 | 계층 적 | 회로망 |
나무의 정의
트리는 일반적으로 노드라고하는 데이터 항목의 유한 모음입니다. 위에서 언급했듯이 트리는 정렬 된 순서로 데이터 항목을 정렬하는 비선형 데이터 구조입니다. 다양한 데이터 요소 사이에 계층 적 구조를 표시하는 데 사용되며 정보와 관련된 분기로 데이터를 구성합니다. 트리에 새로운 에지를 추가하면 루프 또는 회로가 형성됩니다.
이진 트리, 이진 탐색 트리, AVL 트리, 스레드 이진 트리, B- 트리 등의 여러 가지 유형의 트리가 있습니다. 데이터 압축, 파일 저장, 산술 표현식 및 게임 트리 조작은 트리의 응용 프로그램 중 일부입니다 데이터 구조.
나무의 속성 :
- 나무의 뿌리로 알려진 나무 꼭대기에 지정된 노드가 있습니다.
- 나머지 데이터 항목은 하위 트리로 참조되는 분리 된 하위 집합으로 나뉩니다.
- 나무는 바닥쪽으로 높이가 확장됩니다.
- 하나의 루트에서 다른 모든 노드까지의 경로가 있어야한다는 것을 의미하는 트리가 연결되어야합니다.
- 루프를 포함하지 않습니다.
- 나무에는 n-1 개의 모서리가 있습니다.
터미널 노드, 에지, 레벨, 차수, 깊이, 포레스트 등과 같은 나무와 관련된 다양한 용어가 있습니다. 이러한 용어들 중 일부는 아래에 설명되어 있습니다.
- Edge - 두 노드를 연결하는 선.
- 레벨 - 루트 노드가 레벨 0에있는 것과 같은 방식으로 트리가 레벨 로 분할됩니다. 그 직계 하위 노드는 레벨 1에 있고 그 직계 하위 노드는 레벨 2에 있고 터미널 노드 또는 리프 노드까지 있습니다.
- Degree - 주어진 트리에서 노드의 하위 트리 수입니다.
- Depth - 주어진 트리에서 노드의 최대 레벨이며 높이 라고도합니다.
- 터미널 노드 - 최상위 노드는 터미널 노드이며 터미널 및 루트 노드를 제외한 다른 노드는 비 터미널 노드로 알려져 있습니다.
그래프의 정의
그래프 는 다양한 종류의 물리적 구조를 나타낼 수있는 수학적 비선형 데이터 구조이기도합니다. 이것은 정점 그룹 (또는 노드)과 두 개의 정점을 연결하는 모서리 집합으로 구성됩니다. 그래프의 정점은 점 또는 원으로 표시되고 모서리는 호 또는 선 세그먼트로 표시됩니다. 엣지는 E (v, w)로 표시되며, 여기서 v와 w는 정점 쌍입니다. 회로 또는 연결된 그래프에서 모서리를 제거하면 트리 인 하위 그래프가 작성됩니다.
그래프는 지시 형, 비 지향성, 연결 형, 비 연결형, 단순형 및 다중형 그래프와 같이 다양한 범주로 분류됩니다. 컴퓨터 네트워크, 교통 시스템, 사회 네트워크 그래프, 전기 회로 및 프로젝트 계획은 그래프 데이터 구조의 일부 응용 프로그램입니다. 그래프 구조가 분석되는 PERT (프로그램 평가 및 검토 기술) 및 CPM (임계 경로 방법)이라는 관리 기법에도 사용됩니다.
그래프의 프로퍼티 :
- 그래프의 정점은 모서리를 사용하여 임의의 수의 다른 정점에 연결할 수 있습니다.
- 가장자리는 bidirected 또는 지시 될 수있다.
- 가장자리에 가중치를 적용 할 수 있습니다.
그래프에서 인접 꼭지점, 경로, 주기, 차수, 연결된 그래프, 전체 그래프, 가중 그래프 등 다양한 용어를 사용합니다. 이러한 용어 중 일부를 이해해 봅시다.
- 인접한 정점 - 정점 a는 정점 b에 인접합니다 (a, b) 또는 (b, a).
- 경로 - 임의의 정점 w의 경로는 인접한 정점 시퀀스입니다.
- 사이클 - 첫 번째와 마지막 버텍스가 동일한 경로입니다.
- Degree - 정점에 입사하는 다수의 가장자리입니다.
- 연결된 그래프 - 임의의 정점에서 다른 정점까지의 경로가있는 경우 해당 그래프를 연결된 그래프라고합니다.
트리와 그래프의 주요 차이점
- 하나의 트리에는 두 개의 정점 사이에 하나의 경로 만 존재하는 반면 그래프는 노드 사이에 단방향 및 양방향 경로를 가질 수 있습니다.
- 트리에는 정확하게 하나의 루트 노드가 있으며 모든 자식은 단 하나의 부모 만 가질 수 있습니다. 반대로 그래프에서 루트 노드의 개념은 없습니다.
- 그래프에는 루프와 자체 루프가있을 수 있지만 트리에는 루프와 자체 루프가있을 수 없습니다.
- 그래프는 루프와 자체 루프를 가질 수 있기 때문에 더욱 복잡합니다. 대조적으로 나무는 그래프에 비해 단순합니다.
- 트리는 선주문, 순차 및 후행 기술을 사용하여 가로 지릅니다. 다른 한편, 그래프 트래버 설에서는 BFS (Breadth First Search)와 DFS (Depth First Search)를 사용합니다.
- 나무는 n-1 개의 모서리를 가질 수 있습니다. 반대로, 그래프에는 미리 정의 된 수의 에지가 없으며 그래프에 따라 다릅니다.
- 트리에는 계층 적 구조가 있지만 그래프에는 네트워크 모델이 있습니다.
결론
그래프와 트리는 다양한 복잡한 문제를 해결하는 데 사용되는 비선형 데이터 구조입니다. 그래프는 에지가 한 쌍의 꼭지점을 연결하는 정점과 가장자리 그룹으로, 트리는 연결되어 있어야하고 루프가 없어야하는 최소 연결 그래프로 간주됩니다.
