#018_자료구조와 알고리즘_그래프

안녕하세요 삽잡이 입니다.

이번 시간에는 그래프를 알아보려고 합니다.

이전에 트리에 대해서 배웠던 적이 있습니다.

트리의 특징을 살펴봤을때에 고립되있지 않고, 순환되지 않는 노드들의 연결 집합을 트리라고 했었습니다.

이 외에 모든 것들을 그래프라고 말할 수 있을 것 같습니다.

그래프를 표현한다는 자체가 목적에 따라 다 다르겠지만, 

가장 얘기가 많이 나오는 것중 하나가 바로, 정점과 간선의 집합체에 대해서 많이들 얘기합니다.

정점(vertex) 와 간선(edge) 이 둘로 그래프를 표현할 수있습니다.

그래프로 표현할 때에 어떠한 정점에서 어떠한 정점으로 갈 수 있는 방향성이 간선에 표현된다면,

출발 정점과 끝정점이 나타날 수 있을 것입니다.

이런 그래프를 방향성 있는 그래프라고 할 수 있겠지요.

모든 간선이 양방향으로 오고갈 수 있다고 하게 된다면,

방향을 표시할 필요가 없습니다. 화살표를 표시하지 않는 그래프를

방향성 없는 그래프라고 할 수 있습니다.

종종, 정점과 정점 사이에 어디가 가깝고 어디가 먼지에 대해 수치로 표현하기도 합니다.

이를, 비중이라고 얘기하며 영어로는 weight라고도 합니다.

그래프로 표현하는 방법은 여러가지 방법이 있습니다.

그 중 한 방법이 이차원 배열로 표현하는 것이지요...

자신과 자신에게 가는 거리는 0으로 정의하고

자신으로부터 갈 수 있는 곳에서 간선이 있을 때 해당되는 비중을 표식하는 형태로

그래프의 값들을 지정해서 문제를 해결하는 방법이 있는데,

이처럼 이차원 배열을 사용하는 그래프를 인적행렬이라고 한다.

인접행렬을 사용하는 알고리즘 코드는 인터넷에 많이 나와 있습니다.

하지만, 정점이 많아지면 두 정점을 못가는 경우까지도 모두 표현해주다 보니

불필요한 메모리까지 할당되게 되어 효율성이 상당히 낮아지게 됩니다.

어떠한 계산을 함에 있어가지고, 확인할 필요가 없는 부분까지 확인하게되는

불필요한 작업들이 있다보니, 이차원 배열을 사용하는 경우는 정점의 갯수가 적을 때 사용합니다.

정점과 간선의 집합체를 가지고 표현한다면, 인접행렬의 단점을 극복할 수 있습니다.

집합체로 표현한 코드는 추후 올리도록 하겠습니다.

일반적으로 그래프를 정의하는 경우가 많지도 않고,

STL에서 제공해주지도 않기 때문에 상당히 낯설고 어렵게 느껴지는 그래프입니다...

그래프를 통해서는 '깊이 우선 탐색'과 '너비 우선 탐색'을 할 수 있습니다.

우선, 깊이 우선 탐색은 가는 경로를 stack에 보관해둔 둡니다.

예를 들어 A로부터 갈 수 있는 경로를 저장한 뒤에 완료되지 않았다면 

stack에서 꺼내서 또 갈 수 있는 경로를 추가하는 과정을 반복합니다.

즉, 현재 지점으로부터 갈 수 있는 모든 경로를 stack에 저장하고 이 과정을 반복하게 되면

모든 경로를 확인 할 수 있게되는데, 이런 과정을 깊이 우선 탐색이라고 할 수 있습니다.

너비 우선 탐새은 그렇다면 뭘까요?

우선, 가까운 거리를 갑니다. 

그 뒤에 예를들어, A에서부터 상대적으로 거리가 가까운 경로를 가서 문제를 해결하는 것입니다.

이는 우선순위 큐를 사용하게 되는데요,

우선순위 큐는 

보관해달라고하면 order 순으로 보관을 하고 꺼내달라고 하면 맨 앞부터 꺼내주는 자료구조입니다.

즉, 특정 기준 순으로 보관하는 큐라고 할 수 있습니다.

