뇌를 자극하는 알고리즘 - 9. 그래프 : 그래프 순회(Graph Traversal) - 깊이 우선 탐색(Depth First Search), 너비 우선 탐색(Breadth First Search)

구현 소스

GraphTraversal.h

#ifndef GRAPH_TRAVERSAL_H
#define GRAPH_TRAVERSAL_H

#include "AdjacencyListGraph.h"
#include "LinkedListQueue.h"


void DFS(Vertex* V); 
// 깊이 우선 탐색(Depth First Search) => 재귀 호출(Stack)을 이용한 그래프 순회 방법
void BFS(Vertex* V, LinkedQueue* Queue); 
// 너비 우선 탐색(Breadth First Search) => 링크드리스트 큐를 활용한 그래프 순회 방법


#endif

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

----------------------------------------------------------------
LinkedListQueue.h

#ifndef LINKEDLISTQUEUE_H
#define LINKEDLISTQUEUE

#include "AdjacencyListGraph.h"

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

typedef struct tagLinkedQueue{
	Node* Front; // 전단을 가리키는 포인터
	Node* Rear;  // 후단을 가리키는 포인터
	int Count;   // Node의 개수를 가짐
} LinkedQueue;

LinkedQueue* LQ_CreateQueue(); // Queue 생성
void LQ_DestroyQueue(LinkedQueue* Queue); // Queue 파괴 - Queue에 존재하는 모든 Node를 해제 후 Queue 파괴

Node* LQ_CreateNode(Vertex* Data);
void LQ_DestroyNode(Node* _Node);

void LQ_Enqueue(LinkedQueue* Queue, Node* NewNode); 
// Queue에 노드 삽입
// Node 생성과 동시 Queue에 Enqueue 를 하는 경우 LQ_Enqueue(Queue,LQ_CreateNode("XXX"))

Node* LQ_Dequeue(LinkedQueue* Queue);
// Queue에 Dequeue 수행
// Dequeue와 동시 Dequeue된 Node를 파괴하려면
// LQ_DestroyNode(LQ_Dequeue(Queue))

int LQ_IsEmpty(LinkedQueue* Queue); // Queue가 비어있는 여부 확인.

#endif

----------------------------------------------------------------
GraphTraversal.cpp

#include "GraphTraversal.h"

void DFS(Vertex* V) // Depth First Search
{
	Edge* E = NULL;
	
	printf("%d => ", V->Data);

	V->Visited = Visited; // 시작 정점을 방문했음으로 표시 한 후

	E = V->AdjacencyList ; // 시작 정점의 인접리스트를 방문한다.

	while( E != NULL)
	{
		if( E->Target != NULL && (E->Target->Visited == NotVisited) )
		{	// 인접 정점이 존재하고, 그 정점이 방문되지 않았다면,
			DFS( E->Target); 
			// 재귀 호출
			// - 그 정점을 방문하고 또 다시 그 정점의 인접정점을 찾아나간다.			
		}

		E = E->Next;
	}
}
// main에서 생성된 그래프의 깊이 우선 탐색시 순회 순서
// 1 => 2 => 4 => 5 => 7 => 3 => 6

void BFS(Vertex* V, LinkedQueue* Queue) // Breadth First Search
{
	Edge* E = NULL;
	
	printf("%d => ", V->Data);

	V->Visited = Visited; // 시작 정점을 방문했음으로 표시 한 후

	LQ_Enqueue(Queue, LQ_CreateNode(V)); // 큐에 시작 정점 삽입

	while( ! LQ_IsEmpty(Queue) ) 
	{
		Node* Popped = LQ_Dequeue(Queue); // Dequeue 연산 수행후
		V = Popped->Data; // 정점(Vertex)
		E = V->AdjacencyList ; // 정점의 인접리스트

		while( E != NULL)
		{
			V = E->Target; // 인접 정점

			if( V != NULL && (V->Visited == NotVisited) )
			{
				printf("%d => ", V->Data);
				V->Visited = Visited;
				LQ_Enqueue(Queue, LQ_CreateNode(V));
			}

			E = E->Next;
		}

	}

}
// main에서 생성된 그래프의 깊이 우선 탐색시 순회 순서
// 1 => 2 => 3 => 4 => 5 => 6 => 7
// - Queue의 상태
// 1
// 2 3 (1이 dequeue되고 1의 인접정점 2,3이 enqueue)
// 3 4 5(2가 dequeue되고 2의 인접정점 4,5가 enequeue)
// 4 5 6(3이 dequeue되고 3의 인접정점 6이 enqueue)
// 5 6 7(4가 dequeue되고 4의 인접정점 7이 enqueue)
// 6 7  (5가 dequeue되고 5의 인접정점 7은 이미 Visited 상태로 변경 후 enqueue되었기 때문에 넘어감)
// 7    (6이 dequeue되고 6의 인접정점 7은 이미 Visited 상태로 변경 후 enqueue되었기 때문에 넘어감)
// Empty (Loop 종료)

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

}

