열혈 자료구조 - 14.2 인접 리스트 기반의 그래프 구현

그래프의 구조체

enum {A,B,C,D,E};		// INIT에서 전달하는 정점의 수만큼만 사용

typedef struct _ual
{
	int numV;   	// 정점의 수
	int numE;   	// 간선의 수
	List* adjList;  // 간선의 정보를 가지는 연결리스트
} ALGraph;

 

그래프의 구현

- 초기화 : 인자로 정점의 수를 전달

void GraphInit(ALGraph* pg, int nv)
{
	int i;	

	pg->adjList = (List*)malloc(sizeof(List)*nv);		// 정점의 수만큼 연결 리스트를 생성
	pg->numV = nv;
	pg->numE = 0;     // 초기의 간선 수는 0개

	for(i=0; i<nv; i++)
	{
		ListInit(&(pg->adjList[i]));		// 각 연결 리스트를 초기화
	}
}

- 소멸

void GraphDestroy(ALGraph* pg)
{
	if(pg->adjList != NULL) {
		free(pg->adjList);
        }
}

- 간선 추가

void AddEdge(ALGraph * pg, int fromV, int toV)
{
	LInsert(&(pg->adjList[fromV]), toV);
	LInsert(&(pg->adjList[toV]), fromV);	// 무방향일 경우 두 정점에 모두 추가
	pg->numE += 1;
}

- 간선 정보 출력 : 각 연결 리스트의 정보를 모두 출력

void ShowGraphEdgeInfo(ALGraph * pg)
{
	int i;
	int vx;

	for(i=0; i<pg->numV; i++)
	{
		printf("%c와 연결된 정점: ", i + 65);
		
		if(LFirst(&(pg->adjList[i]), &vx))
		{
			printf("%c ", vx + 65);
			
                        while(LNext(&(pg->adjList[i]), &vx)) {
				printf("%c ", vx + 65);		// 문자 형태로 출력하기 위해 65를 더함
                        }
		}
		printf("\n");
	}
}

 

int main(void)
{
	ALGraph graph;
	GraphInit(&graph, 5);     // A, B, C, D, E의 정점 생성

	AddEdge(&graph, A, B);
	AddEdge(&graph, A, D);
	AddEdge(&graph, B, C);
	AddEdge(&graph, C, D);
	AddEdge(&graph, D, E);
	AddEdge(&graph, E, A);

	ShowGraphEdgeInfo(&graph);

	GraphDestroy(&graph);
	return 0;
}