인접 행렬을 통한 그래프 구현

  인접 행렬을 통한 그래프 구현 

인접 행렬로 그래프를 표현하는 것은 다음과 같이 각각의 노드가 순서대로 존재하는 것으로 가정하여 표현하는 것이다.

 

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

• 생성자
  • ArrayGraph() 비어있고 기본 초기 용량을 가지는 인스턴스 생성
  • ArrayGraph(int) 비어있고 지정한 초기 용량을 가지는 인스턴스 생성
• 속성 
  • NodeCapacity 노드의 최대 개수
  • NodeCount 현재 노드의 개수
• 메서드 
  • InsertNode() 가능할 경우 노드 추가
  • InsertEdge(int, int) 앞의 노드에서 뒷 노드로 이동하는 에지 추가
  • RemoveNode(int) 지정된 인덱스의 노드 제거 후 모든 데이터 위치 조정
  • RemoveEdge(int, int) 앞의 노드에서 뒷 노드로 이동하는 에지 제거
  • Clear() 저장되어 있는 모든 데이터 삭제
  • GetDegreeIn(int) 노드의 진입 차수 반환
  • GetDegreeOut(int) 노드의 진출 차수 반환

 

구현 코드

ArrayGraph.h

#pragma once
#include <iostream>

class ArrayGraph
{
public:
#pragma region 생성자
	ArrayGraph(size_t nodeCapacity = 5);
	~ArrayGraph();
#pragma endregion

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

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

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

	size_t GetDegreeIn(int index);
	size_t GetDegreeOut(int index);

	void PrintInfo();
#pragma endregion

private:
#pragma region Class Util
#pragma endregion

#pragma region 변수
	size_t m_nodeCapacity;
	size_t m_nodeCount;

	int** m_graph;
#pragma endregion
};

 

ArrayGraph.cpp

#include "ArrayGraph.h"

#pragma region 생성자
/// <summary>
/// 지정된 크기 혹은 기본 크기의 ArrayGraph를 생성한다.
/// </summary>
/// <param name="nodeCapacity">생성할 그래프의 크기(기본:5)</param>
ArrayGraph::ArrayGraph(size_t nodeCapacity)
	: m_nodeCapacity(nodeCapacity), m_nodeCount(0)
{
	m_graph = new int* [nodeCapacity];
	for (size_t i = 0; i < nodeCapacity; i++)
	{
		m_graph[i] = new int[nodeCapacity];
		std::fill_n(m_graph[i], nodeCapacity, 0);
	}
}

/// <summary>
/// 메모리 누수를 막기 위해 동적 생성한 노드들을 제거한다.
/// </summary>
ArrayGraph::~ArrayGraph()
{
	for (size_t i = 0; i < m_nodeCapacity; i++)
	{
		delete[] m_graph[i];
	}
	delete[] m_graph;
}
#pragma endregion

#pragma region 메서드
/// <summary>
/// ArrayGraph에 노드를 추가한다.
/// </summary>
void ArrayGraph::InsertNode()
{
	if (m_nodeCount < m_nodeCapacity)
	{
		m_nodeCount++;
	}
}

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

	m_graph[from][to]++;
}

/// <summary>
/// ArrayGraph에서 지정된 인덱스의 노드를 제거한다.
/// </summary>
/// <param name="value">제거할 값</param>
void ArrayGraph::RemoveNode(int index)
{
	if (index < 0 || index >= m_nodeCount)
	{
		return;
	}

	for (int i = index; i < m_nodeCount - 1; i++)
	{
		for (int j = 0; j < m_nodeCount; j++)
		{
			m_graph[i][j] = m_graph[i + 1][j];
		}

		for (int j = 0; j < m_nodeCount; j++)
		{
			m_graph[j][i] = m_graph[j][i + 1];
		}
	}

	for (int i = 0; i < m_nodeCount; i++)
	{
		m_graph[i][m_nodeCount - 1] = 0;
		m_graph[m_nodeCount - 1][i] = 0;
	}

	m_nodeCount--;
}

