그래프 (Graph)

그래프란?

그래프(Graph)는 요소들이 서로 복잡하게 연결되어 있는 관계를 표현하는 자료구조이다. 예를 들어, 지하철 노선도는 많은 역들이 어떻게 연결되어 있는지를 알려주며, SNS의 인맥 지도는 사람들의 복잡한 친구 관계를 표현한다. 그래프로 표시된 지도를 이용해 어떤 도시에서 다른 도시로 갈 수 있는 가장 가까운 경로를 찾을 수도 있다. 그래프는 선형 자료구조들이나 트리보다 더 일반화 된 자료구조를 제공하고 많은 분야에서 널리 사용하고 있다.

 

우리나라 지도

이와 같은 예들은 공통적으로 다양한 객체들이 서로 연결되어 있는 구조를 갖는다. 그래프는 이런 구조를 표현할 수 있는 훌륭한 논리적인 도구이다.

 

그래프의 역사

그래프는 수학자 오일러(Euler)에 의해 처음 창안되었다. 

 

오일러는 위 그림과 같은 지형에서 "모든 다리를 건너서 출발했던 장소로 돌아올 수 있는가"라는 문제가 답이 없다는 것을 그래프 이론을 통해 증명하였다.

 

오일러는 이 문제에서 가장 중요한 것은 "A, B, C, D의 위치가 어떠한 관계로 연결 되었는가?" 라고 생각하고, "위치"라는 객체는 정점(vertex)으로, 위치간의 관계인 "다리는" 간선(edge)으로 표현하여 위 그림의 오른쪽과 같은 그래프 문제로 변환하였다. 오일러는 이 그래프에 존재하는 모든 간선을 한번만 통과하면서 처음 정점으로 되돌아 오는 경로를 오일러 경로라 정의하고, 그래프의 모든 정점에 연결된 간선의 개수가 짝수일 때만 오일러 경로가 존재한다는 오일러의 정리를 증명하였다. 그래서 위 그래프는 오일러 경로가 존재하지 않는다.

 

그래프의 개념

그래프는 정점(vertex)과 간선(edge)의 집합으로 구성되고, 수학적으로 G = (V, E)와 같이 표시한다. 여기서, V(G)는 그래프 G의 정점들의 집합을, E(G)는 그래프 G의 간선들의 집합을 의미한다. 정점은 객체를 의미하고, 간선은 객체 간의 관계를 의미하는데, 정점 A와 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현한다. 정점은 노드라고도 불리며, 간선은 링크라고도 불린다.

 

그래프의 종류

그래프는 간선의 종류에 따라 몇 가지로 구분된다.

 

1. 무방향 그래프(undirected graph)

간선에 방향이 표시되지 않은 그래프를 무방향 그래프라 한다. 하나의 간선은 양방향으로 갈수 있는 길을 의미하고 (A, B)와 (B, A)는 동일한 간선이 된다. 

 

2. 방향 그래프(directed graph)

간선에 방향성이 존재하는 그래프를 방향 그래프라 한다. 간선은 보통 화살표로 표시되는데, 일방통행 도로와 마찬가지로 한쪽 방향으로만 갈 수 있음을 의미한다. 정점 A에서 정점 B로만 갈 수 있는 간선은 <A, B>로 표시한다. 방향 그래프에서 <A, B>와 <B, A>는 서로 다른 간선이다.

 

3. 가중치 그래프(weighted graph)

간선에 비용이나 가중치가 할당된 그래프를 가중치 그래프 또는 네트워크라 한다. 간선이 두 정점간의 연결 유무뿐만 아니라 연결 강도까지 나타낼 수 있어 보다 복잡한 관계를 표현할 수 있다. 가중치 그래프는 도시와 도시를 연결하는 도로의 길이, 회로 소자의 용량, 통신망 사용료 등을 추가로 표현할 수 있으므로 응용 분야가 보다 광범위하다.

 

4. 부분 그래프(subgraph)

그래프를 구성하는 정점의 집합과 간선의 집합의 부분 집합으로 이루어진 그래프를 부분 그래프라고 한다. 아래 그림은 무방향 그래프(왼쪽)의 부분 그래프(중앙, 오른쪽)을 보여주고 있다.

 

그래프의 표현 및 구현

* 미리 컴파일하는 헤더

// pch.h
#ifndef PCH_H
#define PCH_H

// 여기에 미리 컴파일하려는 헤더 추가
#include <iostream>
#include <queue> // 너비 탐색 용
using namespace std;

typedef char VtxData; // 공용 정점 데이터용
typedef struct GraphNode 
{
    int id;
    struct GraphNode* link;
}GNode;               // 인접 리스트 데이터용

const int MAX_VTXS = 256; // 인접행렬 표현용 배열 최대 사이즈

#endif //PCH_H

 

인접 행렬을 이용한 그래프

