[Algorithm] C++에서 그래프 구현하기
업데이트(2020.05.26): 배열의 크기를 변수로 받아서 동적으로 그래프를 생성하는 예시 추가
업데이트(2019.03.02): 그래프(방향, 무방향) 이미지 추가
C++에서 그래프를 구현하는 방법을 알아보자.
환경 및 선수조건
- C++
- 그래프의 기본 개념(정점, 간선 등등)
그래프의 구현
- 행렬을 이용한 구현
- List를 이용한 구현(vector를 Linked List처럼 사용)
행렬
개념
- 행렬: 정점
- 행렬값: 가중치 값(연결만 되었으면 1)
- 행과열은 정점을 나타내고 [i][j]값은 정점 i로부터 j가 연결되어있으면 1 아니면 0으로 표시
- 가중치가 있다면 [i][j]에 가중치를 저장
방향 그래프
- 방향 그래프 예시
무방향 그래프
- 무방향 그래프 예시
- 무방향 그래프는 행렬이 대칭임을 알 수 있습니다.
코드
#include <iostream>
#include <stdio.h>
using namespace std;
int main(){
int n,m;
cin >> n >> m; // 정점과 간선의 개수를 입력받음
int graph[n+1][n+1];
// Visual Studio의 경우
/* 변수를 통해서 배열을 동적으로 생성할 때
int ** graph = new int * [n];
for (int i = 0; i <= n; ++i)
graph[i] = new int[m];
*/
// 정적으로 선언했기 때문에 값들을 전부 -1로 초기화
for(int i=0; i<=n; i++){
for(int j=0; j<=n; j++){
graph[i][j] = -1;
}
}
for(int i=0; i<m; i++){
int u,v;
scanf("%d %d", &u, &v);
graph[u][v] = graph[v][u] = 1;
// 단방향의 경우 graph[u][v] = 1;
// 가중치가 있는 경우 단방향의 경우 graph[u][v] = 가중치값;
}
}
리스트(vector를 Linked List처럼 사용)
개념
- vector: 정점
- vector의 요소: 연결된 정점
- 정점의 수만큼 리스트를 생성하고 해당 정점 리스트에다가 연결된 정점들을 추가
방향 그래프
- 방향 그래프 예시
무방향 그래프
- 무방향 그래프 예시
코드
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
int main(){
int n,m;
cin >> n >> m; // 정점과 간선의 개수를 입력받음
vector<int> graph[n+1];
// Visual Studio의 경우
/* 변수를 통해서 배열을 동적으로 생성할 때
vector<int> * graph = new vector<int>[n+1];
*/
for(int i=0; i<m; i++){
int u,v;
scanf("%d %d", &u, &v);
graph[u].push_back(v);
graph[v].push_back(u);
// 단방향의 경우 graph[u].push_back(v);만 작성
// 가중치가 있는 경우 vector<pair<int,int>> graph[n+1];로 만들거나 구조체를 만들어서 가중치와 함께 저장
// graph[u].push_back(make_pair(v,w)); u->v 가중치: w
}
}