뇌를 자극하는 알고리즘 - 9. 그래프 : 위상정렬 (Topological Sort)

구현 소스

TopologicalSort.h

#ifndef TOPOLOGICAL_SORT_H
#define TOPOLOGICAL_SORT_H

#include "AdjacencyListGraph.h"
#include "SLL.h"

void TopologicalSort(Vertex* V, Node** List);
// 위상 정렬 함수
void TS_DFS(Vertex* V, Node** List);
// 위상 정렬에 필요한 깊이 우선 탐색 함수의 수정판
// - 깊이 우선 탐색을 하되 
#endif

---------------------------------------------------------
AdjacencyListGraph.h

#ifndef ADJACENCY_LIST_GRAPH
#define ADJACENCY_LIST_GRAPH

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

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

typedef char 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

---------------------------------------------------------
SLL.h

#ifndef SLL_H
#define SLL_H

#include "AdjacencyListGraph.h"

typedef Vertex* ElementType;

typedef struct tagNode{
	ElementType Data;
	struct tagNode *NextNode;
} Node;

Node* SLL_CreateNode(ElementType NewData); // 노드 생성
void SLL_DestroyNode(Node* Node); // 노드 파괴

void SLL_InsertNewHead(Node** Head, Node* NewHead); 
				// 새로운 노드를 Head로 만드는 함수(-링크드 리스트 맨 앞에 노드를 삽입하는 함수)
void SLL_RemoveNode(Node** Head, Node* Remove);	// 노드 제거 - 제거할 노드의 메모리 해제 기능까지 자체 추가.
Node* SLL_GetNodeAt(Node* Head, int Location); // Location 번째의 노드(0번부터 시작)를 찾아 그 주소를 리턴하는 함수
			
int SLL_GetNodeCount(Node* Head);

void SLL_DestroyAllNodes(Node **List); // 모든 노드를 한번에 제거하는 함수


#endif

---------------------------------------------------------
TopologicalSort.cpp

#include "TopologicalSort.h"

// 위상정렬 함수 - List에 위상정렬된 Node들이 존재
void TopologicalSort(Vertex* V, Node** List)
{
	while( V != NULL && V->Visited == NotVisited )
	{
		TS_DFS(V,List);
		V = V->Next;
	}

}
// main에서 만든 graph의 첫 정점 A를 인자로 줄 시,
// 출력 순서 : H-> F-> C-> G-> D-> A-> E-> B
// 노드 순서 : B-> E-> A-> D-> G-> C-> F-> H => Topological Sort Result

// 위상정렬을 도와주는 깊이 우선 탐색(Depth First Search) 함수
// - 깊이 우선 탐색을 하되, 
//  더 이상 옮겨갈 수 있는 인접 정점을 만날시 그 정점을 List의 Head로 삽입한다. (추가 기능)
void TS_DFS(Vertex* V, Node** List)
{
	Node* NewHead = NULL;
	Edge* E	= NULL;

	V->Visited = Visited; // 시작 정점을 방문하고

	E = V->AdjacencyList; // 그 정점의 간선 List를 저장한 후

	while( E != NULL )
	{
		if( (E->Target != NULL) && (E->Target->Visited == NotVisited) )
		{	// 인접 정점이 NULL이 아니고, 인접정점이 NotVisited 상태라면
			TS_DFS(E->Target , List);
			// 인접 정점을 인자로 다시 한번 TS_DFS 함수 호출
		}

		E = E->Next ;
	}

	printf("%c -> ", V->Data);			
	NewHead = SLL_CreateNode(V);
	SLL_InsertNewHead( List, NewHead);
}

---------------------------------------------------------
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");

}

---------------------------------------------------------
SLL.cpp

#include "SLL.h"


// 노드 생성 함수
Node* SLL_CreateNode(ElementType NewData){

	Node* NewNode = (Node*)malloc(sizeof(Node));
	// 새로운 노드를 생성하고

	NewNode->Data = NewData; // 매개변수로 넘긴 데이터를 저장하고
	NewNode->NextNode = NULL; // 가리키는 다음 노드를 뜻하는 NewtNode는 NULL로

	return NewNode; // 생성한 노드의 주소를 리턴
}

// 생성한 노드를 메모리 해제시키는 함수
void SLL_DestroyNode(Node* Node){
	
	free(Node);
}



// 새로운 노드를 Head로 만드는 함수(-링크드 리스트 맨 앞에 노드를 삽입하는 함수)
void SLL_InsertNewHead(Node** Head, Node* NewHead){
	if( (*Head) == NULL){ // Head가 존재하지 않을시 새로운 노드가 Head
		*Head = NewHead;
		//printf("New Head Inserted <Head Node> : NewNode's Data = %d \n", NewHead->Data);
	}
	else{ // 기존의 Head가 존재시		
		NewHead->NextNode = (*Head);// 새로운 노드의 NextNode가 기존의 Head가 되고 
		(*Head) = NewHead; // 새로운 노드가 Head가 된다.	
		//printf("New Head Inserted <Head Node> : NewNode's Data = %d \n", NewHead->Data);
	}
}


