그래프 (Graph)
- 최초 작성일: 2021년 4월 20일(수)
목차
[TOC]
내용
그래프 개념
[현실 세계의 사물 및 추상적 개념 간]의 [연결 관계]를 표현
- 정점 (Vertex): 데이터를 표현 (사물이나 개념 등)
- 간선 (Edge): 정점 간의 연결을 표현
그래프 구현
인스턴스 생성 (LinkedList의 Node처럼)
// 인스턴스 생성 (LinkedList의 Node처럼)
class Vertex
{
public List<Vertex> edges = new List<Vertex>();
}
void CreateGraph()
{
List<Vertex> v = new List<Vertex>(6)
{
new Vertex(),
new Vertex(),
new Vertex(),
new Vertex(),
new Vertex(),
new Vertex(),
};
v[0].edges.Add(v[1]);
v[0].edges.Add(v[3]);
v[1].edges.Add(v[0]);
v[1].edges.Add(v[2]);
v[1].edges.Add(v[3]);
v[3].edges.Add(v[4]);
v[5].edges.Add(v[4]);
}
리스트를 이용한 그래프 표현
// 읽는 방법: adjacent[from] -> 연결된 목록
// 리스트를 이용한 그래프 표현
// 메모리를 아낄 수 있지만, 접근 속도에서 손해를 본다.
// (간선이 적고 정점이 많은 경우 이점이 있다)
List<int>[] adjacent = new List<int>[6]
{
new List<int> { 1, 3 },
new List<int> { 0, 2, 3 },
new List<int> { },
new List<int> { 4 },
new List<int> { },
new List<int> { 4 },
};
가중치 추가
// 가중치 추가
List<Edge>[] adjacent_1 = new List<Edge>[6]
{
new List<Edge>() { new Edge(1, 15), new Edge(3, 35) },
new List<Edge>() { new Edge(0, 15), new Edge(2, 5), new Edge(3, 10) },
new List<Edge>() { },
new List<Edge>() { new Edge(4, 5) },
new List<Edge>() { },
new List<Edge>() { new Edge(4, 5) },
};
행렬을 이용한 그래프 표현 (2차원 배열)
// 읽는 방법: adjacent3[from, to]
// 행렬을 이용한 그래프 표현 (2차원 배열)
// 메모리 소모가 심하지만, 빠른 접근이 가능하다.
// (정점은 적고 간선이 많은 경우 이점이 있다)
int[,] adjacent2 = new int[6, 6]
{
{ 0, 1, 0, 1, 0, 0 },
{ 1, 0, 1, 1, 0, 0 },
{ 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 1, 0 },
{ 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 1, 0 },
};
가중치 부여
// 가중치 부여, 안쓰는 숫자(-1)를 사용해 연결이 끊긴 것을 표현
int[,] adjacent2_1 = new int[6, 6]
{
{ -1, 15, -1, 35, -1, -1 },
{ 15, -1, 5, 10, -1, -1 },
{ -1, -1, -1, -1, -1, -1 },
{ -1, -1, -1, -1, 5, -1 },
{ -1, -1, -1, -1, -1, -1 },
{ -1, -1, -1, -1, 5, -1 },
};