[알고리즘 C언어] 5.그래프(Graph), 5.1 인접 행렬로 방향성 없는 그래프

이번에는 그래프를 알아보기로 해요.

그래프는 정점과 간선으로 구성하는 자료구조예요.

그래프를 표현하는 방법은 여러가지가 있어요.

여기에서는 인접 행렬을 이용하는 방법과 연결리스트를 이용하는 방법을 알아볼게요.

5.1 인접 행렬로 방향성 없는그래프

방향성 없는 그래프는 정점 A에서 정점 B로 이동할 수 있으면 언제나 정정 B에서 정정 B로 이동할 수 있음을 보장하는 그래프예요.

방향성 없는 그래프를 표현하는 방법 중에 간단한 그래프에는 인접 행렬을 많이 사용해요.

인접 행렬로 방향성 없는 그래프를 표현하면 좌상단에서 우하단으로 이어지는 대각선에 대칭 형태죠.

방향성 없는 그래프와 인접 행렬
방향성 없는 그래프와 인접 행렬

먼저 그래프 형식을 정의하기로 해요.

인접 행렬로 그래프를 표현할 때 그래프에는 정점 개수와 인접 행렬이 필요하겠죠.

typedef struct{//그래프 형식 정의
     int vn; //정점 개수
     int **matrix;//그래프 인접 행렬
 }Graph;

여기에서는 그래프 생성, 소멸, 간선 추가, 이웃 정점을 보여주는 기능을 제공하기로 해요.

Graph *MakeGraph();//그래프 만들기
void DeleteGRaph(Graph *graph);//그래프 소멸
void AddEdge(Graph *graph, int start, int goal); //간선 추가
void ViewNeighbors(Graph *g);//이웃 정점 보여주기

그래프를 생성하는 기능을 먼저 구현하죠.

그래프 메모리를 동적 할당한 후에 정점 개수와 인접 행렬의 메트릭스 메모리를 할당하세요.

그리고 매트릭스의 모든 행의 메모리를 할당하고 0으로 초기화하세요.

Graph *NewGraph(int max_vertex)
 {
     int i = 0;
     Graph *graph = (Graph *)malloc(sizeof(Graph));//그래프 메모리 동적 할당
     graph->vn = max_vertex;//최대 정점 개수 설정
     graph->matrix = (int **)malloc(sizeof(int *)*max_vertex);//매트릭스 메모리 할당
     for (i = 0; i < max_vertex; i++)
     {
         graph->matrix[i] = (int *)malloc(sizeof(int)*max_vertex);//매크릭스 [i-row] 메모리 할당
         memset(graph->matrix[i], 0, sizeof(int)*max_vertex);//메모리 0으로 초기화
     }
     return graph;
 }

그래프를 소멸하는 함수를 작성하죠.

생성에서 할당했던 모든 것을 소멸해야겠죠.

먼저 모든 행을 위한 메모리를 해제하고 매트릭스를 해제하세요.

그리고 그래프 메모리를 해제하세요.

 void DeleteGRaph(Graph *graph)
 {
     int i = 0;
     
     for (i = 0; i < graph->vn; i++)//최대 정점 개수만큼
     {
         free(graph->matrix[i]);//매트릭스 [i-row]  메모리 소멸
     }
     free(graph->matrix);//매트릭스 메모리 해제
     free(graph);//그래프 메모리 해제
 }

그래프에 정점을 추가하는 기능에서는 매크릭스의 start행 goal열과 goal행 start열을 1로 설정하세요.

 void AddEdge(Graph *graph, int start, int goal)
 {
     graph->matrix[start][goal] = 1;//간선 설정
     graph->matrix[goal][start] = 1;//간선 설정
 }

모든 이웃 정보를 보여주는 기능은 특정 정점의 이웃 정보를 보여주는 기능을 반복해서 호출하기로 해요.

void ViewNeighbor(Graph *g,int vt);
 void ViewNeighbors(Graph *g)
 {
     int i;     
     printf("=== 이웃 정점 ===\n");
     for (i = 0; i < g->vn; i++)
     {
         printf("%d의 이웃: ",i);
         ViewNeighbor(g,i);//i정점의 이웃 보여주기
         printf("\n");
     }     
 }

정점의 이웃 정보를 보여주는 기능에서는 vt행과 나머지 정점을 열로 하는 매크릭스가 참이면 출력하세요.

void ViewNeighbor(Graph *g,int vt)
 {
     int i;
     for (i = 0; i < g->vn; i++)
     {
         if(g->matrix[vt][i])
         {
             printf("%d ",i);
         }
     }
 }

C언어 알고리즘