[C++][자료구조] Graph와 Tree의 차이? 구현법은?

1. Graph(그래프) 자료구조

 

*용어정리
G = (V, E) (정점 Node, Vertex / 간선 Edge)

- 경로(시작점과 도착점이 다를 경우), 사이클(시작점과 도착점이 같을 경우)
cf) 단순경로/단순 사이클: 같은 정점을 두 번 이상 방문하지 않는 경로/사이클

- 방향이 있는 그래프/방향이 없는 그래프

- 가중치: 간선의 비용.

- 차수(Degree): 정점과 연결된 간선의 개수

cf) 방향 그래프의 경우, In-degree, Out-degree로 나누어서 차수를 계산한다.

 

*그래프를 저장하는 법
; 어떤 정점 x와 연결된 간선을 찾기 위해 어떻게 효율적으로 저장할지.

 

1) 인접 행렬 방법
A[i][j] = 1, A[i][j] = 0. <- 연결되어 있으면 1, 연결안되어 있으면 0

 

2) 인접 리스트 방법
A[i] = i와 연결된 정점을 리스트로 포함함. 동적 배열(vector, ArrayList 등)이 필요함.
ex) A[1] = {2, 5}, A[2] = {1, 3, 4, 5}, ...
ex) 가중치도 같이 저장할 때는 pair를 이용해서 A[1] = { (2, 2), (5, 7) }, A[2] = { (1, 2), (3, 2), (4, 3), (5, 1) }로 표현함. 1에서 2로 갈 때 가중치가 2, 1에서 5로 갈 때 가중치가 7. 이렇게

//인접리스트로 그래프 표현하기

#include <iostream>
#include <vector>
using namespace std;

int main() {
	int nodeNum, inputNode1, inputNode2;
	cin >> nodeNum;
	vector<int> *graph = new vector<int>[nodeNum + 1];

	//Input
	for (int i = 0; i < nodeNum - 1; i++) {//edge의 개수는 node의 개수 - 1.
		cin >> inputNode1 >> inputNode2;
		graph[inputNode1].push_back(inputNode2);
		graph[inputNode2].push_back(inputNode1);
	}

	delete[] graph;
	return 0;
}

//인접리스트에 가중치도 저장하는 법

#include <iostream>
#include <vector>
using namespace std;

int main() {
	int nodeNum, inputNode1, inputNode2, weight;//노드수, 노드1, 노드2, 가중치
	cin >> nodeNum;
    
        //노드개수만큼 pair 인접리스트 생성
	vector<pair<int, int>> *graph = new vector<pair<int, int>> [nodeNum + 1];
	
	//값 입력
	for (int i = 1; i < nodeNum; i++) {
		cin >> inputNode1 >> inputNode2 >> weight;
		graph[inputNode1].push_back(make_pair(inputNode2, weight));
		graph[inputNode2].push_back(make_pair(inputNode1, weight));
	}
    
        delete[] graph;
	return 0;
}

 

*인접 행렬/인접 리스트 공간 복잡도
1) 인접 행렬: O(V^2)
2) 인접 리스트: O(E)

 

공간복잡도로만 보면 인접행렬이 훨씬 좋음. 하지만 인접행렬이 좋을 때도 있음.

예를 들어, u, v가 있을 때, u->v가 존재하는지를 알아보려면 O(1)의 시간으로 알 수 있음. A[u][v]만 확인하면 되기 때문.
반면에 인접 리스트는 A[u] = { 0, 0, 0, ...} 로 표현되기 때문에 원소 하나하나를 다 찾아봐야 함. 그래서 O(차수) 가 걸림.

또한, 모든 정점이 연결된 완전 그래프일 때는 인접행렬을 써도 공간복잡도가 동일하다.

 

 

2. Tree(트리) 자료구조

: 루프를 가지지 않는 그래프. 노드들을 간선으로 연결한 계층형 자료구조.

출처:&nbsp;https://techdifferences.com/difference-between-tree-and-graph.html

Tree	Graph
두 정점사이에 하나의 길만 존재 하나의 루트 노드가 존재 루프가 허용되지 않음 계층적 모델	두 정점사이에 둘 이상의 경로가 허용됨 루트 노드가 없음 루프가 있을 수 있음 회로망 모델

* 용어정리

- Edge(간선): 두 노드를 연결하는 선

- Level: 노드가 속한 트리의 깊이. 루트노드의 레벨 0, 그 다음 자식 노드부터 +1 Level

- Degree(차수): 한 노드가 가진 자식의 수. ex) 위 그림에서 A노드의 Degree는 2개.

- Depth: 트리의 최대 레벨(높이). 루트 노드부터의 거리.

- Terminal Node: Degree(차수)가 0인 노드. 터미널 노드와 루트 노드를 제외한 나머지를 비터미널 노드라고 부름.

- 부모노드: 노드에 연결된 한단계 상위 레벨의 노드. ex) B의 부모노드: A

- 자식노드: 노드에 연결된 서브트리의 루트노드들. ex) A의 자식 노드: B,C

- 형제노드: 부모가 같은 노드. ex) B, C

 

* 구현방법은 Graph와 같음.

인접리스트를 이용한 가중치없는 Tree, 인접리스트와 pair를 이용한 가중치 있는 Tree.