인접행렬

인접 행렬

인접 : 연결되어있다.

인접 행렬은 그래프의 정점과 정점이 연결되어 있는지 없는지 나타내는 행렬이다.

인접행렬로 나타낼 무방향(양방향) 그래프를 준비한다.

행렬을 하나 그린다.

A 와 B 가 연결되어 있으므로 True 로 표시한다. (1 : True, 0 : False);

자기 자신을 향하는 간선이 있기 때문에 1행 1열에 True 를 넣는다.

반복해서 채워준다. 빈 곳(간선이 없는 곳)은 False 로 채워준다.

int a[4][4] = {
  {1, 1, 1, 0},
  {1, 0, 1, 1},
  {1, 1, 0, 0},
  {0, 1, 0, 0}
};

행렬의 이름을 a 라고 하면 a[from][to]라는 2차원 배열로 표현할 수 있음을 알 수 있다.

위 예시는 무방향 그래프를 예로 들었지만 단방향 그래프와 적용방법이 동일하다.
from 과 to 가 표시되어 있으므로 규칙에 맞게 단방향 그래프의 간선의 값을 행렬에 채워넣으면 된다.

Reference

10주완성 C++ 코딩테스트; 2-4
Graph (그래프)