자료구조_그래프

모든 정보는 https://coding-factory.tistory.com/610에서 가져왔으며, 이해를 하기위해 적어놓은 것이다.

그래프란?

그래프는 정점과 간선으로 이루어진 자료구조이다.정확히는 정점(Vertex)간의 관계를 표현하는 조직도이다.

그런면에서 트리는 그래프의 일종인 셈입니다. 다만 트리와는 달리 그래프는 정점마다 간선이 없을수도 있고 있을수도 있으며 루트 노드, 부모와 자식이라는 개념이 존재하지 않는다.

또한 그래프는 네트워크 모델 즉, 객체와 이에 대한 관계를 나타내는 유연한 방식으로 이해할 수 있다. 

실생활에서 다양한 예를 그래프로 효현할 수 있는데 대표적으로 지하철 노선도, 도심의 도로등이 있다.

이런식으로 활용할 수 있는 방법이 많기에 문제도 다양하게 출제를 할 수있다. 그래프는 알고리즘에서 굉장히 많이 사용된다. 특히 그래프를 순회하는 방식인 DFS와 BFS를 잘 알아두어야 한다.

 

그래프 용어

정점(Vertice) : 노드(node)라고도 하며 정점에는 데이터가 저장된다.

간선(edge) : 링크(arcs)라고도 하며, 노드간의 관계를 나타낸다.

인접 정점(adfacent vertex) : 간선에 의해 연결된 정점

단순 경로(simple-path) : 경로 중 반복되는 정점이 없는것, 같은 간선을 지나가지 않는 경로

차수(degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수

진출 차수(out-degree) : 방향그래프에서 사용된는 용어로 한 노드에서 외부로 향하는 간선의 수

진입 차수(in-degree) : 방향그래프에서 사용되는 용어로 외부 노드에서 들어오는 간선의 수

 

그래프 구현 방법

그래프를 구현하는 방법에는 인접행렬(Adfacency Materix)와 인접리스트(Adjacency List)방식이 있다. 두개의 구현 방식은 각각의 상반된 장단점을 가지고 있는데 대부분 인접리스트 형식을 많이들 사용한다.

인접행렬 방식

인접행렬은 그래프의 노드를 2차원 배열로 만든 것이다. 완성된 배열의 모양은 1,2,3,4,5,6의 정점을 연결하는 노드에 다른 노드들이 인접 정점이라면 1, 아니면 0을 넣어줍니다.

장단점

장점	단점
1. 2차원 배열 안에 모든 정점들의 간선 저보를 담기 떄문에 배열의 위치를 확인하면 두 점에 대한 연결 정보를 조회할 때 O(1) 의 시간 복잡도면 가능하다. 2.구현이 비교적 간편	1.모든 정점에 대해 간선 정보를 대입해야 하므로 O(n^2)의 시간복잡도가 소요 2.무조건 2차원 배열이 필요하기에 필요 이상의 공간이 낭비된다.

인접리스트 방식

인접리스트란 그래프의 노드들을 리스트로 표현한것이다. 주로 정점의 리스트 배열을 만들어 관계를 설정해줌으로써 구현한다.

장단점

장점	단점
1. 정점들의 연결 정보를 탐색할 때 O(n)의 시간이면 가능한다. 2. 필요한 만큼의 공간만 사용하기때문에 공간의 낭비가 적다.	1.특정 두 점이 연결되었는지 확인하려면 인접행렬에 비해 시간이 오래걸린다. 2.구현이 비교적 어렵다.

다양한 그래프의 종류

그래프는 구현되어진 특성에 따라 여러가지 종류로 나누어진다. 대표적인 그래프의 유형은 아래와 같다.

무방향그래프

무방향 그래프는 두 정점을 연결하는 간선에 방향이 없는 그래프이다.

방향그래프

방향 그래프는 두 정점을 연결하는 간선에 방향이 존재하는 그래프이다.

간선의 방향으로만 이동할 수 있다.

가중치그래프

가중치 그래프는 두 정점을 이동할때 비용이 드는 그래프이다.

완전그래프

완전 그래프는 모든 정점이 간선으로 연결되어 있는 그래프이다.

 

그래프의 탐색

첫 정점에서부터 그래프에 존재하는 모든 정점들을 모두 한번씩 방문하는것을 그래프 탐색이라고 한다.

그래프 탑색의 방법은 깊이 우선 탐색(DFS)방식과 너비 우선 탐색(BFS)방식이 있다.

깊이 우선 탐색(DFS)

깊이 우선 탐색은 갈 수 있는 만큼 최대한 깊이 가고, 더 이상 갈 곳이 없다면 이전 정점으로 돌아가는 방식으로 그래프를 순회하는 방식이다. 간단히 재귀호출을 사용하여 구현하거나 스택을 사용하여 구현한다.

넓이 우선탐색(BFS)

넓이 우선탑색 BFS는 시작정점을 방문한 후 시작 정점에 인접한 모든 접점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다.일반적으로 QUEUE를 사용해서 지금 위치에서 갈 수 있는 것들을 모두 큐에 넣는 방식으로 구현한다.