그래프

노드와 에지로 구성된 집합

• 노드(node) : 데이터를 표현하는 단위
• 에지(edge) : 노드를 연결

에지 리스트

에지를 중심으로 그래프를 표현

• 배열에 출발 노드, 도착 노드를 저장하여 에지를 표현

vector<pair<int,int>> graph;

int u,v;

graph.push_back(make_pair(u,v))

인접 행렬

2차원 배열을 자료구조로 이용하여 그래프를 표현

vector<vector<int>> adjMatrix;
adjMatrix[0][1] = 1; // 정점 0 과 정점 1 이 연결되어 있음

인접 리스트

2차원 벡터로 그래프를 표현

vector<vector<int>> adjList;

adjList[1] = {2,3,5}; // 정점 1 과 정점 2, 3, 5 가 연결되어 있음

트리

노드와 에지로 연결된 그래프의 한 형태

• 순환 구조(Cycle)를 지니고 있지 않고, 1개의 루트 노드가 존재
• 루트 노드를 제외한 노드는 단 1개의 부모 노드를 가짐
• 트리의 부분 트리는 트리의 모든 특징을 따름