[C++] 그래프

그래프

• 그래프는 정점(node, vertex)와 간선(edge)로 구성된다.
• 사물들과의 연결 관계를 표현한다.

그래프로 표현 가능한 예

• 가족도
• 먹이사슬
• 지하철
• 교차로

그래프는 일상 생활에 비유한 문제가 많은데 코딩테스트 역시
비슷하므로 잘 학습하도록 하자📖

---

인접행렬

• 그래프의 연결 관계를 나타낸 행렬
• 인접행렬을 출발점(from)과 도착점(to)로 표현할 수 있다.

from/to 1 2 3 4 5
	1	0 0 1 1 0
	2	0 0 1 0 0
	3	0 0 0 0 1
	4	0 1 0 0 0
    5	0 0 0 1	0
    1번 노드에서 3, 4번으로 갈 수 있다.
    2번 노드에서 3번으로 갈 수 있다.
    ...

인접행렬 이해

노드 개수: N개
간선 개수: M개
인접행렬 공간은 N*N

ex)
노드 개수: 100,000개
간선 개수: 100,000개
N*N은 100억개, int는 4바이트
인접행렬 메모리 400억 바이트 필요 == 37Gb 상당히 크다...
-> 실질적으로 중요한 int의 개수 100,000개(=간선 개수)
-> 낭비되고 있는 int의 개수: 99억개

인접 행렬의 데이터를 줄일 수 있는 방법?

	0 0 1 1 0
    0 0 1 0 0
    0 0 0 1 1
    1 0 0 0 0
    0 0 0 1 0
    // 5*5 인접행렬에서 모든 노드들이 필요하지 않다.
    // 노드간 관계를 파악하기 위해서는 값이 1인 int만 필요!
	----------
	0 1 1 0 1
    0 0 1 0 1
    1 0 0 1 0
    0 1 1 0 0
    1 1 0 0 0
    ----------
    1 = [2, 3, 5]
    2 = [3, 5]
    3 = [1, 4]
    4 = [2, 3]
    5 = [1, 2]
    // from 과 to의 관계에 대한 행렬이 아니라
    // from에서 갈 수 있는 to를 바로 저장한다(압축)(=인접리스트)
    // int의 개수는 edge의 개수와 같다🙀

📌주의할점

무조건 인접리스트가 인접행렬보다 좋은 것이 아니다!

case.1: 특정 from에서 특정 to로 갈 수 있는가?

• 인접행렬 arr[1][4]
• 인접리스트 from[1]을 다 뒤져야한다.

case.2: 인접리스트에서 노드간 간선의 개수가 2개 이상일 때 인접행렬이 더 좋다

인접 리스트

• 엣지가 추가될 때마다 메모리를 추가해줘야한다.
• 배열을 쓰면 크기 관리가 어려우니깐 vector라는 친구를 사용한다.🤗
• vertor나 포인터를 사용하면 배열의 크기를 정확하게 쓸 수 있다.

문제 유형

1) 입력 정보를 토대로 인접 행렬 방식 저장

4 <- 노드 개수
6 <- 간선 개수
1 2 <- from to정보가 edge개수 만큼
2 3
2 4
3 4
4 2
4 3

#include <iostream>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int node, edge, arr[5][5] = { 0, };

	cin >> node >> edge;
	for (int i = 0; i < edge; i++) {
		int from, to;
		cin >> from >> to;
		arr[from][to] += 1;
		arr[to][from] += 1;	// 방향이 없는 경우
	}

	for (int from = 1; from <= node; from++) {
		for (int to = 1; to <= node; to++) {
			cout << arr[from][to] << " ";
		}
		cout << "\n";
	}

	return 0;
}

그래프의 연결 방식

• 단방향
• 무방향

그래프의 사용

• 저장
• 활용: 특정 노드에서 갈 수 있는 node들 찾기

5 8	// node, edge
1 2
1 5
2 4
2 3
3 4
3 5
4 1
4 3
2	// 출발점

	int cntNode, cntEdge, node, arr[100][100] = { 0, };
	vector<int> v[100];
	cin >> cntNode >> cntEdge;
    
	// 인접행렬
	for (int i = 1; i <= cntEdge; i++) {
		int from, to;
		cin >> from >> to;
		//v[from].push_back(to);
		arr[from][to] = 1;
	}
	cin >> node;
	
	for (int i = 1; i <= cntNode; i++) {
		if (arr[node][i] == 1)
			cout << i << "\n";
	}
    
	// 인접리스트
	for (int i = 1; i <= cntEdge; i++) {
		int from, to;
		cin >> from >> to;
		v[from].push_back(to);
		//arr[from][to] = 1;
	}
	cin >> node;
	
	for (int i = 0; i < v[node].size() ; i++) {
		cout << v[node][i];
	}
    
    return 0;

thank you o((⊙﹏⊙))o.