인접 리스트를 통한 그래프 구현

  인접 리스트 통한 그래프 구현 

그래프 구현/인접 리스트

인접 리스트는 각각의 노드를 하나의 포인터로 하여 특정 노드에서 이동 가능한 노드를 표현하는 방법으로 다음과 같이 표현된다.

 

구현이 필요한 메서드 및 속성은 다음과 같다.

• 생성자
  • ArrayListGraph() 비어있는는 인스턴스 생성
• 속성 
  
  • NodeCount 현재 노드의 개수
• 메서드 
  • InsertNode() 노드 추가
  • InsertEdge(int, int) 앞의 노드에서 뒷 노드로 이동하는 에지 추가
  • RemoveNode(int) 지정된 인덱스의 노드 제거
  • RemoveEdge(int, int) 앞의 노드에서 뒷 노드로 이동하는 제거
  • Clear() 저장되어 있는 모든 데이터 삭제
  • GetDegreeIn(int) 노드의 진입 차수 반환
  • GetDegreeOut(int) 노드의 진출 차수 반환

 

구현 코드

ArrayListGraph.h

#pragma once
#include <iostream>

struct GraphNode
{
	GraphNode(int value)
		: m_idx(value), m_next(nullptr)
	{
	}

	int m_idx;
	GraphNode* m_next;
};

struct GraphHeader
{
	GraphHeader(int value)
		: m_idx(value), m_data(nullptr), m_next(nullptr)
	{
	}

	int m_idx;
	GraphNode* m_data;
	GraphHeader* m_next;
};

class ArrayListGraph
{
public:
#pragma region 생성자
	ArrayListGraph();
	~ArrayListGraph();
#pragma endregion

#pragma region 속성
	size_t NodeCount() { return m_nodeCount; }
#pragma endregion

#pragma region 메서드
	void InsertNode(int num);
	void InsertEdge(int from, int to);

	void RemoveNode(int num);
	void RemoveEdge(int from, int to);
	void Clear();

	size_t GetDegreeIn(int num);
	size_t GetDegreeOut(int num);

	bool ContainsNode(int num);
	bool ContainsEdge(int from, int to);

	GraphHeader* GetTargetHeader(int num);

	void PrintInfo();
#pragma endregion

private:
#pragma region Class Util
	GraphHeader* PopHeader(int value);
	void PushHeader(GraphHeader* header);

	GraphNode* PopNode(int value);
	void PushNode(GraphNode* node);
#pragma endregion

#pragma region 변수
	size_t m_nodeCount;

	GraphHeader* m_graphHeaders;
	GraphHeader* m_freeHeaders;

	GraphNode* m_freeNodes;
#pragma endregion
};

 

ArrayListGraph.cpp

#include "ArrayListGraph.h"

#pragma region 생성자
/// <summary>
/// 지정된 크기 혹은 기본 크기의 ArrayListGraph를 생성한다.
/// </summary>
ArrayListGraph::ArrayListGraph()
	: m_nodeCount(0), m_graphHeaders(nullptr), m_freeHeaders(nullptr), m_freeNodes(nullptr)
{
}

/// <summary>
/// 메모리 누수를 막기 위해 동적 생성한 노드들을 제거한다.
/// </summary>
ArrayListGraph::~ArrayListGraph()
{
	while (m_freeNodes != nullptr)
	{
		GraphNode* curNode{ m_freeNodes };
		m_freeNodes = m_freeNodes->m_next;
		delete curNode;
	}

	while (m_graphHeaders != nullptr)
	{
		GraphHeader* curHead{ m_graphHeaders };
		m_graphHeaders = m_graphHeaders->m_next;

		while (curHead->m_data != nullptr)
		{
			GraphNode* curNode{ curHead->m_data };
			curHead->m_data = curNode->m_next;
			delete curNode;
		}

		delete curHead;
	}

	while (m_freeHeaders != nullptr)
	{
		GraphHeader* curHead{ m_freeHeaders };
		m_freeHeaders = m_freeHeaders->m_next;
		delete curHead;
	}
}
#pragma endregion

#pragma region 메서드
/// <summary>
/// ArrayListGraph에 노드를 추가한다.
/// </summary>
void ArrayListGraph::InsertNode(int num)
{
	if (ContainsNode(num))
	{
		return;
	}

	GraphHeader* newHeader{ PopHeader(num) };
	newHeader->m_next = m_graphHeaders;
	m_graphHeaders = newHeader;

	m_nodeCount++;
}

/// <summary>
/// ArrayListGraph에 from -> to 인 간선을 추가한다.
/// </summary>
/// <param name="from">시작 노드</param>
/// <param name="to">끝 노드</param>
void ArrayListGraph::InsertEdge(int from, int to)
{
	if (ContainsEdge(from, to))
	{
		return;
	}

	GraphHeader* fromHeader{ GetTargetHeader(from) };
	GraphNode* newNode{ PopNode(to) };
	newNode->m_next = fromHeader->m_data;
	fromHeader->m_data = newNode;
}

