Graph ( 비용 제외 )

<C언어로 쉽게 풀어쓴 자료구조 > 인용

 

1. 개념

그래프는 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조이다.

그래프의 대표적인 예시는 지도 이다.

지도에는 여러 개의 도시들이 있고, 도시들은 서로 연결되어 있다.

그래프 구조는 인접 행렬이나, 인접 리스트로 표현하고 처리할 수 있다.

그래프는 정점(Vertex)과 간선(Edge)들의 집합으로 구성된다.

수학적으로는, G = (V,E) 로 표시한다.

그래프의 대표적인 그림은 아래와 같다.

위의 그림은 대표적으로 무방향 그래프이다.

간선의 방향이 없기 때문.

 

2. 인접 리스트 방식 설명

우리가 만들려고 하는 그래프를 먼저 그려보자.

그리고, 위의 그래프의 모양을 아래와 같이 표현 가능하다.

여기서 그래프를 표현한 방식은 인접 리스트를 이용했다.

즉, 각 각의 정점에 인접한 정점들을 연결 리스트로 표시한 것이다.

각 연결 리스트의 노드들은 인접 정점을 저장하게 된다.

각 연결 리스트들은 헤드 포인터를 가지고 있고

이 헤드 포인터들은 하나의 배열로 구성되어 있다.

따라서 정점의 번호만 알면 이 번호를 배열의 인덱스로 하여

각 정점의 연결 리스트에 쉽게 접근 할 수 있다.

 

그리고 무방향 그래프로 간주해서 만들었다.

무방향 그래프의 경우 정점 A와 정점B를 연결하는 간선( A, B )는

정점A의 연결 리스트에 인접 정점B로써 한 번 표현되고,

정점B의 연결 리스트에 인접 정점A로 다시 한 번 표현된다.

 

그래프에 관련된 변수들을 하나의 구조체Graph에 정리를 먼저 하자.

그래프에 존재하는 정점의 갯수가 필요하며, 이름을 NumOfVertex라 하였다.

그리고 인접리스트를 이용하여 구현하려면 각 정점마다 하나의 연결 리스트가 필요하다.

따라서, 정점의 개수만큼의 헤드 포인터 배열이 필요하다.

포인터 배열의 이름을 pVertexList라 하였다. 그리고 자료형은 Vertex** 이다.

더블 포인터는 싱글 포인터를 가리킬 수 있다.

즉, pVertexList를 정점의 갯수만큼 동적할당을 하면, 각 배열의 공간이 Vertex를 가리키는 Vertex*가 된다.

그리고, 연결 리스트의 하나의 노드를 Vertex라는 구조체를 이용하여 표현했다.

 

3. 구현

< Graph.h >

< Graph.c >

< main.c >

< common.h >

프로그램 실행 결과

 

4. 헤더 파일 & 소스 파일

common.h

0.00MB

Graph.c

0.00MB

Graph.h

0.00MB

main.c

0.00MB