// 노드 제거 - 제거할 노드의 메모리 해제 기능까지 자체 추가.
void SLL_RemoveNode(Node** Head, Node* Remove){
	if( (*Head) == Remove){ // 제거할 Remove노드가 Head가 가리키는 노드와 같을시
		*Head = Remove->NextNode; // Head노드가 가리킬 새로운 Node는 기존의 Head의 NextNode
	}
	else{
		Node* Current = *Head;
		
		while(Current != NULL && Current->NextNode!= Remove){
			// Current가 Tail에 도달하거나 Remove의 바로 앞 노드일시 Loop 탈출
			Current = Current->NextNode;
		}
		if(Current != NULL) // Current가 Remove 바로 앞 노드 가리킬시
			Current->NextNode = Remove->NextNode ; // Remove의 NextNode를 Current의 NextNode가 가리키게됨.
		else{ // 제거할 노드가 없을시
			printf("Error - 제거할 노드가 존재하지 않습니다!\n");
			return ;
			// 예외 처리
		}
	}
	//printf("A Node Is Removed             : Removed Node's Data = %d \n", Remove->Data);
	SLL_DestroyNode(Remove); // 삭제할 노드의 메모리 해제!
}

// Location 번째의 노드(0번부터 시작)를 찾아 그 주소를 리턴하는 함수
Node* SLL_GetNodeAt(Node* Head, int Location){
	Node* Current = Head;
	int Temp_Location = Location;

	while(Current!=NULL && (--Location) >= 0){
		// Current가 Tail에 도달 하거나
		// Location이 나타내는 수만큼 노드 이동 연산이 끝났을시 Loop 탈출
		
		// ex) 0번노드 1번노드 2번노드 존재시
		// Location = 1이고 Head는 0번노드를 가리킴
		// - 루프 첫번째
		// Location은 0이 되고 Current = Current->NextNode 수행하고 Current는 1번노드를 가리킴
		// - 루프 두번째 Location이 -1이 되어 loop 탈출 - 따라서 Current는 Location번째 노드를 가리키게 됨
		Current = Current->NextNode;
	}

	// 대충 예외처리
	if(Current!=NULL) // 옳바르게 탐색이 수행됐을시
		return Current;
	else{ // 탐색에 실패했을시
		printf("Error - %d번 노드가 존재하지 않음.\n",Temp_Location);
		return NULL;
	}
}
int SLL_GetNodeCount(Node* Head){
	int Node_Count = 0;
	Node* Current = Head;

	while(Current != NULL){
		// ex) 2개의 노드 존재시
		// - 첫번째 루프 - 조건만족 : Current가 1번노드로 이동하고 Count는 1
		// - 두번째 루프 - 조건만족 : Current가 2번노드(NULL)로 이동하고 Count는 2
		// - 세번째 루프 - 루프탈출 : Count 는 2
		Current = Current->NextNode;
		Node_Count++;
	}

	return Node_Count;
}


// 모든 노드를 한번에 제거하는 함수
void SLL_DestroyAllNodes(Node **List){	
	int i;
	int Count = SLL_GetNodeCount(*List); // 전체 노드의 갯수를 얻은 후
	Node* Current;

	for(i=0 ; i< Count ; i++){
		Current = SLL_GetNodeAt(*List,0);
		// 0번째 노드를 삭제하게 되면 그 다음 노드가 0번 노드가 되고.. 이런식으로 반복되기 때문에
		// 이걸 현재 노드의 개수만큼 수행하면 모든 노드가 삭제된다.
		SLL_RemoveNode(List, Current);
	}
}

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

#include "TopologicalSort.h"

int main()
{
	Graph* graph = CreateGraph(); // 그래프 G 생성
	
	// Vertex(정점) 생성

	Vertex* A = CreateVertex('A'); 
	Vertex* B = CreateVertex('B');
	Vertex* C = CreateVertex('C');
	Vertex* D = CreateVertex('D');
	Vertex* E = CreateVertex('E');
	Vertex* F = CreateVertex('F');
	Vertex* G = CreateVertex('G');
	Vertex* H = CreateVertex('H');

	// 그래프에 정점 추가
	AddVertex(graph, A);
	AddVertex(graph, B);
	AddVertex(graph, C);
	AddVertex(graph, D);
	AddVertex(graph, E);
	AddVertex(graph, F);
	AddVertex(graph, G);
	AddVertex(graph, H);

	// 간선 추가
	AddEdge( A, CreateEdge( A, C, 0 ) );
	AddEdge( A, CreateEdge( A, D, 0 ) );

	AddEdge( B, CreateEdge( B, C, 0 ) );
	AddEdge( B, CreateEdge( B, E, 0 ) );

	AddEdge( C, CreateEdge( C, F, 0 ) );

	AddEdge( D, CreateEdge( D, F, 0 ) );
	AddEdge( D, CreateEdge( D, G, 0 ) );

	AddEdge( E, CreateEdge( E, G, 0 ) );

	AddEdge( G, CreateEdge( G, H, 0 ) );

	AddEdge( F, CreateEdge( F, H, 0 ) );

	Node* SortedList = NULL;
	Node* Temp = NULL;

	printf("Order - ");
	TopologicalSort(graph->Vertices , &SortedList);
	printf("\n");

	printf("Topological Sort Result - ");
	Temp = SortedList;

	while( Temp != NULL )
	{
		printf("%c -> ", Temp->Data->Data);
		Temp = Temp->NextNode;
	}
	printf("\n");

	SLL_DestroyAllNodes(&SortedList);
	DestroyGraph(graph);

	return 0;
}

---------------------------------------------------------
실행 결과