[자료구조] 그래프 개념

그래프란 현실 세계의 사물이나 추상적인 개념 간의 연결관계를 표현한 것 이다. 

정점(vertex) 데이터를 표현 

간선(Edge) 정점들을 연결관계 표현

 

1. 가중치 그래프(Weighted Graph)

간선에 수치를 담을 수 있다.

ex) 지하철 노선도에서 노선간 걸리는 시간.

 

2. 방향 그래프(Directed Graph)

간선에 방향이 있는 그래프

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

 

구현 1. 연결리스트 사용

객체를 계속 생성해야하기 때문에 비효율 적일 수 있다.

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

        void CreateGraph()
        {
            List<Vertex> list = new List<Vertex>(6)
            {
                new Vertex(),
                new Vertex(),
                new Vertex(),
                new Vertex(),
                new Vertex(),
                new Vertex(),
            };
            list[0].edges.Add(list[1]);
            list[0].edges.Add(list[3]);
            list[1].edges.Add(list[2]);
            list[1].edges.Add(list[5]);
            list[3].edges.Add(list[3]);
            list[4].edges.Add(list[4]);
        }
    }

구현 2. 리스트 배열사용

메모리를 아낄 수 있지만 접근 속도에서 손해를 본다(간선이 적고 정점이 많은 경우 효율 적이다.)

            List<int>[] list = new List<int>[6]
            {
                new List<int>{ 1, 2 },
                new List<int>{ 0, 2, 3 },
                new List<int>{ 4, 1 },
                new List<int>{  },
                new List<int>{  },
                new List<int>{ 5, 1 },
            };

구현 3. 행렬(2차원 배열)사용

메모리 소모가 심하지만 빠른 접근이 가능하다. (접점은 적고 간선이 많은 경우 효율 적이다.)

array = [from, to]

			//가중치가 없고 간선 유무만
			int[,] array = new int[6, 6]
            {
                { 0, 1, 0, 1, 0, 0 },
                { 0, 1, 1, 0, 1, 0 },
                { 0, 1, 0, 1, 0, 0 },
                { 1, 0, 0, 0, 0, 1 },
                { 0, 0, 0, 1, 0, 0 },
                { 0, 1, 0, 1, 0, 1 },
            };

            //가중치가 있을 경우 간선이 없는 부분은 -1로 표시
            int[,] array = new int[6, 6]
            {
                { -1, 1, -1, 1, -1, 0 },
                { -1, 15, -1, 30, -1, 40 },
                { -1, 1, -1, 1, -1, 10 },
                { -1, 10, -1, 20, -1, 1 },
                { -1, 0, -1, 15, -1, 10 },
                { -1, 1, -1, 14, -1, 13 },
            };