그래프의 정의
노드와 그 노드를 연결하는 간선으로 이루어진 자료구조
;연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조이다.
그래프의 종류
(1)방향에 따른 분류
- 무방향 그래프(undirected Graph)
- 무방향 그래프의 간선은 연결 된 노드간 양 방향으로 이동 가능하다
- 정점 A와 정점 B를 연결하는 간선은 (A, B)로 표현한다.
- 방향 그래프(Directed Graph)
- 간선에 방향성이 존재하는 그래프
- 두 개의 정점 A->B로 가는 간선을 <A, B>로 표현한다.
(2)가중치 그래프
- 간선에 비용이나 가중치가 할당된 그래프
- 네트워크라고도 한다.
그 외에도 비연결 여부, 사이클 존재 여부로 구분 가능하다.
그래프의 구현
(1)인접 행렬
인접 행렬은 그래프의 연결 관계를 이차원 배열로 나타내는 방식입니다. 인접 행렬을 adj[][]1라고 한다면 adj[i][j]에 대해서 다음과 같이 정의할 수 있습니다.
adj[i][j] : 노드 i에서 노드 j로 가는 간선이 있으면 1, 아니면 0
cf) 만약 간선에 가중치가 있는 그래프라면 1 대신에 가중치의 값을 직접 넣어주는 방식으로 구현할 수 있습니다.
(2)인접 리스트
STL vector를 이용해서 vector<int> Graph []로 나타내는 방식
(1)무방향. 양방으로 push_back 함수를 통해 생성해준다.
(2)가중치가 있는 그래프 생성
vector<pair<int, int>> Graph 노드 번호와 가중치를 같이 저장
