뇌를 자극하는 알고리즘 - 9. 그래프 : 인접리스트(Adjacency List)로 구현한 그래프

구현소스

AdjacencyListGraph.h

#ifndef ADJACENCY_LIST_GRAPH
#define ADJACENCY_LIST_GRAPH

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

enum VisitMode { Visited=1, NotVisited=0 };

typedef int Element;

typedef struct tagVertex
{
	Element Data;
	enum VisitMode Visited;

	int Index;
	struct tagVertex* Next; // 다음 정점을 가리키는 링크 - 정점의 집합
	struct tagEdge* AdjacencyList; // 정점이 가지는 간선들의 집합 
	// => 한 정점과 인접한 정점들을 찾을 수 있다. 

} Vertex;

typedef struct tagEdge
{
	int Weight; // 간선의 가중치 - 일단은 쓰이지 않음.
	struct tagEdge* Next; // 다음 간선을 가리키는 링크 - 간선의 집합

	Vertex* From; // 간선의 시작점
	Vertex* Target; // 간선의 끝점
}Edge;

typedef struct tagGraph
{
	Vertex* Vertices; // 링크드 리스트의 Head와 같은 역할. Next로 연결된 정점들의 시작점
	int VertexCount;  // 정점의 총 개수
} Graph;

Graph*	CreateGraph();
void	DestroyGraph(Graph *G);

Vertex*	CreateVertex(Element Data);
void	DestroyVertex(Vertex* V);

Edge*	CreateEdge(Vertex* From, Vertex* Target, int Weight);
void	DestroyEdge(Edge* E);

void	AddVertex(Graph* G, Vertex* V); // 그래프에 정점을 추가.
void	AddEdge(Vertex* V, Edge* E);    // 정점에 간선을 추가.
void	PrintGraph(Graph* G);


#endif

--------------------------------------------------------
AdjacencyListGraph.cpp

#include "AdjacencyListGraph.h"

Graph*	CreateGraph()
{

	Graph* NewGraph = (Graph*) malloc( sizeof(Graph) );

	NewGraph->Vertices = NULL;
	NewGraph->VertexCount = 0;

	return NewGraph;
}

Vertex*	CreateVertex(Element Data)
{
	Vertex* NewVertex = (Vertex*) malloc( sizeof(Vertex) );

	NewVertex->AdjacencyList = NULL;
	NewVertex->Next = NULL;

	NewVertex->Visited = NotVisited;
	NewVertex->Data = Data;
	NewVertex->Index = -1;	

	return NewVertex;
}

Edge*	CreateEdge(Vertex* From, Vertex* Target, int Weight)
{
	Edge* NewEdge = (Edge*) malloc( sizeof(Edge) );

	NewEdge->From = From;
	NewEdge->Target = Target;

	NewEdge->Next = NULL;
	NewEdge->Weight = 0;

	return NewEdge;
}

void	DestroyEdge(Edge* E)
{
	free(E);
}

void	DestroyVertex(Vertex* V)
{
	// 정점과 연관된 간선들을 일단 제거 한 후에
	while(V->AdjacencyList != NULL)
	{
		Edge* Edge = V->AdjacencyList->Next;
		DestroyEdge(V->AdjacencyList);
		V->AdjacencyList = Edge;

		// 정점이 가지는 간선 리스트를 처음부터 순차적으로 제거해 나간다.
	}

	// 정점을 제거
	free(V);
}

void	DestroyGraph(Graph *G)
{
	// 그래프를 제거 하기전 정점들을 우선적으로 제거
	// 정점이 가지는 간선들 -> 정점 -> .... 제거작업을 모든 정점에 수행해야 함.

	while(G->Vertices != NULL)
	{
		Vertex* Vertices = G->Vertices->Next;
		DestroyVertex(G->Vertices);
		G->Vertices = Vertices;
		
		// 정점들의 리스트를 처음부터 순차적으로 제거해 나감.
	}

	free(G);
}


// 그래프에 정점을 추가.
void	AddVertex(Graph* G, Vertex* V)
{
	Vertex* VertexList = G->Vertices ;

	if(VertexList == NULL) // 정점이 없는 경우
	{
		G->Vertices = V;
	}
	else	
	{ // 정점이 존재하는 경우 가장 마지막에 추가된 정점의 Next로 연결해야 한다.

		while( VertexList->Next != NULL)
			VertexList = VertexList->Next;

		VertexList->Next = V;
	}

	V->Index = (G->VertexCount)++;
	// Index 정점의 번호. 처음 그래프에 추가된 정점의 Index는 0이 된다.
}

// 정점에 간선을 추가.
void	AddEdge(Vertex* V, Edge* E)
{
	Edge* AdjacencyList = V->AdjacencyList ;

	if( AdjacencyList == NULL)
	{ // 정점에 간선이 존재하지 않는 경우
		V->AdjacencyList = E;
	}
	else
	{ // 간선이 이미 존재하는 경우 가장 마지막에 추가된 간선의 Next에 연결
		while( AdjacencyList->Next != NULL)
			AdjacencyList = AdjacencyList->Next;

		AdjacencyList->Next = E;
	}

}
void	PrintGraph(Graph* G)
{
	Vertex* V = G->Vertices;
	Edge*	E = NULL ;

	if( V == NULL) // 그래프에 정점이 없다면
		return ;

	while( V!=NULL )
	{
		E = V->AdjacencyList ;
		printf(" Data[%d] Vertex\n", V->Data );

		if( E == NULL)
		{ // 정점 V의 간선이 존재하지 않는 경우 다음 정점으로 이동
			V = V->Next;
			printf("\n");
			continue;
		}

		printf(" -- Adjacency List : \n");
		while( E!=NULL)
		{
			printf("    - Data[%d] Vertex[Weight:%d], ", E->Target->Data , E->Weight);
			E = E->Next ;
			printf("\n");
		}
		printf("\n");

		V = V->Next;
		
	}

	printf("\n");

}

--------------------------------------------------------
main.cpp

#include "AdjacencyListGraph.h"

int main()
{
	Graph* G = CreateGraph();
	Vertex* V[5];
	int i;

	for(i=0; i<5; i++)
	{
		V[i] = CreateVertex( i );
	} // 정점을 생성하고

	for(i=0; i<5; i++)
	{
		AddVertex(G, V[i]);
	} // 생성된 정점을 그래프에 추가

	AddEdge( V[0], CreateEdge(V[0], V[1], 0) );
	AddEdge( V[0], CreateEdge(V[0], V[2], 0) );
	AddEdge( V[0], CreateEdge(V[0], V[3], 0) );
	AddEdge( V[0], CreateEdge(V[0], V[4], 0) );

	AddEdge( V[1], CreateEdge(V[1], V[0], 0) );
	AddEdge( V[1], CreateEdge(V[1], V[3], 0) );
	AddEdge( V[1], CreateEdge(V[1], V[4], 0) );

	AddEdge( V[2], CreateEdge(V[2], V[0], 0) );
	AddEdge( V[2], CreateEdge(V[2], V[1], 0) );

	AddEdge( V[3], CreateEdge(V[3], V[0], 0) );
	AddEdge( V[3], CreateEdge(V[3], V[4], 0) );

	AddEdge( V[4], CreateEdge(V[4], V[0], 0) );
	AddEdge( V[4], CreateEdge(V[4], V[1], 0) );
	AddEdge( V[4], CreateEdge(V[4], V[3], 0) );

	PrintGraph(G);
	DestroyGraph(G);

	return 0;
}

--------------------------------------------------------
참고 그림 및 실행결과