[그래프의 표현] 인접 행렬
인접행렬 그래프의 간선과 접점의 관계를 행렬(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 대신에 가중치값을 넣어주면된다. 그래서 나온 행렬은 아래와같다. 이제 이 인접행렬을 어떻게 사용하는지에 대한 예시를 ..
2016. 3. 31.
