그래프 이론

전체 코드

/*
그래프의 개념
현실 세계의 사물이나 추상적인 개념 간의 연결

정점 : 데이터를 표현

간선 : 정점들을 연결하는데 사용

namespace Exercise
{

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

    
    // 클래스 안에 edge목록을 넣어둠
    class Vertex
    {
        public List<Vertex> edges = new List<Vertex>();


    }
    internal class Program
    {
        
        static void Main(string[] args)
        {

            // 읽는 방법 : 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},
            };
            // Vertex 인스턴스 생성 부담을 줄이자..

            // 가중치 포함
            List<Edge>[] adjacentEdge = 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차원 배열 이용하기
            int[,] adjacentMatrix = 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},
            };

        }
        public void CreateGraph()
        {
            // 인스턴스를 생성함
            List<Vertex> v = new List<Vertex>(6)
            {
                new Vertex(),
                new Vertex(),
                new Vertex(),
                new Vertex(),
                new Vertex(),
                new Vertex(),
            };
            // edge끼리 연결
            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]);
            // 매번 new를 해줘서 정점을 연결해 줘야함
            // 정점은 추상적인 개념일 수 있어서
            // 인스턴스를 생성하는것이 낭비일 수 있음
        }

       
       
    }
}



*/

---

1. 그래프의 기본 개념

• 그래프(Graph): 사물이나 개념 간의 관계를 표현한 자료구조입니다.
• 정점(Vertex): 그래프 내에서 개체를 나타냅니다. 예를 들어, 사람, 장소, 객체 등이 될 수 있습니다.
• 간선(Edge): 정점 간의 관계를 나타냅니다. 관계의 유형이나 강도를 나타내기 위해 가중치를 부여할 수도 있습니다.

그래프의 시각적 표현

아래는 그래프, 가중치 그래프, 방향 그래프 의 예시입니다. 각 원은 정점을, 화살표는 간선을 나타냅니다.

• 그래프 예시

  • ex) 소셜 네트워크 관계도

• 가중치 그래프

  • ex) 지하철 노선도

• 방향 그래프

  • ex) 일방 통행이 포함된 도로망
  • ex) 두 사람 사이의 호감도

2. 그래프 구현 방법

그래프를 표현하는 방법에는 여러 가지가 있습니다. 일반적으로 사용되는 표현 방식은 인접 리스트와 인접 행렬입니다.

2.1. 인스턴스를 이용한 그래프 표현 (객체 지향적 방법)

List<Vertex> v = new List<Vertex>(6)
{
    new Vertex(),
    new Vertex(),
    new Vertex(),
    new Vertex(),
    new Vertex(),
    new Vertex(),
};

분석:

• List<Vertex> v: Vertex 클래스 인스턴스를 저장하는 리스트입니다.
• new Vertex(): 각 정점을 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]);

설명:

• 각 정점은 다른 정점과 연결되는 간선을 가지고 있습니다. 예를 들어, 정점 0은 정점 1과 정점 3과 연결되고, 정점 1은 정점 0, 정점 2, 정점 3과 연결됩니다.
• 이는 인접 리스트로 그래프를 구현한 형태로, 각 정점의 인접 정점들을 리스트로 관리합니다.

2.2. 리스트를 이용한 그래프 표현

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<int>[] adjacent: 각 정점에 연결된 다른 정점들을 저장하는 리스트 배열입니다.
• 예를 들어, adjacent[0]은 정점 0과 연결된 정점 1과 정점 3을 나타냅니다.

설명:

이 방식은 간단한 그래프 표현으로, 메모리 절약이 가능하고 간선이 적을 때 유리합니다. 그러나 간선에 접근할 때는 속도가 느릴 수 있습니다.

2.3. 가중치가 있는 간선 추가

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

List<Edge>[] adjacent = 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)},
};

분석:

• Edge 클래스는 간선의 연결된 정점과 그 간선의 가중치를 정의합니다. 예를 들어, new Edge(1, 15)는 정점 0에서 정점 1로 연결된 간선의 가중치가 15임을 나타냅니다.

설명:

가중치가 추가된 간선은 경로 계산을 할 때 유용합니다. 예를 들어, 최단 경로 문제에서는 각 간선의 가중치를 고려하여 경로를 선택합니다.

---

3. 행렬을 이용한 그래프 표현

행렬을 사용한 그래프 표현은 인접 행렬이라고 합니다. 행렬에서 각 원소는 두 정점 간의 연결 여부를 나타냅니다.

3.1. 인접 행렬 구현

int[,] adjacent = 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},
};

분석:

• int[,] adjacent: 2차원 배열로 그래프를 표현합니다. 배열의 값이 1이면 연결됨을 나타내고, 0이면 연결되지 않음을 의미합니다.

설명:

인접 행렬은 빠른 연결 확인이 가능하지만, 간선이 적을 경우 메모리 낭비가 발생할 수 있습니다. 간선의 수가 많을 때 유리합니다.

3.2. 가중치가 있는 인접 행렬

int[,] adjacent = 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},
};

분석:

• adjacent[0, 1]: 정점 0에서 정점 1로 가는 간선의 가중치가 15임을 나타냅니다.
• -1: 연결되지 않은 간선을 나타냅니다.

설명:

가중치를 포함한 인접 행렬에서는 연결되지 않은 정점은 특별한 값(예: -1)으로 표시하며, 각 간선의 가중치도 관리할 수 있습니다.

---