/// <summary>
/// ArrayListGraph에서 지정된 인덱스의 노드를 제거한다.
/// </summary>
/// <param name="value">제거할 값</param>
void ArrayListGraph::RemoveNode(int num)
{
	if (!ContainsNode(num))
	{
		std::cout << "존재하지 않는 노드를 제거하려 하고 있습니다.\n";
		return;
	}

	GraphHeader* curHeader{ m_graphHeaders };

	while (curHeader != nullptr)
	{
		if (ContainsEdge(curHeader->m_idx, num))
		{
			RemoveEdge(curHeader->m_idx, num);
		}

		curHeader = curHeader->m_next;
	}

	GraphHeader* prevHeader{ nullptr };
	curHeader = m_graphHeaders;

	while (curHeader != nullptr)
	{
		if (curHeader->m_idx == num)
		{
			break;
		}

		prevHeader = curHeader;
		curHeader = curHeader->m_next;
	}

	if (prevHeader == nullptr)
	{
		m_graphHeaders = curHeader->m_next;
	}
	else
	{
		prevHeader->m_next = curHeader->m_next;
	}

	PushHeader(curHeader);

	m_nodeCount--;
}

/// <summary>
/// ArrayListGraph에서 from -> to 인 간선을 제거한다.
/// </summary>
/// <param name="from">시작 노드</param>
/// <param name="to">끝 노드</param>
void ArrayListGraph::RemoveEdge(int from, int to)
{
	if (!ContainsNode(from) || !ContainsNode(to))
	{
		std::cout << "존재하지 않는 에지를 제거하려 하고 있습니다.\n";
		return;
	}

	GraphHeader* targetHeader{ GetTargetHeader(from) };

	GraphNode* prevNode{ nullptr };
	GraphNode* curNode{ targetHeader->m_data };

	while (curNode != nullptr)
	{
		if (curNode->m_idx == to)
		{
			break;
		}

		prevNode = curNode;
		curNode = curNode->m_next;
	}

	if (prevNode == nullptr)
	{
		targetHeader->m_data = curNode->m_next;
	}
	else
	{
		prevNode->m_next = curNode->m_next;
	}

	PushNode(curNode);
}

/// <summary>
/// ArrayListGraph의 모든 노드 및 간선을 제거한다.
/// </summary>
void ArrayListGraph::Clear()
{
	while (m_graphHeaders != nullptr)
	{
		GraphHeader* curHead{ m_graphHeaders };
		m_graphHeaders = m_graphHeaders->m_next;
		PushHeader(curHead);
	}

	m_nodeCount = 0;
}

/// <summary>
/// 지정된 인덱스의 노드에 진입하는 차수를 반환한다.
/// </summary>
/// <param name="num">노드의 번호</param>
size_t ArrayListGraph::GetDegreeIn(int num)
{
	if (!ContainsNode(num))
	{
		return -1;
	}

	int count{ 0 };
	GraphHeader* curHead{ m_graphHeaders };

	while (curHead != nullptr)
	{
		GraphNode* curNode{ curHead->m_data };
		while (curNode != nullptr)
		{
			if (curNode->m_idx == num)
			{
				count++;
			}
			curNode = curNode->m_next;
		}
		curHead = curHead->m_next;
	}

	return count;
}

/// <summary>
/// 지정된 인덱스의 노드에서 진출하는 차수를 반환한다.
/// </summary>
/// <param name="num">노드의 번호</param>
size_t ArrayListGraph::GetDegreeOut(int num)
{
	GraphHeader* targetHeader{ GetTargetHeader(num) };

	if (targetHeader == nullptr)
	{
		return -1;
	}
	
	int count{ 0 };
	GraphNode* targetNode = targetHeader->m_data;

	while (targetNode != nullptr)
	{
		targetNode = targetNode->m_next;
		count++;
	}

	return count;
}

/// <summary>
/// 그래프에 지정된 숫자의 노드가 존재하는지 검사
/// </summary>
/// <param name="num">확인할 번호</param>
/// <returns>노드 존재 여부</returns>
bool ArrayListGraph::ContainsNode(int num)
{
	GraphHeader* curHead{ m_graphHeaders };
	while (curHead != nullptr)
	{
		if (curHead->m_idx == num)
		{
			return true;
		}
		curHead = curHead->m_next;
	}

	return false;
}

/// <summary>
/// 그래프에 시작 노드에서 끝 노드로의 에지가 존재하는지 검사
/// </summary>
/// <param name="from">시작 노드 번호</param>
/// <param name="to">끝 노드 번호</param>
/// <returns>에지 존재 여부</returns>
bool ArrayListGraph::ContainsEdge(int from, int to)
{
	if (!ContainsNode(from) || !ContainsNode(to))
	{
		std::cout << "존재하지 않는 노드를 추가하려 하고 있습니다.\n";
		return true;
	}

	GraphHeader* targetHeader{ GetTargetHeader(from) };
	GraphNode* targetNode{ targetHeader->m_data };
	while (targetNode != nullptr)
	{
		if (targetNode->m_idx == to)
		{
			return true;
		}
		targetNode = targetNode->m_next;
	}

	return false;
}