/// <summary>
/// ArrayGraph에서 from -> to 인 간선을 제거한다.
/// </summary>
/// <param name="from">시작 노드</param>
/// <param name="to">끝 노드</param>
void ArrayGraph::RemoveEdge(int from, int to)
{
	if (from < 0 || from >= m_nodeCount || to < 0 || to >= m_nodeCount)
	{
		return;
	}

	if (m_graph[from][to] > 0)
	{
		m_graph[from][to]--;
	}
}

/// <summary>
/// ArrayGraph의 모든 노드 및 간선을 제거한다.
/// </summary>
void ArrayGraph::Clear()
{
	m_nodeCount = 0;

	for (size_t i = 0; i < m_nodeCapacity; i++)
	{
		std::fill_n(m_graph[i], m_nodeCapacity, 0);
	}
}

/// <summary>
/// 지정된 인덱스의 노드에 진입하는 차수를 반환한다.
/// </summary>
/// <param name="index">노드의 인덱스</param>
size_t ArrayGraph::GetDegreeIn(int index)
{
	if (index < 0 || index >= m_nodeCount)
	{
		return -1;
	}

	int count{ 0 };
	for (int i = 0; i < m_nodeCount; i++)
	{
		count += m_graph[i][index];
	}

	return count;
}

/// <summary>
/// 지정된 인덱스의 노드에서 진출하는 차수를 반환한다.
/// </summary>
/// <param name="index">노드의 인덱스</param>
size_t ArrayGraph::GetDegreeOut(int index)
{
	if (index < 0 || index >= m_nodeCount)
	{
		return -1;
	}

	int count{ 0 };
	for (int i = 0; i < m_nodeCount; i++)
	{
		count += m_graph[index][i];
	}

	return count;
}

/// <summary>
/// 테스트용 리스트 정보 출력 함수
/// </summary>
void ArrayGraph::PrintInfo()
{
	std::cout << "----------------------\n";
	std::cout << "Capacity: " << m_nodeCapacity << '\n';
	std::cout << "Count: " << m_nodeCount << '\n';
	for (size_t i = 0; i < m_nodeCapacity; i++)
	{
		for (size_t j = 0; j < m_nodeCapacity; j++)
		{
			std::cout << ' ' << m_graph[i][j] << ' ';
		}
		std::cout << '\n';
	}
	std::cout << "----------------------\n\n";
}
#pragma endregion

 

테스트 코드

main.cpp

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

// 생성한 자료구조 테스트용 메인
int main()
{
	ArrayGraph graph;

	graph.InsertNode();
	graph.InsertNode();
	graph.InsertNode();
	graph.InsertNode();

	graph.InsertEdge(0, 1);
	graph.InsertEdge(0, 3);
	graph.InsertEdge(1, 1);
	graph.InsertEdge(1, 2);
	graph.InsertEdge(1, 3);
	graph.InsertEdge(2, 0);
	graph.InsertEdge(2, 3);
	graph.InsertEdge(3, 0);
	graph.PrintInfo();

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

	graph.RemoveEdge(3, 0);
	graph.PrintInfo();

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

	graph.RemoveNode(1);
	graph.PrintInfo();

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

	graph.Clear();
	graph.PrintInfo();
}

 

실행 결과

----------------------
Capacity: 5
Count: 4
 0  1  0  1  0
 0  1  1  1  0
 1  0  0  1  0
 1  0  0  0  0
 0  0  0  0  0
----------------------

1 2
----------------------
Capacity: 5
Count: 4
 0  1  0  1  0
 0  1  1  1  0
 1  0  0  1  0
 0  0  0  0  0
 0  0  0  0  0
----------------------

1 2
----------------------
Capacity: 5
Count: 3
 0  0  1  0  0
 1  0  1  0  0
 0  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0
----------------------

2 0
----------------------
Capacity: 5
Count: 0
 0  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0
----------------------