알고리즘...106

그래프 구현 준비

그래프는 다음의 표현 방식이 존재한다.

• 인접 행렬 표현 방식
• 인접 리스트 표현 방식

 

그래프는 다음의 종류가 존재한다.

• 방향 그래프
• 무방향 그래프

 

그래프의 순회는 다음의 방법을 쓸 수 있다.

• 너비 우선 탐색(BFS)
• 깊이 우선 탐색(DFS)

 

또, 그래프는 필요에 따라 가중치를 표현할 수 있다.

 

이에 따라 클래스의 생성자에서 방향, 무방향 그래프를 설정하고 그래프를 출력할 때 순회 방법을 선택할 수 있도록 한다.

 

Graph.h

#pragma once
#include "../Common.h"
#include <cmath>
#include <string>
#include <vector>

using std::string;
using std::vector;

/// <summary>
/// 그래프의 간선 처리 방식
/// </summary>
enum class GraphOption
{
	Undirected,
	Directed,
};

/// <summary>
/// 그래프의 순회 방식
/// </summary>
enum class GraphTraversal
{
	BFS,
	DFS,
};

/// <summary>
/// 그래프 노드를 나타내기 위한 구조체
/// </summary>
struct GraphNode
{
	GraphNode(string name) : name(name) {}

	string name;
};

/// <summary>
/// 그래프의 구성 요소 테스트를 위한 베이스 클래스
/// </summary>
class Graph
{
public:
	Graph(GraphOption graphOption = GraphOption::Undirected) : m_graphOption(graphOption) {};

	virtual void AddNode(string name);
	virtual void AddEdge(string from, string to, int weight = 1) = 0;
	virtual void RemoveNode(string name) = 0;
	virtual void RemoveEdge(string from, string to) = 0;
	virtual void Clear() = 0;

	virtual void PrintGraph(GraphTraversal graphTraversal = GraphTraversal::BFS, string graphName = "Graph");

	bool Exists(string name);
	int GetNodeIndex(string name);

private:
	string GetGraphOptionString();
	string GetGraphTraversalString(GraphTraversal graphTraversal);

protected:
	GraphOption CurrentHashFunction() { return m_graphOption; }

private:
	GraphOption m_graphOption;
	vector<GraphNode> m_graphNodeList;
};

 

Graph.cpp

#include "Graph.h"

#pragma region Public Functions
/// <summary>
/// 그래프에 노드를 추가한다.
/// </summary>
/// <param name="name">추가할 노드 이름</param>
void Graph::AddNode(string name)
{
	if (Exists(name))
	{
		return;
	}

	for (size_t total = m_graphNodeList.size(), i = 0; i < total; i++)
	{
		if (m_graphNodeList[i].name == "")
		{
			m_graphNodeList[i].name = name;
			return;
		}
	}

	m_graphNodeList.push_back(GraphNode(name));
}

/// <summary>
/// 해시 테이블의 현 상태를 출력한다.
/// </summary>
void Graph::PrintGraph(GraphTraversal graphTraversal, string graphName)
{
	std::cout << "------------------------------------------\n";
	std::cout << "- Class Name		: " << graphName << '\n';
	std::cout << "- GraphOption		: " << GetGraphOptionString() << '\n';
	std::cout << "- GraphTraversal	: " << GetGraphTraversalString(graphTraversal) << '\n';
	std::cout << "- Graph Nodes\n";
	if (m_graphNodeList.empty())
	{
		std::cout << "EMPTY\n";
	}
	else
	{
		for (size_t total = m_graphNodeList.size(), i = 0; i < total; i++)
		{
			std::cout << "Index[" << i << "] : ";

			if (m_graphNodeList[i].name == "")
			{
				std::cout << "None";
			}
			else
			{
				std::cout << m_graphNodeList[i].name;
			}

			if (i < total - 1)
			{
				std::cout << " - ";
			}
		}
	}
	std::cout << "------------------------------------------\n";
}

/// <summary>
/// 주어진 이름의 노드가 존재하는지 여부를 반환한다.
/// </summary>
/// <param name="name">검색할 노드의 이름</param>
/// <returns>존재 여부</returns>
bool Graph::Exists(string name)
{
	for (size_t total = m_graphNodeList.size(), i = 0; i < total; i++)
	{
		if (m_graphNodeList[i].name == name)
		{
			return true;
		}
	}
	return false;
}

/// <summary>
/// 그래프에 주어진 이름을 가진 노드의 인덱스를 검색하여 반환한다.
/// </summary>
/// <param name="name">검색할 노드의 이름</param>
/// <returns>노드의 인덱스(없으면 -1)</returns>
int Graph::GetNodeIndex(string name)
{
	for (size_t total = m_graphNodeList.size(), i = 0; i < total; i++)
	{
		if (m_graphNodeList[i].name == name)
		{
			return static_cast<int>(i);
		}
	}
	return -1;
}
#pragma endregion

#pragma region Private Functions
/// <summary>
/// 현재 그래프 옵션을 string 으로 반환한다.
/// </summary>
/// <returns>그래프 옵션 string</returns>
std::string Graph::GetGraphOptionString()
{
	if (m_graphOption == GraphOption::Undirected)
	{
		return "Undirected";
	}
	return "Directed";
}

/// <summary>
/// 주어진 그래프 순회 옵션을 string 으로 변환한다.
/// </summary>
/// <param name="graphTraversal">그래프 순회 방법</param>
/// <returns>그래프 순회 방법 string</returns>
string Graph::GetGraphTraversalString(GraphTraversal graphTraversal)
{
	if (graphTraversal == GraphTraversal::BFS)
	{
		return "BFS";
	}
	return "DFS";
}
#pragma endregion

 

NadanKim/Algorithm: 알고리즘 학습 및 예제 코드 작성을 위한 저장소 (github.com)

GitHub - NadanKim/Algorithm: 알고리즘 학습 및 예제 코드 작성을 위한 저장소