[알고리즘] 그래프 표현 방법

그래프를 표현하는 것은 정점과 연결된 정점을 표현하는 것이다.

 

1. 연결된 정점의 숫자만 표시

vector<vector<int>> adjacent;
adjacent[0] = {1,2};
adjacent[1] = {2};
adajcent[2] = {0,1};

메모리 낭비가 적다는 장점이 있지만, 해당 정점이 몇번 정점과 연결되어 있는지 찾으려면 오래걸림(std::find..)

 

 

2.  연결된 정점은 true, 아니면 false로 표시

vector<vector<bool>> adjacent(3,vector<bool>(3,false)); //기본값 false로 설정
adjacent[0][1] = true;
adjacent[0][2] = true;
adjacent[1][2] = true;
adjacent[2][0] = true;
adjacent[2][1] = true;

메모리 낭비가 좀 있지만 , 해당 정점이 몇번 정점과 연결되어 있는지 찾는 것이 빠르다.(간선 많은 경우 이점)

실전에서 2번을 많이 사용한다고 한다.