Chapter 4-2. 그래프

Date: 2020.10.06 Updated: 2020.10.06

카테고리: Algorithm Lesson 2

태그: C Sharp Data Structure Graph Algorithm

인프런에 있는 Rookiss님의 [C#과 유니티로 만드는 MMORPG 게임 개발 시리즈] Part2: 자료구조와 알고리즘 강의를 듣고 정리한 필기입니다. 😀
🌜 강의 들으러 가기 Click

Chapter 4. 그래프

🚖 그래프 이론

그래프의 개념

그래프의 개념 👉 현실 세계의 사물이나 추상적인 개념간의 연결 관계를 표현.

정점(Vertex) 👉 데이터를 표현 (사물, 개념 등)
간선(Edge) 👉 정점들을 연결하여 정점 간의 연결 관계를 표현
- 간선에 가중치 같은 어떤 값을 줄 수도 있다.
그래프 ex) 소셜 네트워크 관계도 (페이스북 친구 관계)

방향 그래프

방향이 존재하는 간선을 가진 그래프 👉, 👈

방향 그래프 ex) 사람 간의 호감도, 일방 통행이 포함된 도로망

그래프를 어떻게 코드로 표현할까?

각 방법마다 장단점이 있기 때문에 그래프는 딱히 정해진 라이브러리 클래스가 없다.

경우에 따라 어떤 방법이 더 효율적이냐가 다르기 때문이다.
- 정점의 수 > 간선의 수 👉 리스트가 나음
- 정점의 수 < 간선의 수 👉 행렬(배열)이 나음

첫 번째 방법 - 정점을 인스턴스로 생성

    class Vertex
    {
        // 나(정점)와 연결되어 있는 정점들을 edges 리스트에 저장
        public List<Vertex> edges = new List<Vertex>();  
    }

    class Program
    {
        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] 정점은 v[1], v[3] 과 연결됨.
            v[0].edges.Add(v[3]);
            v[1].edges.Add(v[0]);  // v[1] 정점은 v[0], v[2], v[3] 과 연결됨.
            v[1].edges.Add(v[2]);
            v[1].edges.Add(v[3]);
            v[3].edges.Add(v[4]);  // v[3] 정점은 v[4] 과 연결됨.
            v[5].edges.Add(v[4]);  // v[5] 정점은 v[4] 과 연결됨.
        }

        static void Main(string[] args)
        {
            CreateGraph();
        }
    }

직관적으로 정점을 실제로 new로 인스턴스로서 생성한 후, 각각의 정점들에서 자신과 연결된 정점들을 리스트로 관리하는 방법.
- 단점
  - 정점을 추가할 때마다 new로 인스턴스를 만들어 구체화 해주어야 한다. 만약 정점이 추상적인 데이터를 담고 있어 구체화할 필요가 없다면 메모리 낭비.

두 번째 방법 - 리스트로 그래프 표현

List<int>[] adjacent = new List<int>[6] // 6 개의 리스트를 adjacent 배열로 관리
{
    new List<int> {1, 3},       // v[0] 정점은 v[1], v[3] 과 연결됨.
    new List<int> {0, 2, 3},    // v[1] 정점은 v[0], v[2], v[3] 과 연결됨.
    new List<int> { },
    new List<int> { 4 },        // v[3] 정점은 v[4] 과 연결됨.
    new List<int> { },
    new List<int> { 4 },        // v[5] 정점은 v[4] 과 연결됨.
}   

정점을 꼭 인스턴스로 생성해야 한다는 부담감을 덜어주었다. 인스턴스 생성할 필요 없이 정수 배열 인덱스를 정점으로 생각하고 리스트의 배열로 관리. 메모리를 아낄 수 있다.

class Edge
{
    public Edge(int v, int w) { vertex = v; weight = w; }
    public int vertex;  
    public int weight;
}

// ...