그래프 G를 인접 행렬로 표현해 보자. 정점의 개수가 n이라면 nxn의 2차원 배열 형태인 인접 행렬(adjacency matrix)이 사용된다. 이 행렬을 M이라 하면 M의 각 원소들은 다음과 같은 값을 갖는다. 

if(간선 (i, j)가 그래프에 존재)            M[i][j] = 1,
otherwise                                 M[i][j] = 0.

우리가 다루는 그래프에서는 자체 간선(자신에서 출발해서 자신으로 들어오는 간선)을 허용하지 않으므로 인접 행렬의 대각선 성분은 모두 0으로 표시한다.

 

 

* GraphMatrix 클래스

// GraphMatrix.h
#pragma once

class GraphMatrix
{
public:
	GraphMatrix();
	~GraphMatrix();

public:
	bool IsEmpty() { return (m_Size == 0); }
	bool IsFull() { return (m_Size >= MAX_VTXS); }

public:
	void Initialize();
	void Insert(VtxData name);
	void InsertEdgeOneWay(int u, int v, int value);		// 간선 한쪽 방향
	void InsertEdgeTwoWay(int u, int v, int value);		// 간선 양쪽 방향
	void Print();

private:
	int m_Adj[MAX_VTXS][MAX_VTXS];			// 인접행렬
	int m_Size = 0;					// 전체 정점의 개수
	VtxData m_Data[MAX_VTXS];			// 정점에 저장할 데이터 배열
};

// GraphMatrix.cpp
#include "pch.h"
#include "GraphMatrix.h"

GraphMatrix::GraphMatrix()
{
}

GraphMatrix::~GraphMatrix()
{
}

void GraphMatrix::Initialize()
{
	m_Size = 0;
	for (int i = 0; i < MAX_VTXS; ++i)
	{
		for (int j = 0; j < MAX_VTXS; ++j)
		{
			m_Adj[i][j] = 0;
		}
	}
}

void GraphMatrix::Insert(VtxData name)
{
	if (IsFull())
	{
		cout << "Error : 그래프 정점의 개수 초과" << endl;
		exit(-1);
	}
	else
	{
		m_Data[m_Size++] = name;
	}
}

void GraphMatrix::InsertEdgeOneWay(int u, int v, int value)
{
	m_Adj[u][v] = value;
}

void GraphMatrix::InsertEdgeTwoWay(int u, int v, int value)
{
	m_Adj[u][v] = m_Adj[v][u] = value;
}

void GraphMatrix::Print()
{
	cout << "***그래프(인접행렬)***" << endl;
	cout << "크기 : " << m_Size << endl;

	for (int i = 0; i < m_Size; ++i)
	{
		cout << m_Data[i] << "  ";
		for (int j = 0; j < m_Size; ++j)
		{
			cout << " " << m_Adj[i][j];
		}
		cout << endl;
	}
}

*  main

#include "pch.h"
#include "GraphMatrix.h"

int main()
{
	GraphMatrix gm;
	gm.Initialize();

	for (int i = 0; i < 4; ++i)
		gm.Insert('A' + i);

	gm.InsertEdgeTwoWay(0, 1, 1); // A, C
	gm.InsertEdgeTwoWay(0, 3, 1); // A, D
	gm.InsertEdgeTwoWay(1, 2, 1); // B, C
	gm.InsertEdgeTwoWay(1, 3, 1); // B, D
	gm.InsertEdgeTwoWay(2, 3, 1); // C, D
	gm.Print();
}

출력 값

 

인접 리스트를 이용한 그래프

인접 리스트(adjacency list)는 그래프의 각 정점에 인접한 정점들을 연결 리스트로 표현하는 방법이다. 연결 리스트의 노드들은 인접 정점 정보를 저장하는데, 그래프에는 이러한 각 인접 리스트에 대한 헤더 포인터를 배열로 갖는다. 따라서 정점의 번호만 알면 각 정점의 연결 리스트에 쉽게 접근할 수 있다.

 

* GraphLinkedList 클래스

// GraphLinkedList.h
#pragma once
class GraphLinkedList
{
public:
	GraphLinkedList();
	~GraphLinkedList();

public:
	bool IsEmpty() { return (m_Size == 0); }
	bool IsFull() { return (m_Size >= MAX_VTXS); }

public:
	void Initialize();
	void Reset();
	void InsertVertex(VtxData name);
	void InsertEdgeOneWay(int u, int v);
	void Print();

private:
	GNode* m_Adj[MAX_VTXS];
	int m_Size = 0;
	VtxData m_Data[MAX_VTXS];
};

// GraphLinkedList.cpp
#include "pch.h"
#include "GraphLinkedList.h"

GraphLinkedList::GraphLinkedList()
{
}

GraphLinkedList::~GraphLinkedList()
{
	Reset();
}

