Graph,그래프

Rookiss님의 [c#과 유니티로 만드는 mmorpg 게임 개발 시리즈] part2 : 자료구조와 알고리즘 강의 내용을 정리했습니다.

Rookiss님의 [c++과 유니티로 만드는 mmorpg 게임 개발 시리즈] part3 : 자료구조와 알고리즘 강의 내용을 정리했습니다.

 

개념

- [현실 세계의 사물이나 추상적인 개념] 간의 [연결 관계]를 표현한다.

- 정점(데이터, 사물 개념)과 간선(정점을 연결)로 이루어진다.

 

종류

 - 일반 그래프

 - 방향 그래프

 - 가중치 그래프

 

구현방법

- 노드 정의

: 정점이 간선 정보를 포함하는 형태.

struct Vertex
{
	vector<Vertex*> edges;
}

vector<Vertex> v;
v.resize(6);

v[0].edges.push_back(&v[1]);
v[0].edges.push_back(&v[3]);
v[1].edges.push_back(&v[0]);
v[1].edges.push_back(&v[2]);
v[1].edges.push_back(&v[3]);
v[3].edges.push_back(&v[4]);
v[5].edges.push_back(&v[4]);

- 리스트

 : 메모리는 절약. 접근 속도 느림. 정점수가 많고 간선이 적은 경우 유리.

        List<int>[] nodes = new List<int>[]
        {
            new List<int>() { 1, 3},
            new List<int>() { 0, 2, 3},
            new List<int>() { 1 },
            new List<int>() { 0, 1},
            new List<int>() { 5 },
            new List<int>() { 4 },
        };

- 행렬 사용

 : 메모리는 많이 사용하게 됨. 접근 속도 빠름. 정점수가 적고 간선이 많은 경우 유리.

        int[,] nodes = new int[6, 6]
        {
            {0, 1, 0, 1, 0, 0 },
            {1, 0, 1, 1, 0, 0 },
            {0, 1, 0, 0, 0, 0 },
            {1, 1, 0, 0, 0, 0 },
            {0, 0, 0, 0, 0, 1 },
            {0, 0, 0, 0, 1, 0 },
        };