List<int>[] adjacent = new List<int>[6] // 6 개의 리스트를 adjacent 배열로 관리
{
    new List<Edge> { new Edge(1, 15), new Edge(3, 35) },       // v[0] 정점은 v[1] (가중치 15), v[3] (가중치 35) 과 연결됨.
    new List<Edge> { new Edge(0, 15), new Edge(2, 5), new Edge(3, 10) },    // v[1] 정점은 v[0] (가중치 15), v[2] (가중치 5), v[3] (가중치 10) 과 연결됨.
    new List<Edge> { },
    new List<Edge> { new Edge(4, 5) },        // v[3] 정점은 v[4] (가중치 5) 과 연결됨.
    new List<Edge> { },
    new List<Edge> { new Edge(4, 5) },        // v[5] 정점은 v[4] (가중치 5) 과 연결됨.
}   

연결에 있어 가중치 같은 추가 정보가 필요하다면 위와 같이 구현할 수도 있다.

리스트로 그래프 표현시 단점
- 접근 속도에서 손해를 본다.
  - 2 번째 정점이 3 번째 정점과 연결되어 있는지를 알고 싶다면 리스트 배열 adjacent[1] 에 접근한 후 또 adjacent[1] 리스트에서 3 번째 정점이 있는지를 탐색해야 한다.
  - 바로 바로 알 수가 없다.
  - 간선이 적고 정점이 많은 경우엔 이점이 있지만 간선이 많은 경우엔 탐색이 오래 걸리게 된다.

세 번째 방법 - 행렬(2차원 배열) 이용하기

int [,] adjacent2 = new int[6, 6]
{
    { 0, 1, 0, 1, 0, 0},       // v[0] 정점은 v[1], v[3] 과 연결됨.
    { 1, 0, 1, 1, 0, 0},       // v[1] 정점은 v[0], v[2], v[3] 과 연결됨.
    { 0, 0, 0, 0, 0, 0},
    { 0, 0, 0, 1, 0, 0},       // v[3] 정점은 v[4] 과 연결됨.
    { 0, 0, 0, 0, 0, 0},
    { 0, 0, 0, 1, 0, 0},       // v[5] 정점은 v[4] 과 연결됨.
}

메모리 소모가 심하다.
- 연결 되어 있지 않은 정점도 배열의 연속성을 꺠지 않기 위해 넣어주어야 하므로
- 정점이 100개면 만개 데이터를 저장해야 함.
그러나 빠른 접근이 가능하다! 배열의 연속성 때문에.
- 2 번째 정점이 3 번째 정점과 연결되어 있는지를 알고 싶다면 adjacent[1][2] 값을 받아보면 땡이다.
간선이 많고 정점이 적은 경우에 이점이 있다.

int [,] adjacent2 = new int[6, 6]
{
    { -1, 15, -1, 35, -1, -1},   // v[0] 정점은 v[1] (가중치 15), v[3] (가중치 35) 과 연결됨.
    { 15, -1, 5, 10, -1, -1},     // v[1] 정점은 v[0] (가중치 15), v[2] (가중치 5), v[3] (가중치 10) 과 연결됨.
    { -1, -1, -1, -1, -1, -1},
    { -1, -1, -1, -1, 5, -1},     // v[3] 정점은 v[4] (가중치 5) 과 연결됨.
    { -1, -1, -1, -1, -1, -1},
    { -1, -1, -1, -1, 5, -1},     // v[5] 정점은 v[4] (가중치 5) 과 연결됨.
}

가중치를 표현한다면
- -1로 연결 안되어 있음을 표시
리스트로 구현했을 때처럼 자료구조를 또 쓸 필요 없이 그냥 한번에 배열 하나로 가중치 표현도 가능하다.

🚖 그래프 구현

방향이 없는 (양방향인) 그래프 구현.

    class Graph
    {
        // 1️⃣ 배열로 구현
        int[,] adj = 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, 1, 0 },
            { 0, 0, 0, 1, 0, 1 },
            { 0, 0, 0, 0, 1, 0 },
        };

        // 2️⃣ 리스트로 구현
        List<int>[] adj2 = new List<int>[]
        {
            new List<int>() { 1, 3 },
            new List<int>() { 0, 2, 3 },
            new List<int>() { 1 },
            new List<int>() { 0, 1, 4 },
            new List<int>() { 3, 5 },
            new List<int>() { 4 },
        };
    }

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

공부하는 식빵맘 👱‍♀️