정리를 해보도록 하겠습니다.

깊이 우선 탐색은 stack을 사용합니다. 

즉, 두 정점 사이에 갈 수 있는 모든 경로를 조사하고자 할 때 사용합니다.

너비 우선 탐색은 우선순위 큐를 사용합니다.

즉, 두 정점 사이에 가장 바른 길을 찾고자 할 때 사용하게 됩니다.

최단 거리를 찾는 알고리즘들은 모두 너비 우선 탐색(우선순위 큐를 사용하는)을 기반으로

만들어졌다고 할 수 있습니다. 즉, 시발점이라고 할 수 있다 이것이죠.... 푸하하

깊이 우선 탐색은 동적알고리즘입니다.

stack에서 넣고 꺼내는 과정을 거쳤었지요...

다음은 동적알고리즘을 의사 코드로 만들었을때의 과정입니다.

//동적 알고리즘 
//초기 경험 정보 생성
//스택에 보관
//반복(스택이 비어있지 않다면)
    //스택에서 꺼냄
    //다음 경험 목록 조사
    //반복(각 경험에 대하여)
        //조건(목표에 도달)
            //솔루션 컬렉션에 보관
        //아니면
            //스택에 보관

이와 같은 의사 코드를 사용해서 동적 알고리즘을 구현하게 되는데,

graph를 사용해서는 경로 탐색에 대한 프로그램을 구현할 수 있겠군요...

최소 거리/ 모든 경로등을 파악할 수 있으니....

네비게이션도 그렇고... WIFI 까지...?

아무튼...

그래프를 사용한 알고리즘으로는 크루스칼 알고리즘이 있습니다.

신장트리를 만들어주는 알고리즘인데요,

신장 트리란, 어떠한 그래프가 있을 때 그래프와 정점을 가지고 만들어진 새로운 트리를 뜻합니다.

그 중에서 최소 신장 트리를 만드는 이유는 객체들 사이에서 메시지를 주고 받을 때 

약속된 길을 가지고 데이터를 주고 받기위해서 인데요...

일반적으로 라우터에서 많이 사용하는 프로토콜 입니다.

대역폭을 활용하기 위해 정점과 정점 사이에 데이터를 주고 받을 경로를 미리 약속하고 그 경로로 

이동하기 위해서 최소 신장 트리를 사용하는 것이지요...

즉, 다시 정리하자면 경로의 합이 최소일 경우 우리는 '최소 신장 트리'라고 부를 수 있습니다.

최소 신장 트리를 만드는 방법에는 다양한 방법이 있겠지만,

위에서 말씀드린 크르스칼 알고리즘과 프림 알고리즘이 대표적입니다.

프림 알고리즘은 정점을 하나씩 만들어가며 트리를 확대해나가는 알고리즘입니다.

최초의 정점은 임의로 정할 수 있습니다.

즉, 정점을 추가해 나가는 원리로 신장트리를 만드는 것을 프림 알고리즘이라고 합니다.

그렇다면 크루스칼/ 프림 알고리즘에 대해서 다시 정리해보겠습니다.

크루스칼 알고리즘은 간선을 선택해나가는 트리입니다.

따라서 미리 간선을 비중순으로 정렬해두고, 가장 적은 간선을 선택하는 것이지요.

단, 간선 때문에 싸이클이 발생하면 배제하게 됩니다.

그 다음 비중이 작은 것을 계속 선택하게 되는 것이지요.

싸이클이 발생하지 않는 간선을 선택하고 트리를 만드는 것이 크루스칼 알고리즘입니다.

프림 알고리즘에서는 그래프의 정점 개수만큼 정점을 선택하면 되는 것입니다.

이와 같은 알고리즘은 다시한번 말씀드리지만, 라우터에서 사용하는 알고리즘들입니다.

이들은 위에서 깊이 우선 탐색, 너비 우선 탐색에서 언급했던 동적 알고리즘과 달리

탐욕알고리즘 종류입니다.

어떤 정점을 선택할 것인가를 솔루션에 따라 하나 선택하는 과정을 거치기때문이지요.

최적의 것 하나만 선택해서 사용한다 이 말입니다.

다음 시간에 뵙겠습니다!

이상 삽잡이였습니다!