Part 2-4-2. 그래프 : 그래프 이론, 생성

 

 

그래프 이론

 

[그래프의 개념]

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

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

 

 

[방향 그래프]
방향이 존재하는 간선을 가진 그래프

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

 

[그래프 순회 방법]
배열이나 리스트는 선형 자료 구조이므로 원소들을 차례대로 순회하면 되지만 그래프는 선형 자료 구조가 아닌, 한 정점에 연결된 정점들이 여러개일 수 있으므로 연결된 정점들 중 다음엔 어떤 정점을 탐색할지 다르므로 순회 방법이 다양하다. 대표적으로 두 가지가 있다.

1. DFS (Depth First Search 깊이 우선 탐색)

👉들어갈 수 있다면 무조건 들어가며 깊이 들어가며, 끝까지 들어가야 다시 돌아 옴

 

2. BFS (Breadth First Search 너비 우선 탐색)

 

 

[그렇다면 그래프는 어떻게 코드로 표현할까?]

 

 

각 방법마다 장단점이 있기 때문에 그래프는 딱히 정해진 라이브러리 클래스가 없다. 왜냐하면 경우에 따라 어떤 방법이 더 효율적이냐가 다르기 때문이다.

• 정점의 수 > 간선의 수 👉 리스트가 나음
• 정점의 수 < 간선의 수 👉 행렬(배열)이 나음

 

 

[1. 리스트 버텍스를 이용한 정점을 인스턴스로 생성하는 방법]

    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로 인스턴스를 만들어 구체화 해주어야 한다는 단점이 있다. 만약 정점이 추상적인 데이터를 담고 있어 구체화할 필요가 없다면 메모리 낭비.

 

[2. 리스트를 이용하여 그래프를 표현하는 방법]

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번째 정점이 있는지를 탐색해야 한다. 즉 바로 바로 알수가 없다.
• 간선이 적고 정점이 많은 경우엔 이점이 있지만 간선이 많은 경우엔 탐색이 오래 걸리게 된다.

 

 

[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) 과 연결됨.
}

 

 만약 2차원 배열을 이용해 가중치를 표현할 경우 -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 },
        };
    }