자료구조_그래프

그래프 자료구조

• 컴퓨터과학 분야에서는 데이터를 저장하는 자료구조에서 그래프 이론을 사용하였다.
• 그래프의 특칭과 규칙을 갖도록 데이터를 저장한 것이며, 데이터들의 관계를 저장할 때 함께 정의하여 저장할 방법
• 컴퓨터과학 분야에서는 그래프 자료구조를 표현할 때 노드로 표현한다.
• 노드의 이름이나　노드의 정의보다는 노드의 수가 중요
• 그래프 형태로 저장한다는 것은 노드와 간선이 정해진 모델에서 노드와 간선을 정의하여 저장한다는 것
• 그래프를 배열로 저장한다는 것은 노드 데이터를 배열 자료구조로 저장한다는 것, 간선을 데이터로 표현하여 배열 자료구조로 저장한다는 것

인접리스트로 표현

graph_array = {A:[B, C], B:[A, E], C:[A,D,E], D:[C, E], E:[B,C,D]}

2차원 배열로 표현

graph_array = [[0,1,1,0,0], [1,0,0,0,1], [1,0,0,1,1], [0,0,1,0,1], [0,1,1,0]]

• 연결 리스트에서는 간선에 대한 정보가 아니라 노드에 대한 정보로 간선의 정보를 저장하였으며 배열에서는 노드에 대한 정보가 아니라 간선에 대한 정보를 저장하여 표현한 것을 알 수 있음
• 그래프 자료구조를 이용하여 여러가지 문제를 쉽게 해결할 수 있음
• 최단 거리 문제를 해결한 알고리즘인 프림 알고리즘, 크러스컬 아록리점, 다익스트라 알고리즘 등은 데이터를 그래프 자료구조로 저장한 후 저장된 데이터들을 이용하여 최단거리를 찾는 알고리즘
• 탐색 문제 이외에도 깊이 우선 탐색인 DFS 알고리즘과 너비 우선 탐색인 BFS 탐색 알고리즘이 있다.

트리 자료구조

• 트리는 그래프의 일종으로 여러 노드가 한 노드를 가리킬 수 없는 구조를 말함

• 트리도 그래프의 일종이므로 노드와 간선으로 구성된다.

• 노드와 연결된 노드들 사이에는 부모와 자식 관계가 있으며, 한 방향으로만 연결되어있고, 자식 노드는 반드시 하나의 부모만 갖도록 하는 규칙이 있다.

• 트리에 여러 가지 규칙을 추가해 다양한 형태의 트리를 정의

• 자식 노드가 2개 이상을 정의할 수 있는 트리, 이진 트리는 자식 노드가 2개 이하인 트리, 완전 이진 트리는 자식 노드를 추가할 때 왼쪽부터 오른쪽으로 추가하는 규칙을 갖는 트리이고, 균형 이진 트리는 자식 노드의 추가 위치는 상관없지만 왼쪽과 오른쪽 레벨 차이가 1이하가 되도록 노드를 추가하는 트리 구조

트리에서 사용하는 용어

트리의 가장 위에 있는 노드 : 루트 노드

트리의 가장 마지막에 있는 노드 : 리프 노드

루트 노드와 리프 노드 사이의 노드들을 : 가지 노드

부모 노드에서 자식 노드가 생성될 때마다 레벨을 정의

한 부모 노드에서 생성된 노드들을 형제 노드로 정의

각 노드의 차수는 자식 노드의 개수를 의미

• 트리 자료구조는 트리의 특징과 규칙을 갖도록 데이터를 저장하는 자료구조
• 트리의 특징과 규칙으로 저장되지만 트리 자료구조도 기본 자료형과 기본 자료구조로 주기억장치에 저장됨
• 트리도 기본 자료구조인 연결 리스트와 배열을 이용하여 데이터를 저장할 수 있음
• 이때의 노드는 특정 값을 가지고 있으며, 하나의 자료구조로 저장된 노드들은 부모와 자식 관계를 갖는 간선임
• 연결 리스트 자료구조로 저장할 때 각 노드는 두 개의 주소값을 저장할 수 있는 영역을 갖도록 정의
• 왼족 주소값 영역에는 왼쪽 자식 노드 데이터가 저장된 주소값이 저장되며, 오른쪽 주소값 영역에는 오른쪽 자식 노드 데이터가 저장된 주소값이 저장되도록 정의
• 2차원 배열 자료구조로 저장할 때는 부모 노드와 자식 노드를 연결 리스트로 연결, 자식 노드를 배열로 표현할 수 있음
• 이때 인덱스 0에 저장된 데이터는 왼쪽 자식 노드이고, 인덱스 1에 저장된 데이터는 오른쪽 자식 노드로 정의

