Graph - 인접 행렬 그래프

이번 시간에는 그래프 소스에 대해 알아본다.

행렬을 이용하여 구현하는 방법과 리스트를 이용하여 구현하는 방법 2가지 인데,

먼저 행렬을 이용하여 구현한 인접 행렬 그래프를 알아본다.

그래프의 관련 내용은 검색하면 금방 알아 볼 수 있기 때문에 여기서는 설명 하지 않는다.

먼저 인접행렬그래프의 헤더파일을 살펴보자.

1. arraygraph.h

1. #ifndef _ARRAYGRAPH_H_
2. #define _ARRAYGRAPH_H_
3.  
4. #define UNDIRECTION 0       //무방향 그래프
5. #define DIRECTION 1         //방향 그래프
6. #define SUCCESS 1          
7. #define FAIL 0
8. #define USE 1
9. #define NOT_USE 0
10.  
11.  
12. typedef struct ArrayGraphType{
13.     int maxVertexCount;         //최대 노드 수
14.     int currentVertexCount;     //현재 노드 수
15.     int graphtype;              //그래프의 타입(방향성, 무방향성)
16.     int **ppAdjEdge;            //간선 저장 위한 2차원 배열
17.     int *pVertex;               //노드 저장을 위한 1차원 배열
18. }ArrayGraph;
19.  
20. ArrayGraph* createUndirectGraph(int maxVertexCount);                //무방향성 그래프 생성
21. ArrayGraph* createDirectGraph(int maxVertexCount);                  //방향성 그래프 생성
22. void deleteArrayGraph(ArrayGraph* pGraph);                          //그래프 제거
23. int addVertexArrayGraph(ArrayGraph* pGraph, int vertexID);          //노드 생성
24. int removeVertexArrayGraph(ArrayGraph* pGraph, int removeID);       //노드 삭제
25. int addEdgeArrayGraph(ArrayGraph* pGraph, int fromID, int toID, int weight);    //간선 생성
26. int removeEdgeArrayGraph(ArrayGraph* pGraph, int fromID, int toID);             //간선 제거
27. void displayArrayGraph(ArrayGraph* pGraph);                         //그래프 출력
28.  
29. #endif

코드리딩 한번만 해도, 어떻게 구성되어 있는지 쉽게 파악 할 수 있을 것이다.

다음은 하나하나씩 확인해 보자.

2. arraygraph.c

1) ArrayGraph* createUndirectGraph(int maxVertexCount)

위의 함수는 무방향 그래프를 생성하기 위한 함수이다. 

함수의 입력인자는 최대 몇개의 노드를 생성할 지에 대한 정수형 데이터이다.

1. ArrayGraph* createUndirectGraph(int maxVertexCount)
2. {
3.     ArrayGraph *pReturn = NULL;
4.     int i,j;
5.  
6.     //노드 갯수 에러 검사
7.     if(maxVertexCount <= 0)
8.     {
9.         printf("maxCertexCount error\n");
10.         return NULL;
11.     }
12.  
13.     //그래프 구조체 동적할당
14.     pReturn = (ArrayGraph *)malloc(sizeof(ArrayGraph));
15.  
16.     //동적할당 에러 검사
17.     if(pReturn==NULL)
18.     {
19.         printf("memory allocation error\n");
20.         return NULL;
21.     }
22.    
23.     pReturn->maxVertexCount=maxVertexCount;     //최대 노드 개수 입력
24.     pReturn->currentVertexCount=0;              //현재 노드 개수 0 입력
25.     pReturn->graphtype = UNDIRECTION;           //무방향성 그래프
26.  
27.     //최대 노드 개수만큼 동적할당
28.     pReturn->pVertex = (int *)malloc(sizeof(int)*maxVertexCount);
29.     //동적할당 에러 검사
30.     if(pReturn->pVertex==NULL)
31.     {
32.         free(pReturn);
33.         printf("Don't create ArrayGraph - memory allocation error\n");
34.         return NULL;
35.     }
36.    
37.     //최대 노드 개수만큼 필요한 간선 수 동적할당
38.     pReturn->ppAdjEdge = (int **)malloc(sizeof(int*)*maxVertexCount);
39.     //동적할당 에러 검사
40.     if(pReturn->ppAdjEdge==NULL)
41.     {
42.         free(pReturn->pVertex);
43.         free(pReturn);
44.         printf("memory allocation error\n");
45.         return NULL;
46.     }
47.    
48.     //최대 노드 수 만큼 간선의 데이터 입력할 공간 할당
49.     for(i=0;i<maxVertexCount;i++)
50.     {
51.         pReturn->ppAdjEdge[i] = (int *)malloc(sizeof(int)*maxVertexCount);
52.        
53.         //pReturn->ppAdjEdge[i]의 메모리 할당 실패 예외 처리
54.         if(pReturn->ppAdjEdge[i]==NULL)
55.         {
56.             for(j=0;j<i-1;j++)
57.                 free(pReturn->ppAdjEdge[j]); //이전 할당 메모리 해제
58.  
59.             //남은 메모리 전체 해제
60.             free(pReturn->ppAdjEdge);
61.             free(pReturn->pVertex);
62.             free(pReturn);
63.  
64.             return NULL;
65.         }
66.     }
67.  
68.     //그래프의 노드 초기화
69.     memset(pReturn->pVertex, 0, sizeof(int)*maxVertexCount);
70.     for(i=0;i<maxVertexCount;i++)
71.         memset(pReturn->ppAdjEdge[i], 0, sizeof(int)*maxVertexCount);
72.  
73.     return pReturn;
74.    
75. }

