[Data Structure] 그래프 표현 방법 1) 인접 행렬

그래프의 표현방법 인접 행렬(Adjacency Matrix) : 2차원 배열을 사용 인접 리스트(Adjacency List) : 연결 리스트를 사용 인접 행렬 - 정점의 수 n개에 대해 n×n의 2차원 배열로 구성 - 간선 (i, j)가 그래프에 존재하면 m[i][j] = 1 - 간선 (i, j)가 그래프에 없으면 m[i][j] = 0 - n개의 정점이 존재하면 n²개의 메모리가 필요 → 메모리 낭비가 크다 - 간선이 매우 많은 밀집 그래프에는 적합하다 - 간선이 적은 희소 그래프의 경우에는 메모리 낭비가 크므로 적합하지 않다 무방향 그래프 = 행렬이 대칭으로 구성 그래프 인접행렬 구현 #define MAX_VERTEX 50 typedef struct graph { int n; // 정점의 개수 coun..

2021.12.22