----------------------------------------------------------------
LinkedListQueue.cpp

#include "LinkedListQueue.h"

// Queue 생성
LinkedQueue* LQ_CreateQueue(){
	LinkedQueue* Queue = (LinkedQueue*)malloc(sizeof(LinkedQueue));

	Queue->Front = NULL;
	Queue->Rear  = NULL;
	Queue->Count = 0;

	return Queue;

}
// Queue 파괴 - Queue에 존재하는 모든 Node를 해제 후 Queue 파괴
void LQ_DestroyQueue(LinkedQueue* Queue){
	while(! (LQ_IsEmpty(Queue)) ){
		Node* Dequeued = LQ_Dequeue(Queue);
		LQ_DestroyNode(Dequeued);
	}
	free(Queue);
}

Node* LQ_CreateNode(Vertex* Data){
	Node* NewNode = (Node*) malloc( sizeof(Node) );
	NewNode->Data = Data;
	NewNode->NextNode = NULL;

	return NewNode;
}
void LQ_DestroyNode(Node* _Node){
	free(_Node);
}

// Queue에 노드 삽입
// Node 생성과 동시 Queue에 Enqueue 를 하는 경우 LQ_Enqueue(Queue,LQ_CreateNode("XXX"))
void LQ_Enqueue(LinkedQueue* Queue, Node* NewNode){
	// 큐에 노드가 없을 경우
	if( LQ_IsEmpty(Queue) )
	{
		// 전단과 후단 모두 NewNode를 가리키게 한다.
		Queue->Front = NewNode;
		Queue->Rear  = NewNode;
	}
	else
	{
		// Rear의 링크를 조정한다.
		// 기존 Rear의 NextNode를 NewNode로 바꾸고
		// Rear는 새로운 NewNode를 가리키게 함.

		Queue->Rear->NextNode = NewNode;
		Queue->Rear = NewNode;
	}

	// 수행후 노드의 개수를 증가
	(Queue->Count)++;
	
}

// Queue에 Dequeue 수행
// Dequeue와 동시 Dequeue된 Node를 파괴하려면
// LQ_DestroyNode(LQ_Dequeue(Queue))
Node* LQ_Dequeue(LinkedQueue* Queue){
	Node* Front = Queue->Front; // Front가 가리키는 Node를 저장

	// Queue노드가 한개 남았을시
	if(Queue->Front->NextNode == NULL)
	{
		// Queue의 Front와 Rear를 NULL로 .. Front == NULL -> Empty 상태
		Queue->Front = NULL;
		Queue->Rear  = NULL;
	}
	else
	{
		Queue->Front = Queue->Front->NextNode;
	}
	(Queue->Count)--;
	
	return Front;
}

// Queue가 비어있는 여부 확인.
int LQ_IsEmpty(LinkedQueue* Queue){
	return (Queue->Front == NULL);	
}

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

#include "GraphTraversal.h"

int main()
{
	Graph* G = CreateGraph();
	LinkedQueue* Queue = LQ_CreateQueue();

	Vertex* V1 = CreateVertex(1);
	Vertex* V2 = CreateVertex(2);
	Vertex* V3 = CreateVertex(3);
	Vertex* V4 = CreateVertex(4);
	Vertex* V5 = CreateVertex(5);
	Vertex* V6 = CreateVertex(6);
	Vertex* V7 = CreateVertex(7);

	AddVertex(G, V1);
	AddVertex(G, V2);
	AddVertex(G, V3);
	AddVertex(G, V4);
	AddVertex(G, V5);
	AddVertex(G, V6);
	AddVertex(G, V7);

	AddEdge( V1, CreateEdge(V1,V2,0) );
	AddEdge( V1, CreateEdge(V1,V3,0) );

	AddEdge( V2, CreateEdge(V2,V4,0) );
	AddEdge( V2, CreateEdge(V2,V5,0) );

	AddEdge( V3, CreateEdge(V3,V4,0) );
	AddEdge( V3, CreateEdge(V3,V6,0) );

	AddEdge( V4, CreateEdge(V4,V5,0) );
	AddEdge( V4, CreateEdge(V4,V7,0) );

	AddEdge( V5, CreateEdge(V5,V7,0) );

	AddEdge( V6, CreateEdge(V6,V7,0) );

	printf(" - Depth First Search : \n  ");
	DFS(G->Vertices);
	printf("\n");

	V2->Visited = NotVisited;
	V3->Visited = NotVisited;
	V4->Visited = NotVisited;
	V5->Visited = NotVisited;
	V6->Visited = NotVisited;
	V7->Visited = NotVisited;

	// 다시 NotVisited로 바꾼후 BFS 수행.
	printf(" - Breadth First Search : \n  ");
	BFS(G->Vertices, Queue);
	printf("\n");

	LQ_DestroyQueue(Queue);

	DestroyGraph(G);

	return 0;
}

----------------------------------------------------------------

실행 결과