자료구조...83

ArrayListGraph 삭제 메서드)

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

 

ArrayListGraph.cpp

/// <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;
}

 

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

	graph.RemoveEdge(1, 4);

	graph.PrintInfo();

	graph.RemoveNode(2);

	graph.PrintInfo();
}

 

실행결과

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

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

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