그래프 G(V, E)

정점 (vertex) 의 집합 V와 이를 연결하는 간선 (edge)들의 집합 E로 구성되어있음.

그래프는 트리와 달리 정점을 객체 인스턴스로 표현하지 않고, 배열에 각 정점의 정보를 저장하여 구현한다.

그래프의 종류

• 방향 그래프 (directed graph) 혹은 유향 그래프
• 무향 그래프 (undirected graph)
• 가중치 그래프(weighted graph)

그래프의 경로

한 정점을 최대 한 번만 지나가는 경로를 단순 경로(simple path)라고 한다. 시작한 점에서 끝나는 경로를 사이클 (cycle) 경로 혹은 회로라고 한다.

인접 리스트 (adjacent list)

vector<list<int>> adjecent;

정점마다 해당 정점에서 나가는 간선의 목록을 저장하여 그래프로 표현한다.

adjacent[i]는 정점 i와 간선을 통해 연결된 정점들의 번호를 저장하는 연결리스트이다.

이 경우 시간 복잡도는 O(|V| + |E|) 이다. 간선의 수가 |V|^2에 비해 훨씬 적은 희소 그래프 (sparse graph)의 경우에 사용하기 유리하다.

인접 행렬 (adjacent matrix)

vector<vector<bool>> adjacent;