C# - 그래프(자료 구조) 이론 (그래프 종류들, 다양하게 코드로 구현해보기)

그래프

정점과 간선을 조합으로 이루어져있다.

그래프의 종류는  무방향 그래프(간선에 방향이 없는 경우), 방향 그래프(간선에 방향이 있는 경우), 가중치 그래프(간선에 가중치 정보가 추가된 경우)등이 있다.

---

01 무방향 그래프

간선에 방향이 없는 경우

 

---

02 가중치 그래프(Weighted Graph)

간선에 가중치 정보가 추가된 경우

간선에 대한 가중치를 이용해서 최단 거리를 구할 수 있다.

 

---

03 방향 그래프

간선에 방향이 있는 경우

 

---

그래프를 어떻게 구현할까?

인스턴스 생성으로 구현

단점 : Vertex인스턴스 생성 부담이 크다.

01 정점클래스 만들기

List<Vertex>에는 해당 정점과 연결된 간선들을 저장한다.

class Vertex
{
    public List<Vertex> edges = new List<Vertex>();
}

---

02 정점들을 저장하는 리스트 vertices만들기

List<Vertex> vertices = new List<Vertex>(4)
{
    new Vertex(),
    new Vertex(),
    new Vertex(),
    new Vertex(),
};

---

03 정점들에 간선 추가하기

vertices[0].edges.Add(vertices[1]);
vertices[0].edges.Add(vertices[2]);
vertices[1].edges.Add(vertices[3]);
vertices[2].edges.Add(vertices[1]);
vertices[2].edges.Add(vertices[3]);

---

04 정점에 연결된 간선들 갯수 출력하기

Console.WriteLine("그래프 결과:");
foreach (var vertex in vertices)
{
    Console.Write("Vertex: ");
    Console.WriteLine(vertex.edges.Count);
}

---

리스트 이용으로 구현

단점 : 접근 속도가 낮다. 일일히 다 가봐야지만 알 수가 있다.

01 배열인 인접 리스트만들기

배열의 각 인덱스는 정점을 나타낸다. 그리고 인덱스에는 정점과 연결된 노드들을 리스트로 표현한다.

List<int>[] adjacent = new List<int>[4]
{
   new List<int> {1,2},
   new List<int> {3},
   new List<int> {1,3},
   new List<int> {},
};

---

02 정점에 연결된 간선들 갯수 출력하기

Console.WriteLine("리스트 이용 , 그래프 결과:");
foreach (var vertex in adjacent)
{
    Console.Write("Vertex: ");
    Console.WriteLine(vertex.Count);
}

---

리스트 이용으로 가중치 그래프 구현

01 Edge를 나타내기 위한 클래스 만들기

간선의 도착점, 간선의 가중치를 포함하고 있다.

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

---

02 각 정점 객체에 Edge와 weight정보 넣기

List<Edge>[] adjacent = new List<Edge>[4]
{
    new List<Edge> {new Edge(1,33), new Edge(2,12)},
    new List<Edge> {new Edge(3,6)},
    new List<Edge> {new Edge(1,9),new Edge(3,19)},
    new List<Edge> {},
};

---

코드 상세 설명

new List<Edge> {new Edge(1,33), new Edge(2,12)},

1) new List<Edge>를 통해서 비어있는 List<Edge>객체를 생성

2) new Edge(1,33), new Edge(2,13)를 통해 Edge객체들을 리스트에 추가

---

03 결과 보기

foreach (var vertex in adjacent)
{
    Console.Write("Vertex: ");

    foreach (var edge in vertex)
    {
        Console.Write($"({edge.vertex},{edge.weight}) ");
    }

    Console.WriteLine();
}

---

2차원 행렬 이용하기

단점 : 메모리 소모가 심함

01 가중치 없는 경우

int[,] adjacent = new int[4, 4]
{
    { 0, 1, 1, 0 },
    { 0, 0, 0, 1 },
    { 0, 1, 0, 1 },
    { 0, 0, 0, 0 },
};

---

02 가중치 있는 경우

int[,] adjacent = new int[4, 4]
{
    {-1, 33, 12, -1 },
    { -1, -1, -1, 6 },
    { -1, 9, -1, 19 },
    { -1, -1, -1, -1 },
};

 

 

 

 

 

 

 

 

참고 :  본 내용은 MMORPG  PART2 강의를 수강하여 작성하였습니다.

https://www.inflearn.com/course/%EC%9C%A0%EB%8B%88%ED%8B%B0-mmorpg-%EA%B0%9C%EB%B0%9C-part2/dashboard