void GraphLinkedList::Initialize()
{
	m_Size = 0;
	for (int i = 0; i < MAX_VTXS; ++i)
	{
		m_Adj[i] = nullptr;
	}
}

void GraphLinkedList::Reset()
{
	GNode* n;
	for (int i = 0; i < m_Size; ++i)
	{
		while (m_Adj[i] != nullptr)
		{
			n = m_Adj[i];
			m_Adj[i] = n->link;
			delete n;
			n = nullptr;
		}
	}

	m_Size;
}

void GraphLinkedList::InsertVertex(VtxData name)
{
	if (IsFull())
	{
		cout << "Error : 그래프 정점의 개수 초과" << endl;
		exit(-1);
	}
	else
	{
		m_Data[m_Size++] = name;
	}
}

void GraphLinkedList::InsertEdgeOneWay(int u, int v)
{
	GNode* n = new GNode;
	n->link = m_Adj[u];
	n->id = v;
	m_Adj[u] = n;
}

void GraphLinkedList::Print()
{
	cout << "***그래프(인접리스트)***" << endl;
	cout << "크기 : " << m_Size << endl;

	for (int i = 0; i < m_Size; ++i)
	{
		cout << m_Data[i] << "  ";
		for (GNode* n = m_Adj[i]; n != nullptr; n = n->link)
		{
			cout << " " << m_Data[n->id];
		}
		cout << endl;
	}
}

* main

#include "pch.h"
#include "GraphLinkedList.h"

int main()
{
	GraphLinkedList gl;

	gl.Initialize();
	
	for (int i = 0; i < 4; ++i)
	{
		gl.InsertVertex('A' + i);
	}

	//A
	gl.InsertEdgeOneWay(0, 3);
	gl.InsertEdgeOneWay(0, 1);
	//B
	gl.InsertEdgeOneWay(1, 0);
	gl.InsertEdgeOneWay(1, 2);
	gl.InsertEdgeOneWay(1, 3);
	//C
	gl.InsertEdgeOneWay(2, 1);
	gl.InsertEdgeOneWay(2, 3);
	//D
	gl.InsertEdgeOneWay(3, 2);
	gl.InsertEdgeOneWay(3, 1);
	gl.InsertEdgeOneWay(3, 0);
	gl.Print();
}

출력 값

 

 

그래프의 탐색

그래프의 탐색은 가장 기본적인 연산으로 하나의 정점에서 시작하여 모든 정점들을 한 번씩 방문하는 작업이다. 실제로 많은 그래프 문제들이 단순히 정점들의 탐색만으로 해결된다. 예를 들면 전자회로에서 어떤 두 단자가 서로 연결되어 있는지를 판단하는 것은 그래프 탐색만으로 가능하고, 미로에서 출구를 찾는 일도 그래프 탐색으로 해결할 수 있다. 기본적으로 그래프 탐색 방법은 깊이 우선 탐색과 너비 우선 탐색 두 가지가 있다. 

 

이 두 가지 방법에 대한 원리는 알고리즘에서 포스팅 한 바가 있으므로 링크로 대체하고 여기서는 구현에만 집중하도록 한다.

 

깊이 우선 탐색

깊이 우선 탐색 (DFS)

 

* 인접행렬

// GraphMatrix.h
#pragma once

class GraphMatrix
{
// 위와 같으므로 생략...
	void DFS(int v);
	void ResetVisited();
private:
// 위와 같으므로 생략...
	int m_Visited[MAX_VTXS]; // 들른곳을 체크하기 위함(스택과 같은 역할)
};

// GraphMatrix.cpp
// 위와 같은 내용은 생략...
GraphMatrix::~GraphMatrix()
{
	ResetVisited();
}

void GraphMatrix::Initialize()
{
	m_Size = 0;
	for (int i = 0; i < MAX_VTXS; ++i)
	{
		for (int j = 0; j < MAX_VTXS; ++j)
		{
			m_Adj[i][j] = 0;
		}
		m_Visited[i] = 0;
	}
}

void GraphMatrix::DFS(int v)
{
	m_Visited[v] = 1; // 들른 정점은 방문표시
	cout << m_Data[v] << "  "; // 들른 정점 출력
	for (int w = 0; w < m_Size; ++w)
	{
        // 만약 인접한 정점이 있고 들르지 않은 경우
        // 계속해서 탐색한다
		if (m_Adj[v][w] != 0 && m_Visited[w] == 0)
			DFS(w);
	}
}

void GraphMatrix::ResetVisited()
{
	for (int i = 0; i < m_Size; ++i)
	{
		m_Visited[i] = 0;
	}
}

다음과 같은 그래프를 깊이 탐색한다고 가정하면 다음과 같다.

 

// main
#include "pch.h"
#include "GraphMatrix.h"

