[길찾기 알고리즘] 2. 그래프 (2) 그래프 기본 개념

그래프

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

- 정점, 간선으로 이루어짐

- 방향과 가중치 유무에 따라 종류가 다양

 

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

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

 

[ 그래프 예시]

- 일반 그래프 : SNS 관계도

- 가중치 그래프 (Weighted Graph) : 지하철 노선도

- 방향 그래프 (Directed Graph) : 일방통행 포함된 도로망

 

* 특징 : 언어 차원에서 지원하는 Collection 없음

- 종류가 매우 다양하므로 상황에 맞는 그래프를 사용자가 직접 구현하여 사용

---

코드로 만들기

인스턴스로 생성하는 방법

- 각 정점마다 객체로 생성해 연결

using System;
using System.Collections.Generic;

namespace ConsoleApp1
{
    class Vertex
    {
        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].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]);
        }
        static void Main(string[] args)
        {
        }
    }
}

---

List

방향 그래프

- 읽는 방법 : 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 }
};

가중치 그래프

- 간선을 인스턴스로 생성하여 리스트에 저장

class Edge
{
    public Edge(int v, int w) { vertex = v; weight = w; }
    public int vertex;
    public int weight;
}
class Program
{
    static void Main(string[] args)
    {
        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) },
        };
    }
}

---

2차원 배열(행렬)

방향 그래프

- 메모리 낭비 심하지만 접근 속도 빠름

- 정점이 적고 간선이 많은 경우 이득

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 }
};

가중치 그래프

- 사용하지 않는 숫자(-1 or 0)로 연결 되지 않은 것을 표현

int[,] adjacent = new int[6, 6]
{
    { 0, 15, 0, 35, 0, 0 },
    { 15, 0, 5, 10, 0, 0 },
    { 0, 0, 0, 0, 0, 0 },
    { 0, 0, 0, 0, 5, 0 },
    { 0, 0, 0, 0, 0, 0 },
    { 0, 0, 0, 0, 5, 0 }
};

내용 출처 : Inflearn Rookiss님 강의 [C#과 유니티로 만드는 MMORPG 게임 개발 시리즈] Part2: 자료구조와 알고리즘

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