그래프

그래프라는 자료구조에 대해서 간단하게 알아보았다.

 

그래프는 정점(Vertex) 와 간선(Edge)로 구성되있다.

 

여기서 Vertex는 데이터를 표현하는것이고 Edge는 Vertex와 Vertex를 잇는 선이다. 

대충 이런식!

 

관계망, 노선 등 여러가지를 표현할 수 있다. 

 

여기서 가충치 그래프라는 개념이 등장하는데, Edge에 가중치를 부여하는것이다.

 

예를 들어서, Vertex가 자하철 역이라고 생각해보면 Edge가 각 역의 거리, 밀집도 등을 표현할 수 있다.

 

이런 가중치 그래프를 사용해서 길찾기 알고리즘을 진행하는듯? 

 

암튼 이것 말고도 방향 그래프 등 여러 그래프가 있고 상황에 따라서 구현하는듯 하다.

 

그래프를 구현하는 방법 중 여러가지가 있는데 첫 번째로 관계에 대해 생각해보면 양방향 LinkedList가 떠오를 수 있다.

(직관적인 방법임!)

 

또 다른 방법으로 List를 이용해서 구현할 수 있다. 정확히는 이차원 List

List의 첫 번째가 Vertex고 그 안 요소들이 Edge인 형식

 

위의 그래프의 예시를 들자면

1 : {1}

2 : {3, 4}

3: {2,4}

4 : {2,3,5}

5 : {4}

 

이런식!

 

이런식으로 사용하면 메모리를 아낄 수 있지만 접근 속도가 떨어진다고 한다. 그 이유는? 

 

우리는 눈으로 봐서 쉽게 구분할 수 있지만 컴퓨터의 관점으로 보았을 때, 4번이 3번과 연결되있는지 알고 싶으면

 

4번에 접근해서 3이 나올때까지 요소들을 순회해야하는것! 그래서 접근 속도 면에서 탈락. 

 

두 번째 방법은 행렬을 이용해서 그래프를 표현하는 방법

 

아차원 배열을 이용해서 Vertex마다 모든 Edge의 정보를 넣어두는것 예시를 두자면

 

1 : {0,1,0,0,0}  1번 Vertex는 2번과 연결되어 있으니 2번에 1표시

2 : {1,0,1,1,0} 2번 Vertex는 1.3.4와 연결되어 있으니...

(생략) 

 

이렇게 되었을 때 이점은? 2번이 3번과 연결되어 있는지 확인하려면 그냥 바로 2번 Vertex에 3번 접근해서 값을 얻어오면 끝난다. 이래서 행렬을 사용하는 방법은 접근이 빠른것. 하지만 단점은? 연결되어있지 않은 정보까지 모두 저장을 해야하니까 메모리가 많이 사용된다..

 

여기서 가중치까지 적용한다면? 

 

연결되어 있지 않은 정보들은 단순히 -1로 처리하고, 연결되어 있으면 그냥 연결되어 있다는 정보가 아니라 바로 가중치 값을 넣어두면 좀 더 빠른 접근이 되는 그래프를 만들 수 있다.

 

Vertex 2 : {1,-1,5,70,-1}

 

이런식으로..