목록자료구조 (13)
Binaryseop
1. 순차 자료구조 방식을 이용한 그래프 구현: 인접 행렬 그래프를 구성하는 정점과 두 정점을 연결한 간선의 유무를 저장하기 위해서 2차원의 정방 행렬을 사용합니다. n개의 정점을 가진 그래프는 각 정점에 대한 행과 열을 나타내야 하므로 n x n 정방 행렬을 사용하고 두 정점이 인접하면 1, 인접하지 않으면 0으로 표현합니다. 이런 방법으로 그래프를 표현한 행렬을 인접 행렬이라고 합니다. ① 무방향 그래프 · 임의의 한 정점에서 자기 자신을 가리키는 간선은 없기 때문에 인접 행렬의 대각선은 항상 0입니다. · 간선 (Vi, Vj)는 간선 (Vj, Vi)와 같은 의미이기 때문에 행렬의 (i, j)값과 (j, i)값은 항상 같습니다. 따라서 무방향 그래프에서 인접 행렬은 대각선을 기준으로 대칭을 이룹니다...
1. 그래프 그래프(Graph)는 연결되어있는 원소간의 관계를 표현한 자료구조입니다. · 그래프는 연결할 객체를 나타내는 정점(Vertext)과 객체를 연결하는 간선(Edge)의 집합으로 구성됩니다. · 그래프 G를 G=(V, E)로 정의하는데, V는 정점의 집합, E는 간선들의 집합을 의미합니다. 2. 그래프 종류 ① 무방향 그래프 무방향 그래프(Undirected Graph)는 두 정점을 연결하는 간선에 방향이 없는 그래프. · 무향방 그래프에서 정점 Vi와 Vj를 연결하는 간선을 (Vi, Vj)로 표현하는데, 이때 (Vi, Vj)와 (Vj, Vi)는 같은 간선을 나타냅니다. · V(G1)={A,B,C,D}, E(G1)={(A,B), (A,D), (B,C), (B,D), (C,D)} ② 방향 그래프 ..
1. 트리 트리(Tree)란 비선형 자료구조 중에서 자료들 간에 계층관계를 가진 계층형 자료구조(Hierarchical Data Structure)를 말합니다. · 노드(Node): 트리를 구성하는 원소(자료) · 간선(Edge): 노드를 연결하는 선 · 차수(Dgree): 자식 노드의 수 · 높이(Height): 루트에서 해당 노드에 이르는 경로에 있는 간선의 수 · 루트 노드(Root Node): 트리의 시작 노드 · 형제 노드(Sibling Node): 같은 부모 노드의 자식노드들 · 조상 노드(Ancestor Node): 한 노드에서 간선을 따라 루트 노드까지 이르는 경로에 있는 노드들 · 자손 노드(Descendant Node): 한 노드의 서브 트리에 있는 노드들 · 단말 또는 리프 노드(Le..
1. 덱(Deque, Double-ended Queue) 덱은 큐의 양쪽 끝에서 데이터의 삽입과 삭제가 모두 가능하게 만든 큐로서, 스택과 큐의 성질을 모두 가지고 있는 자료구조입니다. 2. 덱의 연산 덱은 양쪽 끝에서 데이터의 삽입과 삭제 연산을 모두 할 수 있기 때문에, 스택과 큐의 연산을 모두 구현할 수 있습니다. · 스택 연산 front를 스택의 top으로 생각했을 때, 덱의 insertFront() 연산과 deleteFront() 연산은 push() 연산, pop() 연산과 같습니다. rear를 스택의 top으로 생각했을 때, 덱의 insertRear() 연산과 deleteRear() 연산은 push() 연산, pop() 연산과 같습니다. · 큐 연산 insertRear() 연산과 deleteF..