[C#] 그래프 이론

1. 그래프의 개념

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

 정점(Vertex) : 데이터를 표현(사물, 개념 등)

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

 

ex) 소셜 네트워크 관계도 (페이스북)

 -이 그래프에서 0번이 본인이라고 가정할 때 1번과 2번은 친구 관계, 3번과 4번은 직접은 모르지만 친구의 친구 관계라고 할 수 있습니다.

 

ex) 지하철 노선도

 -간선에다가 수치를 추가할 수 있다. 지하철로 예를 들어보면 0번역에서 2번역까지 15분이 걸리고. 2번역에서 3번역은 5분이 걸린다.

 

ex) 일방 통행이 포함된 도로망

ex) 두 사람 사이의 호감도

 -간선에 방향이 생겨서 0번에서 1번으로 가는 간선은 있지만 1번에서 0번으로 가는 간선은 없다. 호감도로 예를 들면 0번과 2번은 서로 호감이 있고, 4번과 5번은 5번만 호감을 가지고 있다.

 

방향 가중치 그래프 - 리스트 배열

List<int>[] adjacent = new List<int>[6]
{
    new List<int> { 1, 2 }, //0번 -> 1번, 2번
    new List<int> { 2 }, //1번 -> 2번
    new List<int> { 0, 3, 4 }, //2번 -> 0번, 3번, 4번
    new List<int> {  }, 
    new List<int> {  },
    new List<int> { 4 }, //5번 -> 4번
}

- 읽는 방법 : adjacent[from] -> 연결된 목록

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

- 메모리는 아낄 수 있지만, 접근 속도에서 손해를 본다.

- 간선이 적고 정점이 많은 경우 이점이 있다.

 

방향 그래프 - 행렬 (2차원 배열) 이용하기

 - 읽는 방법 : adjacent[from, to]

 - 접근 속도를 높이기 위해, 행렬을 사용 할 수도 있다.

int[,] adjacent2 = new int[6, 6]
{
    { 0, 1, 1, 0, 0, 0 },
    { 0, 0, 1, 0, 0, 0 },
    { 1, 0, 0, 1, 1, 0 },
    { 0, 0, 0, 0, 0, 0 },
    { 0, 0, 0, 0, 0, 0 },
    { 0, 0, 0, 0, 1, 0 },
}

 

 

만약 방향그래프에서 가중치가 더해지면 리스트를 어떻게 작성해야 할까요?

방향 가중치 그래프 - 리스트 배열

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, 10), new Edge(2, 15) },
    new List<Edge>() { new Edge(2, 15) },
    new List<Edge>() { new Edge(0, 15), new Edge(3, 5), new Edge(4, 5) },
    new List<Edge>() { },
    new List<Edge>() { },
    new List<Edge>() { new Edge(4, 5) },
}

 

방향 가중치 그래프 - 행렬(2차원 배열)

 - 안 쓰는 숫자(예 : -1)를 사용해서 연결이 끊긴 것을 표현

int[,] adjacent2 = new int[6, 6]
{
    { -1, 10, 15, -1, -1, -1 },
    { -1, -1, 15, -1, -1, -1 },
    { 15, -1, -1, 5, 5, -1 },
    { -1, -1, -1, -1, -1, -1 },
    { -1, -1, -1, -1, -1, -1 },
    { -1, -1, -1, -1, 5, -1 },
}

 

 

 

 

---------------------------------------------------------------------------------------------------------------------------

참고 : [인프런] Rookiss님의 [C#과 유니티로 만드는 MMORPG 게임 개발 시리즈] Part2: 자료구조와 알고리즘