자료구조...82

ArrayListGraph 삽입 메서드)

그래프에서 사용하는 삽입 메서드를 구현한다.

 

ArrayListGraph.cpp

#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>
/// 그래프에 지정된 숫자의 노드가 존재하는지 검사
/// </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;
}
#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();
}

 

실행결과

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