그래프(Graph)를 표현하는 방법에 대하여

▶그래프

---

그래프는 정점들의 집합 V와 간선들의 집합 E로 이루어진 자료구조입니다.

▶그래프 표현 방법

---

그래프를 표현하는 방법으로 인접 행렬과 인접 리스트가 있습니다.

정점의 개수가 N개인 그래프를 인접 행렬로 표현하려면 (N+1) x (N+1) 크기의 2차원 배열이 필요합니다.

무 방향 그래프인 경우에 1번 정점과 2번 정점이 연결되어있다면 (1,2)와 (2,1)에 모두 1을 저장해 두 정점이 연결되었음을 표현합니다. 만약 방향 그래프인 경우에 1번 정점에서 2번 정점으로 화살표가 그려져있다면 (1,2)에만 1을 저장하는 방식입니다.

int adj[5][5] = {0,};

// 1번 정점과 2번 정점이 연결된 경우

adj[1][2] = 1;
adj[2][1] = 1;

정점의 개수가 N개인 그래프를 인접 리스트로 표현하려면 N+1 크기의 1차원 벡터가 필요합니다.

각 정점에서 연결되어있는 정점들의 번호를 동적으로 할당하여 저장하는 방식으로 표현합니다.

vector<int> adj[5];

// 1번 정점과 2번 정점이 연결된 경우

adj[1].push_back(2);
adj[2].push_back(1);