2) ArrayGraph* createDirectGraph(int maxVertexCount)

아래 함수는 방향성그래프 생성을 위한 그래프이다. 내부를 확인하면, 일단 무방향성 그래프를 생성하고,

거기서 반환된 그래프 구조체의 데이터 중 그래프 타입을 방향성으로 변경하여 반환한다.

1. ArrayGraph* createDirectGraph(int maxVertexCount)
2. {
3.     ArrayGraph* pReturn = createUndirectGraph(maxVertexCount);
4.  
5.     if(pReturn==NULL)
6.         return NULL;
7.  
8.     pReturn->graphtype = DIRECTION;
9.  
10.     return pReturn;
11. }

3) void deleteArrayGraph(ArrayGraph* pGraph)

생성한 인접행렬그래프를 제거하기 위한 코드이다.

1. void deleteArrayGraph(ArrayGraph* pGraph)
2. {
3.     int i,j;
4.     if(pGraph == NULL)
5.         return;
6.  
7.     for(i=0;i<pGraph->maxVertexCount;i++)
8.     {
9.         if(pGraph->ppAdjEdge[i]!=NULL)
10.         {
11.             free(pGraph->ppAdjEdge[i]);
12.         }
13.     }
14.     if(pGraph->ppAdjEdge!=NULL) free(pGraph->ppAdjEdge);
15.     if(pGraph->pVertex!=NULL) free(pGraph->pVertex);
16.     free(pGraph);
17. }

4) int addVertexArrayGraph(ArrayGraph* pGraph, int vertexID);

노드를 추가하는 기능을 하는 함수이다. 그래프 구조체 포인터와, 추가할 노드의 인덱스를 입력한다.

그래프 구조체 포인터의 상태, 최대노드갯수, 추가하고픈 노드가 이미 있는지 등을 확인하고 생성한다.

1. int addVertexArrayGraph(ArrayGraph* pGraph, int vertexID)
2. {
3.     if(pGraph==NULL)
4.     {
5.         return FAIL;
6.     }
7.  
8.     if(vertexID>pGraph->maxVertexCount)
9.         return FAIL;
10.  
11.     if(pGraph->pVertex[vertexID]==USE)
12.         return FAIL;
13.  
14.     pGraph->pVertex[vertexID] = USE;
15.     pGraph->currentVertexCount++;
16.  
17.     return SUCCESS;
18. }

5) int removeVertexArrayGraph(ArrayGraph* pGraph, int removeID)

-원하는 노드를 제거하기 위한 함수이다. 이 때 주의해야할 점은 노드 뿐만 아니라, 노드에 연결된

모든 간선도 제거해야 한다는 것이다. 아래 빨간색으로 표현된 코드 부분이다.

1. int removeVertexArrayGraph(ArrayGraph* pGraph, int removeID)
2. {
3.     int i;
4.  
5.     if(pGraph==NULL)
6.         return FAIL;
7.     if(pGraph->pVertex[removeID]==NOT_USE)
8.         return FAIL;
9.     if(removeID>pGraph->maxVertexCount)
10.         return FAIL;
11.  
12.     for(i=0;i<pGraph->maxVertexCount;i++)
13.     {
14.         removeEdgeArrayGraph(pGraph, removeID, i);
15.         removeEdgeArrayGraph(pGraph, i, removeID);
16.     }
17.  
18.     pGraph->pVertex[removeID] = NOT_USE;
19.     pGraph->currentVertexCount--;
20.  
21.     return SUCCESS;
22. }

