CH 14-2 인접리스트 기반의 그래프 구현

14-2. 인접 리스트 기반의 그래프 구현

이번시간에는 인접리스트 기반으로 그래프를 구현해보겠다. 인접리스트는 연결리스트를 기반으로 한다.

복습차원에서 저번시간에 배운걸 다시 살펴보면,

위는 무방향 그래프의 인접리스트 기반 구현법이다.

위는 유향 그래프의 인접리스트 기반 구현법이다.

• 위 두 그림을 보면… 유향이든 무향이든 실제 메모리 레벨에서 구현은 다른건 없고, 그저 무향의 두배의 메모리를 써서 반대 방향으로 연결만 해주면 유향그래프가 된다는 사실을 알 수 있다. 즉 무향 유향 따로따로 구현하는게 아니라, 하나의 코드만 구현해주면 무향과 유향 다 표현할 수 있다.

앞서 구현했던 연결리스트를 그대로 가져다가 그래프 구현에 활용하면… 사실 크게 구현할 건 많이 없다.

일단 헤더를 보자.

#include "DLinkedList.h" //use DmyLList 

// 정점 이름 상수화 (enum이용)
enum {A, B, C, D, E, F, G, H ,I, J};

typedef struct _ual
{
	int numV; //정점 수
	int numE; //간선 수
	List* adjList; //간선의 정보(어떤 정점과 연결되어있는지)
} ALGraph;

더미연결리스트를 가져다가 그대로 활용한다. 정점이름은 따로 상수화해서 관리한다. 따라서 정점의 정보는 ALGraph구조체에 들어가지 않는다.

//그래프 초기화 함수
void GraphInit(ALGraph* pg, int nv);

//그래프 리소스 해제 함수
void GraphDestory(ALGraph* pg);

//간선 추가 함수
void AddEdge(ALGraph* pg, int fromV, int toV);

//간선 정보 출력 함수
void ShowGraphEdgeInfo(ALGraph* pg);