구현2 [자료구조] 그래프 구현 1. 그래프 구현 방법 인접 행렬(adjacent matrix) : 2차원 배열 사용 인접 리스트(adjacency list) : 연결리스트 사용 1) 인접 행렬 방법 if(간선 (i, j)가 그래프에 존재) M[i][j] = 1. 존재하지 않으면 M[i][j] = 0 2. 인접 행렬 행렬에 대한 2차원 배열을 사용하는 순차 자료구조 방법 그래프의 두 정점을 연결한 간선의 유무를 행렬로 저장 n개의 정점을 가진 그래프 : n * n 정방 행렬 행렬의 행 번호와 열 번호 : 그래프의 정점 행렬값 : 두 정점이 인접되어 있으면 1, 인접되어있지 않으면 0 1) 인접 행렬 예 2) 무방향 그래프 행 i의 합 = 열 i의 합 = 정점 i의 차수 3) 방향 그래프 행 i의 합 = 정점 i의 진출 차수(Out) 열.. 2020. 6. 28. [자료구조] 이진 트리 구현 1. 순차 자료구조를 이용한 이진 트리 구현 1) 1차원 배열의 순차 자료구조 사용 높이가 h인 포화 이진 트리의 노드 번호를 배열의 인덱스로 사용 인덱스 0번 : 실제로 사용하지 않고 비워둔다. 인덱스 1번 : 루트 저장 2) 이진 트리의 1차원 배열에서의 인덱스 관계 노드 인덱스 성립 조건 노드 i의 부모 노드 [ i/2 ] 정수로 만듦 (가우스 기호) i > 1 노드 i의 왼쪽 자식 노드 2 * i (2 * i) ≤ n 노드 i의 오른쪽 자식 노드 (2 * i) + 1 (2 * i + 1) ≤ n 루트 노드 1 0 < n 3) 이진 트리의 순차 자료구조 표현 단점 사향(Skewed) 이진 트리의 경우에 사용하지 않는 배열 원소에 대한 메모리 공간 낭비 발생 트리의 원소 삽입, 삭제에 대한 배열의 크.. 2020. 6. 24. 이전 1 다음