6) int addEdgeArrayGraph(ArrayGraph* pGraph, int fromID, int toID, int weight);

- 간선을 추가하는 함수

간선 생성을 원하는 노드에서 노드까지를 입력하고, 가중치를 입력한다.

그리고 그래프가 무방향성이라면 대칭되는 간선도 동일한 값을 입력하여 준다.

1. int addEdgeArrayGraph(ArrayGraph* pGraph, int fromID, int toID, int weight)
2. {
3.     if(pGraph==NULL)
4.         return FAIL;
5.     if(fromID>pGraph->maxVertexCount || toID>pGraph->maxVertexCount)
6.         return FAIL;
7.     if(pGraph->pVertex[fromID]==NOT_USE||pGraph->pVertex[toID]==NOT_USE)
8.         return FAIL;
9.     if( weight<=0)
10.         return FAIL;
11.  
12.     pGraph->ppAdjEdge[fromID][toID] = weight;
13.  
14.     if(pGraph->graphtype==UNDIRECTION)
15.         pGraph->ppAdjEdge[toID][fromID] = weight;
16. }

7) int removeEdgeArrayGraph(ArrayGraph* pGraph, int fromID, int toID);

-간선을 제거하기 위한 함수.

간선 제거를 위해 가중치를 0으로 초기화 하고, 무방향성이라면 동일하게 대칭되는 곳 또한 0으로 초기화!

1. int removeEdgeArrayGraph(ArrayGraph* pGraph, int fromID, int toID)
2. {
3.     if(pGraph==NULL)
4.         return FAIL;
5.     if(fromID>pGraph->maxVertexCount || toID>pGraph->maxVertexCount)
6.         return FAIL;
7.     if(pGraph->pVertex[fromID]==NOT_USE||pGraph->pVertex[toID]==NOT_USE)
8.         return FAIL;
9.  
10.     pGraph->ppAdjEdge[fromID][toID] = 0;
11.     if(pGraph->graphtype==UNDIRECTION)
12.         pGraph->ppAdjEdge[toID][fromID] = 0;
13.  
14.     return SUCCESS;
15. }

8) void displayArrayGraph(ArrayGraph* pGraph)

-현재 그래프 상태를 출력하는 함수

void displayArrayGraph(ArrayGraph* pGraph)

{

int i,j;

if(pGraph==NULL)

return;

if(pGraph->graphtype==UNDIRECTION) printf("Graph : UNDIRECTION\n");

if(pGraph->graphtype==DIRECTION) printf("Graph : DIRECTION\n");

for(i=0;i<pGraph->maxVertexCount;i++)

{

for(j=0;j<pGraph->maxVertexCount;j++)

printf("%d ", pGraph->ppAdjEdge[i][j]);

printf("\n");

}

}

자, 그럼 위의 코드를 이용하여 테스트를 하여 보자.

아래는 예제소스이다.

1. #include<stdio.h>
2. #include "arraygraph.h"
3.  
4. int main()
5. {
6.     ArrayGraph* pGraph = createUndirectGraph(6);
7.     int i;
8.  
9.     for(i=0;i<6;i++)
10.         addVertexArrayGraph(pGraph, i);
11.  
12.     addEdgeArrayGraph(pGraph, 0, 3, 1);
13.     addEdgeArrayGraph(pGraph, 1, 3, 1);
14.     addEdgeArrayGraph(pGraph, 2, 3, 2);
15.     addEdgeArrayGraph(pGraph, 5, 2, 5);
16.     addEdgeArrayGraph(pGraph, 0, 1, 4);
17.     addEdgeArrayGraph(pGraph, 1, 3, 2);
18.     addEdgeArrayGraph(pGraph, 4, 5, 7);
19.     addEdgeArrayGraph(pGraph, 5, 2, 2);
20.     addEdgeArrayGraph(pGraph, 3, 3, 1);
21.     addEdgeArrayGraph(pGraph, 4, 1, 7);
22.     addEdgeArrayGraph(pGraph, 2, 1, 4);
23.     displayArrayGraph(pGraph);
24.     deleteArrayGraph(pGraph);
25.    
26. }

결과는 아래와 같다!! 확인하여 보자.

위의 소스들이 정확히 올바른 소스라고는 할 수 없다. 하지만 어느 정도 참고는 할 수 있길 !!!

다음 시간에는 인접리스트를 이용하여 구현하여 보자. 검증 또한 여러분의 몫!

야밤에 짧은 시간내에 코딩하려니 힘드네요....

기본 소스는 공유하겠습니다 !

arraygraph.c

arraygraph.h

main.c