int main()
{
	GraphMatrix gm;
	gm.Initialize();

	for (int i = 0; i < 8; ++i)
	{
		gm.Insert('A' + i);
	}
	
	// A
	gm.InsertEdgeOneWay(0, 1, 1); gm.InsertEdgeOneWay(0, 2, 1);
	// B
	gm.InsertEdgeOneWay(1, 0, 1); gm.InsertEdgeOneWay(1, 3, 1);
	// C
	gm.InsertEdgeOneWay(2, 0, 1); gm.InsertEdgeOneWay(2, 3, 1);
	gm.InsertEdgeOneWay(2, 4, 1);
	// D
	gm.InsertEdgeOneWay(3, 1, 1); gm.InsertEdgeOneWay(3, 2, 1);
	gm.InsertEdgeOneWay(3, 5, 1);
	// E
	gm.InsertEdgeOneWay(4, 2, 1); gm.InsertEdgeOneWay(4, 6, 1);
	gm.InsertEdgeOneWay(4, 7, 1);
	// F
	gm.InsertEdgeOneWay(5, 3, 1);
	// G
	gm.InsertEdgeOneWay(6, 4, 1); gm.InsertEdgeOneWay(6, 7, 1);
	// H
	gm.InsertEdgeOneWay(7, 4, 1); gm.InsertEdgeOneWay(7, 6, 1);
	
	// DFS A부터 시작
	cout << "DFS ==> ";
	gm.DFS(0);
	cout << endl;

}

 

출력 값

 

 

* 인접리스트

// GraphLinkedList.h
#pragma once
class GraphLinkedList
{
// 위와 같은 내용은 생략...
	void DFS(int v);
	void ResetVisited();
private:
	int m_Visited[MAX_VTXS];
};

// GraphLinkedList.cpp
// 위와 같은 내용은 생략...

GraphLinkedList::~GraphLinkedList()
{
	Reset();
	ResetVisited();
}

void GraphLinkedList::Initialize()
{
	m_Size = 0;
	for (int i = 0; i < MAX_VTXS; ++i)
	{
		m_Adj[i] = nullptr;
		m_Visited[i] = 0;
	}
}

void GraphLinkedList::DFS(int v)
{
	m_Visited[v] = 1;
	cout << m_Data[v] << "  ";
	for (GNode* n = m_Adj[v]; n != nullptr; n = n->link)
	{
		if (m_Visited[n->id] == 0)
			DFS(n->id);
	}
}

void GraphLinkedList::ResetVisited()
{
	for (int i = 0; i < m_Size; ++i)
	{
		m_Visited[i] = 0;
	}
}

 main과 출력 값은 위와 같으므로 생략한다.

 

너비 우선 탐색

너비 우선 탐색 (BFS)

(Queue를 사용해야 하기 때문에 STL에 있는 <queue>를 활용하였다.)

 

* 인접행렬

// GraphMatrix.h
#pragma once

class GraphMatrix
{
// 중복되는 내용 생략...
public:
	void BFS(int v);
private:
	queue<int> m_Queue;
};

// GraphMatrix.cpp
// 중복되는 내용 생략...

void GraphMatrix::BFS(int v)
{
	m_Visited[v] = 1;
	cout << m_Data[v] << "  ";
	m_Queue.push(v);
	while (!m_Queue.empty())
	{
		v = m_Queue.front();
		m_Queue.pop();
		for (int w = 0; w < m_Size; ++w)
		{
			if (m_Adj[v][w] != 0 && m_Visited[w] == 0)
			{
				m_Visited[w] = 1;
				cout << m_Data[w] << "  ";
				m_Queue.push(w);
			}
		}
	}
}

역시 위와 같은 그래프를 너비 탐색하면 다음과 같다.

 

// main
#include "pch.h"
#include "GraphMatrix.h"

int main()
{
	// 위 main과 같으므로 생략
	
	// BFS A부터 시작
	cout << "BFS ==> ";
	gm.BFS(0);
	cout << endl;
}

출력 값

 

 

* 인접리스트

// GraphLinkedList.h
#pragma once
class GraphLinkedList
{
// 중복되는 내용은 생략...
public:
	void BFS(int v);
private:
	queue<int> m_Queue;
};

// GraphLinkedList.cpp
// 중복되는 내용 생략...
void GraphLinkedList::BFS(int v)
{
	m_Visited[v] = 1;
	cout << m_Data[v] << "  ";
	m_Queue.push(v);
	while (!m_Queue.empty())
	{
		v = m_Queue.front();
		m_Queue.pop();
		for (GNode* n = m_Adj[v]; n != nullptr; n = n->link)
		{
			if (m_Visited[n->id] == 0)
			{
				m_Visited[n->id] = 1;
				cout << m_Data[n->id] << "  ";
				m_Queue.push(n->id);
			}
		}
	}
}

 main과 출력 값은 위와 같으므로 생략한다.