---

• 트리 자료구조는 효율적인 데이터의 삽입과 삭제 방법을 제공
• 트리 자료구조를 이욯나 문제 해결 알고리즘의 예의 경우, 이진 탐색 알고리즘, 정렬 문제를 트리 자료구조를 이용하여 해결한 힙 정렬 알고리즘 등이 있음
• 트리는 그래프의 일종으로 컴퓨터과학에서 많이 사용하는 자료구조 중 하나

	그래프	트리
정의	노드와 그 노드를 연결하는 간선을 하나로 모아놓은 자료구조	그래프의 한 종류
방향성	방향/무방향 그래프 모두 존재	방향 그래프
사이클	사이클 가능 순환/비순환 그래프 모두 가능	사이클 불가능 비순환 그래프
루트 노드	루트 노드 개념이 없음	한 개의 루트 노드만 존재
부모-자식	부모-자식 개념이 없음	부모-자식 관계
모델	네트워크 모델	계층 모델
간선의 수	그래프에 따라 간선의 수가 다름 간선이 없을 수도 있음	노드가 n인 트리는 항성 n-1의 간선을 가짐

그래프 순회

• 순회는 그래프 또는 트리와 같은 연결 구조에서 모든 노드를 순차적으로 탐색하는 방법

• 하나의 노드로 시작하여 차례대로 모든 노드를 한 번씩 방문하는 방법

• 모든 노드 또는 특정 노드를 방문하는 방법을 찾기 위한 방법

  예) 도시와 도로를 그래프로 표현하는 경우 특정 도시에서 다른 도시로 갈 수 있는 길이 있는지 확인할 때 순회 방법을 사용할 수 있다.
  
  전자회로에서 단자와 연결선을 그래프로 표현하는 경우 특정 단자와 연결되어 있는지 확인할 때 순회 방법을 사용할 수 있음

• 이와 같이 순회는 그래프 자료구조를 바탕으로 여러 가지 문제를 해결하기 위해 정의, 탐색 알고리즘으로 알려저 있다

• 깊이 우선 순회 (DSF: Depth First Search), 너비 우선 순회(BSF: Breadth First Search)

깊이 우선 순회

• 깊이 우선 순회(DSF)는 시작 노드를 정하고 방문하지 않은 노드가 존재할 때까지 방문하는 방법

규칙

• 현재 노드의 인접 노드 중 방문하지 않은 노드를 방문
• 방문한 노드의 인접 노드 중 더 이상 방문하지 않은 인접 노드가 존재하지 않으면 방문했던 경로로 되돌아간다
• 방문하지 않은 노드가 더 이상 존재하지 않으면 종료한다.

• 그래프의 노드를 방문하는 순회를 하기 위해서는 시작 노드를 반드시 정해야 한다
• 시작 노드를 정하고, 다음 방문 노드는 조건없이 무작위 선택으로 한다고 가정
• 깊이 우선 순회 규칙에 따라 인접 노드 중 더 이상 방문하지 않은 인접 노드가 존재하지 않으면 방문했던 경로를 되돌아 간다. 계속해서 이 방법을 반복하며, 최초에 선택된 노드로 되돌아 가며 방문하지 않은 인접노드가 없고 시작 노드로 되돌아오고 모든 노드의 순회를 마치고 돌아옴을 알 수 있음
• 깊이 우선 순회 방법은 시작 노드에서 한 방향으로 마지막 노드까지 방문하고, 방문 경로를 되돌아가면서 방문하지 않은 노드를 확인 후 방문

너비 우선 순회

• 너비 우선 순회(BSF)는 시작 노드를 정하고 인접한 노드를 모두 방문하는 순회 방법

규칙

• 현재 노드의 인접 노드를 모두 방문
• 인접 노드 중 더 이상 방문하지 않은 인접 노드가 존재하지 않으면 방문했던 경로를 되돌아간다
• 방문하지 않은 노드가 더 이상 존재하지 않으면 종료

• 너비 우선 순회 방법은 시작 노드와 가까운 노드부터 방문하고 멀리 떨어진 노드를 나중에 방문하는 순회 방법