5. 그래프 (Graph) - 인접리스트법

1. 개요

[그림 1] 인접리스트로 표현한 그래프

이전에는 인접행렬이 아닌 링크드리스트를 이용하여 인접리스트로 그래프를 표현하는 방법에 대해 알아보겠다.

인접행렬이 최소그래프에 있어서 메모리 낭비가 심했다면, 인접리스트는 정점의 갯수, 간선의 갯수만큼 메모리를 할당하므로 메모리적인 측면에 있어 인접행렬법보다 좋다. 따라서 최소그래프 표현에 적합하다.

그림과 같이 각 정점에서 간선으로 연결된 정점들을 리스트 형태로 연결해 놓는 기법이다.

(※ 인접리스트법도 당연히 무방향 그래프에서의 대칭성을 고려하여 코드를 구현하여야 한다)

---

2. 그래프 구현

1. 구조체 및 함수 선언 

typedef struct _node { int vertex; struct _node *next; }Node; typedef struct { Node *graph[MAX_VERTEX]; /* 인접 리스트 표기 배열 - Node 포인터 배열 */ int vertexCnt; /* 정점 개수 */ int edgeCnt; /* 간선 개수 */ }GraphList; void initGraph_List(GraphList *g, char *fileName); /* 데이터파일에서 그래프의 정점과 간선 정보를 입력 받아 그래프를 인접 리스트법으로 초기화하는 함수 */ void outputGraph_List(GraphList *g); /* 그래프내의 정점과 간선의 관계를 인접 리스트 형태로 출력 */ int addNode(GraphList *g, int vNum1, int vNum2); /* 두 정점의 관계를 리스트에 등록함 */ void destroyGraph_List(GraphList *g); /* 그래프내의 정점 노드 모두 삭제 */  

노드구조체 , 인접리스트 그래프 구조체를 선언

인접리스트 그래프 구조체에는 동적할당 시켜줄 최대정점갯수만큼의 방을 가진 2차원 배열을 선언한다. (헤드노드)

 2. 인접리스트 초기화 

void initGraph_List(GraphList *g, char *fileName) { char vertex[3]; /* 간선정보 입력을 위한 공간 "AB" 형태의 데이터 저장 char 배열 */ int i,j,k; /* iterator */ FILE *fp; /* 그래프 정보 저장 파일의 파일포인터 */ fp=fopen(fileName, "rt"); assert(fp!=NULL); fscanf(fp, "%d %d\n", &g->vertexCnt, &g->edgeCnt); /* 정점과 간선의 개수를 읽기 */ /* 정점의 개수에 맞춰 인접 리스트 영역 초기화 */ for(i=0; i<g->vertexCnt; ++i) g->graph[i] = NULL; /* 무방향 그래프에서의 대칭성(Symmetry) 고려한 초기화 표기 */ for(k=0; k<g->edgeCnt; ++k) { fscanf(fp, "%s\n",vertex); i=vertex[0]-'A'; /* 정점의 이름을 숫자화 'B'-'A' => 1의 형식으로 변환*/ j=vertex[1]-'A'; /* 정점의 이름을 숫자화 */ assert( addNode(g, i, j) != FALSE); } fclose(fp); }  

인접행렬때와 마찬가지로 파일을 불러와 인접리스트를 초기화 시킨다. 다른점은 배열에 해당 값들을 넣지않고 addNode()함수를 통해 해당 값을 리스트에 넣어준다.

 3. 노드 추가 

int addNode(GraphList *g, int vNum1, int vNum2) { Node *newNode; newNode = (Node *) malloc(sizeof(Node)); /* 새 간선 정보 노드 생성 */ if(newNode == NULL) return FALSE; newNode->next = g->graph[vNum1]; newNode->vertex = vNum2; g->graph[vNum1] = newNode; /* 새로운 간선 정보 노드를 인접 리스트에 추가 */ /* 무방향 그래프에서의 대칭성(Symmetry) 고려하여 역 방향에 간선도 추가로 초기화 */ newNode = (Node *) malloc(sizeof(Node)); /* 새 간선 정보 노드 생성 */ if(newNode == NULL) { free(g->graph[vNum1]); return FALSE; } newNode->next = g->graph[vNum2]; newNode->vertex = vNum1; g->graph[vNum2] = newNode; /* 새로운 간선 정보 노드를 인접 리스트에 추가 */ return TRUE; }  

두 정점의 관계를 리스트에 등록하는 함수로 전달인자로는 이어줄 정점 2개와 그래프 정보 구조체의 주소를 받는다.

새로운 간선 정보 노드를 메모리 할당해주고 그 새 노드의 next에 인접리스트 그래프 구조체 헤드노드의 첫번째 전달인자 방을 넣어주고

그 노드의 정점정보에 두번째 전달인자 정점을 넣어준다 ( 이름 새기는 것 ) 그리고 헤드노드의 첫번째 전달인자 방이 가리키는 곳을 새로 할당한 노드로 바꿔준다.

무방향 그래프에서의 대칭성을 고려하여 역 방향도 위와 같은 방법으로 초기화시켜준다.

 4. 그래프 출력 

void outputGraph_List(GraphList *g) { int i; /* iterator */ Node *now; for(i=0; i<g->vertexCnt; ++i) { printf("%3c : ", 'A' + i); for(now = g->graph[i]; now != NULL; now = now->next) printf("%3c -> ", 'A' + now->vertex); printf("\b\b\b "); NEWL; } }  

리스트의 순서대로 출력을 한다.

 5. 그래프 소멸 

void destroyGraph_List(GraphList *g) { int i; /* iterator */ Node *now, *next; for(i=0; i<g->vertexCnt; ++i) { now = g->graph[i]; while(now != NULL) { next = now->next; free(now); now=next; } } }

헤드노드를 모두 메모리 해제시켜준다.