글 읽기 - c언어 그래프 구현 메모리 할당관련 질문!

sc3289 2년 전 0

윤성우 저자 자료구조 책을 공부하면서 그래프를 보고 있는데

처음 그래프를 구현할 때 이제 vertex들을 위한 node 배열 동적메모리 할당을 해주고

edge 들을 표현하면서 이제 vertex마다 node들을 이어붙이는게 그래프를 구현하는거라고 이해했습니다.

vertex에 node들 이어붙이는 과정에서도 동적메모리 할당을 이용하는데

어째서 프로그램 종료 전 메모리 할당을 vertex에 한해서만 풀어주는건지 잘 모르겠습니다. (77번째 줄 free(g);)

edge들을 표현할때도 동적메모리를 할당했으니 각 vertex 배열 index마다 edge들까지도 메모리 할당을 풀어줘야 하는거 아닌가요?

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 50

typedef struct GraphNode
{
	int vertex;
	struct GraphNode* link;
}GraphNode;

typedef struct GraphType
{
	int n;
	GraphNode* adj_list[MAX_VERTICES];
}GraphType;


void init(GraphType* g)
{
	int v;
	g->n = 0;
	for (v = 0; v < MAX_VERTICES; v++)
		g->adj_list[v] = NULL;
}

void insert_vertex(GraphType * g, int v)
{
	g->n++;
}

void insert_edge(GraphType * g, int u, int v)
{
	GraphNode* node = (GraphNode*)malloc(sizeof(GraphNode));
	node->vertex = v;
    node->link = g->adj_list[u];
    g->adj_list[u] = node;
}


void print_adj_list(GraphType * g)
{
	for (int i = 0; i < g->n; i++)
	{
		GraphNode* p = g->adj_list[i];
		printf("정점 %d의 인접 리스트", i);
		while (p != NULL) {
			printf("-> %d", p->vertex);
			p = p->link;
		}
		printf("\n");
	}
}

int main()
{
	GraphType* g;
	g = (GraphType*)malloc(sizeof(GraphType));
	init(g);
	for (int i = 0; i < 6; i++)
        insert_vertex(g, i);
	insert_edge(g, 0, 1);
	insert_edge(g, 1, 0);
	insert_edge(g, 0, 2);
	insert_edge(g, 2, 0);
	insert_edge(g, 0, 3);
	insert_edge(g, 3, 0);
	insert_edge(g, 0, 5);
	insert_edge(g, 5, 0);
	insert_edge(g, 1, 2);
	insert_edge(g, 2, 1);
	insert_edge(g, 2, 5);
	insert_edge(g, 5, 2);
	insert_edge(g, 3, 4);
	insert_edge(g, 4, 3);
	print_adj_list(g);
	free(g);
	return 0;
}

bupjae 2년 전 1

그래프를 만들 때 insert_edge 에서 각각의 edge 마다 동적 할당을 하고 있으므로

그래프를 해제할 때에도 각각의 edge 마다 동적 할당 해제를 해야 합니다.

77번째 줄과 같이 그래프 본체만 free 하면, edge 가 할당받은 메모리는 (프로그램을 종료하기 전에는) 아무도 사용할 수 없습니다.

이 프로그램은 free 를 하자마자 프로그램이 종료되며, 종료된 프로그램이 사용했던 메모리는 OS 가 모두 청소를 하기 때문에 문제점이 눈에 보이지 않을 뿐입니다.

sc3289 2년 전 0

역시.. free를 각 edge들도 해줘야 하는군요 감사합니다!

교재에서도 저러니 뭔가 싶었습니다..

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

c언어 그래프 구현 메모리 할당관련 질문!

sc3289 2년 전 0

bupjae 2년 전 1

sc3289 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말