/// <summary>
/// 지정된 번호의 헤더가 존재하는 경우 헤더 반환
/// </summary>
/// <param name="num">노드 번호</param>
/// <returns>해당 번호의 노드(없으면 nullptr)</returns>
GraphHeader* ArrayListGraph::GetTargetHeader(int num)
{
	GraphHeader* target{ m_graphHeaders };
	while (target != nullptr)
	{
		if (target->m_idx == num)
		{
			break;
		}
		target = target->m_next;
	}

	return target;
}

/// <summary>
/// 테스트용 리스트 정보 출력 함수
/// </summary>
void ArrayListGraph::PrintInfo()
{
	std::cout << "----------------------\n";
	std::cout << "Count: " << m_nodeCount << '\n';
	GraphHeader* curHeader{ m_graphHeaders };
	while (curHeader != nullptr)
	{
		std::cout << curHeader->m_idx << " : ";
		if (curHeader->m_data == nullptr)
		{
			std::cout << "NULL\n";
		}
		else
		{
			GraphNode* curNode{ curHeader->m_data };
			while (curNode != nullptr)
			{
				std::cout << curNode->m_idx << ' ';
				curNode = curNode->m_next;
			}
			std::cout << '\n';
		}
		curHeader = curHeader->m_next;
	}
	std::cout << "----------------------\n\n";
}
#pragma endregion

#pragma region Class Util
/// <summary>
/// 자유 공간 리스트에서 헤더를 가져오거나 새로 생성한다.
/// </summary>
/// <param name="value">헤더 생성 시 인덱스 값</param>
/// <returns>새 헤더</returns>
GraphHeader* ArrayListGraph::PopHeader(int value)
{
	GraphHeader* newNode{ nullptr };
	if (m_freeHeaders == nullptr)
	{
		newNode = new GraphHeader(value);
	}
	else
	{
		newNode = m_freeHeaders;
		m_freeHeaders = m_freeHeaders->m_next;

		newNode->m_idx = value;
		newNode->m_data = nullptr;
		newNode->m_next = nullptr;
	}
	return newNode;
}

/// <summary>
/// 자유 공간 리스트에 제거된 헤더를 저장한다.
/// </summary>
/// <param name="node">제거된 헤더</param>
void ArrayListGraph::PushHeader(GraphHeader* header)
{
	while (header->m_data != nullptr)
	{
		GraphNode* curNode{ header->m_data };
		header->m_data = curNode->m_next;
		PushNode(curNode);
	}

	header->m_next = m_freeHeaders;
	m_freeHeaders = header;
}

/// <summary>
/// 자유 공간 리스트에서 노드를 가져오거나 새로 생성한다.
/// </summary>
/// <param name="value">노드 생성시 초기값</param>
/// <returns>새 노드</returns>
GraphNode* ArrayListGraph::PopNode(int value)
{
	GraphNode* newNode{ nullptr };
	if (m_freeNodes == nullptr)
	{
		newNode = new GraphNode(value);
	}
	else
	{
		newNode = m_freeNodes;
		m_freeNodes = m_freeNodes->m_next;

		newNode->m_idx = value;
		newNode->m_next = nullptr;
	}
	return newNode;
}

/// <summary>
/// 자유 공간 리스트에 제거된 노드를 저장한다.
/// </summary>
/// <param name="node">제거된 노드</param>
void ArrayListGraph::PushNode(GraphNode* node)
{
	node->m_next = m_freeNodes;
	m_freeNodes = node;
}
#pragma endregion

 

테스트 코드

main.cpp

#include <iostream>
#include "Graph/ArrayListGraph.h"

// 생성한 자료구조 테스트용 메인
int main()
{
	ArrayListGraph graph;
	graph.InsertNode(1);
	graph.InsertNode(2);
	graph.InsertNode(3);
	graph.InsertNode(4);

	graph.InsertEdge(1, 2);
	graph.InsertEdge(1, 4);
	graph.InsertEdge(2, 3);
	graph.InsertEdge(2, 4);
	graph.InsertEdge(3, 4);

	graph.PrintInfo();

	std::cout << graph.GetDegreeIn(1) << ' ' << graph.GetDegreeOut(1) << '\n';

	graph.RemoveEdge(1, 4);

	graph.PrintInfo();

	std::cout << graph.GetDegreeIn(1) << ' ' << graph.GetDegreeOut(1) << '\n';

	graph.RemoveNode(2);

	graph.PrintInfo();
}

 

실행 결과

----------------------
Count: 4
4 : NULL
3 : 4
2 : 4 3
1 : 4 2
----------------------

0 2
----------------------
Count: 4
4 : NULL
3 : 4
2 : 4 3
1 : 2
----------------------

0 1
----------------------
Count: 3
4 : NULL
3 : 4
1 : NULL
----------------------