[Algorithm] C++에서 그래프 구현하기

업데이트(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];

    // 정적으로 선언했기 때문에 값들을 전부 -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];

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


참고자료

[Linux] 쉘 스크립트에서 멀티프로세스(혹은 스레드) 기능 사용하기

> 백그라운드로 명령어를 실행해서 병렬적으로 실행되는 멀티 프로세스 환경을 만들어보자.## 환경- Linux 기반 시스템- Bash shell(/bin/bash)## 멀티프로세스? 병렬처리? 멀티스레드? 백그라운드 프로세스?- 여기서 진행할 방식...… Continue reading