[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
    }
}


참고자료