Graph 알고리즘

⛳️ 그래프의 종류

• Directed Graph: 방향이 있는 그래프
  
  • Cyclic Graph: 하나 이상의 cycle이 있는 경우
  • Acyclic Graph: cycle이 없는 경우
• Undirected Graph: 방향이 없는 그래프 

 

⛳️ 그래프를 표현하는 방법

1. Adjacency Matrix, 행렬 (2차원배열)

matrix[i][j]에 정점 i와 정점 j의 연결 상태 저장

간선이 있으면 1, 간선이 없으면 0으로 표현

 

(1) 방향 그래프

(2) 무방향 그래프

 

코드

#include <iostream>

using namespace std;

int main(){
	// n : 정점 개수, m : 간선 개수
    int n,m;
    cin >> n >> m;

    int graph[n+1][n+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;
    }
}

 

2. Adjacency List, 연결 리스트 (1차원배열)

정점의 수만큼 배열을 생성, 각 정점 배열에 연결된 정점을 연결 리스트로 추가

 

(1) 방향 그래프

(2) 무방향 그래프

 

코드

#include <iostream>
#include <stdio.h>
#include <vector>

using namespace std;

int main(){
	// n: 정점 개수, m: 간선 개수
    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);만 작성
    }
}

 

 

⛳️ 참고 자료

https://twpower.github.io/72-implement-graph-in-cpp

https://www.youtube.com/watch?v=fVcKN42YXXI