[C] 그래프

그래프란객체 간의 관계를 표현하는 비선형 자료구조이며, 다 대 다의 관계를 표현한다. C 언어에서의 그래프는 다른 언어 및 일반적으로 사용하는 그래프의 개념과는 다름을 유의해야한다. 그래프는 주로 G 로 나타내며 G=(V,E) 와 같이 V 와 E의 정보로 정의된다. V 는 그래프로 표현의 대상이 되는 관계, 즉 정점을 의미하며 E는 정점 간의 관계를 의미하는 간선을 표현한다. 그래프의 종류는 간선이 방향을 가지느냐 아니냐에 따라 방향그래프와 무방향그래프로 분류할 수 있다. 무방향그래프는 두 정점을 연결하는 간선에 방향성이 없는 그래프로 (V1, V2) 와 같이 표현하며 방향그래프는 간선에 방향성이 존재하여 정점 간의 접근성이 제한되는 것으로 <V1, V2> 와 같이 표현한다. 경로란 정점 V_i 에서 V_j로 갈때 만나는 모든 정점들을 순서대로 나열한 리스트이며 그때의 간선 수를 경로 길이라고 한다.

그래프를 구현하는 방법에는 2차원 배열을 사용한 인접행렬방법과 연결 리스트를 사용한 인접리스크방법이 있으며 이번 글에서는 인접행렬방법을 소개한다. 인접행렬방법은 대상 정점 수 n에 대해 n x n 정방행렬을 구성하여 V_i 에서 V_j로의 간선 유무를 각각 행과 열 인덱스를 참조하여 1/0을 할당한다. 대각 성분은 정점 자기자신을 의미하므로 항상 0이며 무방향 그래프는 방향성이 없으므로 대칭행렬을 만들게 된다.

먼 훗날 graph 개념과 관련된 그림들이 업데이트 될 예정임