그래프는 노드 그리고 노드간 서로룰 잇는 간선(Edge)으로 이루어진 자료구조이다. 간선이 방향성을 가지느냐 아니냐에 따라 방향 그래프 혹은 무방향 그래프로 나뉘며 간선에 가중치가 있을 경우에는 가중 그래프(Weighted Graph)라 한다.
■ 구현 ( 설계 )
AddNode( key )
AddEdge( key_from, key_to )
DeleteNode( key )
DeleteEdge( key_from, to )
FindAdjacentNodes( key )
그래프의 노드를 추가하고 노드간 간선을 설정하여 인접 노드(Adjacent Node)들을 얻을수있는 무방향 그래프를 만들어보자.
■ 구현 ( 헤더 )
[Graph.h]
#pragma once
#include <list>
using namespace std;
typedef unsigned int SIZE;
typedef unsigned int KEY;
class Graph
{
private:
KEY** nodeList = nullptr;
bool** edgeList = nullptr;
SIZE size = 0;
SIZE capacity = 0;
private:
KEY* CreateNode(const KEY& key);
bool FreeNode(const KEY& key);
private:
bool CheckNodeExist(const KEY& key) const;
public:
inline const SIZE& GetSize() const { return this->size; }
void FindAdjacentNodes(const KEY& key, list<KEY>* nodes) const;
public:
bool AddNode(const KEY& key);
bool AddEdge(const KEY& key1, const KEY& key2);
bool DeleteNode(const KEY& key);
bool DeleteEdge(const KEY& key1, const KEY& key2);
private:
Graph();
public:
~Graph();
public:
static Graph* Create(const SIZE& capacity);
void Release();
};
|
순전히 블로그에 올릴용으로 만드는거라 자료를 많이 다룰일은없어 간선을 2차원 동적배열로 관리하기로했다. nodeList 도 더블 포인터인데 , nodeList는 2차원 동적배열로 쓸것이 아니라 1차원 포인터 배열로 쓸것이다.( 널값 여부로 해당 node가 존재하는지를 판단하기 위해 )
■ 구현 ( 코드 )
[Graph.cpp]
소스 코드는 매우 간단하다. 주의해서 볼것은 무방향 이기때문에 간선 추가 및 삭제시 양뱡향에 대한 처리를 해주고 있다는 점이다.
[Graph.cpp]
#include <memory.h>
#include "Graph.h"
KEY * Graph::CreateNode(const KEY & key)
{
KEY* pkey = new KEY(key);
this->size++;
return pkey;
}
bool Graph::FreeNode(const KEY & key)
{
if (!CheckNodeExist(key))
return false;
delete this->nodeList[key];
this->nodeList[key] = nullptr;
this->size--;
return true;
}
bool Graph::CheckNodeExist(const KEY & key) const
{
if (key >= this->capacity)
return false;
if (!this->nodeList[key])
return false;
return true;
}
void Graph::FindAdjacentNodes(const KEY& key, list<KEY>* nodes) const
{
if (!CheckNodeExist(key))
return;
for (int i = 0; i < this->capacity; ++i)
{
if (this->edgeList[key][i])
{
nodes->push_back(i);
}
}
}
bool Graph::AddNode(const KEY & key)
{
if (CheckNodeExist(key))
return false;
this->nodeList[key] = CreateNode(key);
return true;
}
bool Graph::AddEdge(const KEY & key1, const KEY & key2)
{
if (key1 == key2)
return false;
if (!CheckNodeExist(key1) || !CheckNodeExist(key2))
return false;
this->edgeList[key1][key2] = true;
this->edgeList[key2][key1] = true;
return true;
}
bool Graph::DeleteNode(const KEY & key)
{
if (!CheckNodeExist(key))
return false;
for (SIZE i = 0; i < this->capacity; ++i)
{
DeleteEdge(key, i);
DeleteEdge(i, key);
}
FreeNode(key);
return true;
}
bool Graph::DeleteEdge(const KEY & key1, const KEY & key2)
{
if (key1 == key2)
return false;
if (!CheckNodeExist(key1) || !CheckNodeExist(key2))
return false;
this->edgeList[key1][key2] = false;
this->edgeList[key2][key1] = false;
return true;
}
Graph::Graph()
{
}
Graph::~Graph()
{
}
Graph * Graph::Create(const SIZE & capacity)
{
Graph* graph = new Graph;
graph->Release();
graph->nodeList = new KEY*[capacity];
memset(graph->nodeList, 0, sizeof(KEY*)*capacity);
graph->edgeList = new bool*[capacity];
for (SIZE i = 0; i < capacity; ++i)
{
graph->edgeList[i] = new bool[capacity];
memset(graph->edgeList[i], 0, sizeof(bool)*capacity);
}
graph->capacity = capacity;
return graph;
}
void Graph::Release()
{
if (this->nodeList)
{
for (SIZE i = 0; i < this->capacity; ++i)
{
delete this->nodeList[i];
}
delete[] this->nodeList;
this->nodeList = nullptr;
}
if (this->edgeList)
{
for (SIZE i = 0; i < this->capacity; ++i)
{
delete[] this->edgeList[i];
}
delete[] this->edgeList;
this->edgeList = nullptr;
}
this->capacity = 0;
}
|
■ 실행 결과
[Main.cpp]
■ 소스 코드
[Main.cpp]
#include <iostream>
#include "Graph.h"
using namespace std;
int main()
{
Graph* graph = Graph::Create(10);
graph->AddNode(0);
graph->AddNode(1);
graph->AddNode(2);
graph->AddNode(3);
graph->AddEdge(0, 1);
graph->AddEdge(0, 2);
graph->AddEdge(0, 3);
graph->DeleteEdge(0, 1);
list<KEY> nodes;
graph->FindAdjacentNodes(0, &nodes);
while(nodes.size())
{
cout << "0 node's adjacent node : " << nodes.front() << endl;
nodes.pop_front();
}
graph->DeleteNode(0);
graph->DeleteNode(1);
cout << "Graph's size : " << graph->GetSize() << endl;
graph->Release();
delete graph;
graph = nullptr;
return 0;
}
|
■ 소스 코드
댓글 없음:
댓글 쓰기