[그래프의 표현] 인접 행렬

인접행렬

그래프의 간선과 접점의 관계를 행렬(2차원 배열)로 표현하는 방식이다. 

 위의 그래프의 정점은 1,2,3,4,5,6 총 6개가 있고 연결된 간선은 1 - 2 , 1 - 5, 2 - 3 , 2 - 4, 2 - 5, 3 - 4, 4 -5 , 4- 6 으로 총 간선이 8개있다. 이 그래프를 인접행렬로 표현하자면 총 정점의 개수인 6인 6 x 6 행렬을 만들고 간선이 연결된 곳에 숫자를 집어넣는 것이다. 예를들어 행렬을 D[x][y] 라 하면 1 - 2 가 연결된 간선을 표현하기 위해서 D[1][2] = D[2][1] = 1을 넣어주어서 간선을 표시한다. 만약 간선의 가중치 가 있다면 1  대신에 가중치값을 넣어주면된다. 그래서 나온 행렬은 아래와같다. 

 이제 이 인접행렬을 어떻게 사용하는지에 대한 예시를 하나 들어보겠다. 만약 여기서 1 -> 6으로 가는 방법을 찾는것을 예를 들어보겠다. 

 위의 그림같이 차례대로 탐색 진행한다. 이미 지나간 정점과 간선을 표시하면서 끝까지 타고들어간다. 파고들다가 어디로도 갈 수 없으면 그 전 정점으로 가서 마저 탐색을 반복한다. 그래서 위의 그림처럼 1 -> 6번까지 진행하는 것을 볼 수 있다.