IM 13일차 (Graph)

1. Graph란?

 

  그래프는 정점과 간선으로 이루어진 자료구조다.

  정확히는 정점(Vertex)간의 관계를 표현하는 조직도라고 볼 수 있다.

  그런면에서 트리도 그래프라고 할 수 있다.

 

  다만 트리와는 달리 그래프는 정점마다 간선이 없을수도 있고 있을수도 있으며 루트 노드, 부모와 자식이라는 개념이 없다.

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

 

  그래프의 실생활 예제는 다양하다.

  지도, 지하철 노선도, SNS 에서의 팔로우 및 팔로잉이 대표적인 예이다.

 

 

 

2. 용어 정리

 

  2 - 1) 정점(Vertex) : 그래프를 형성하는 노드다.

  2 - 2) 간선(Edge) : 그래프에서 노드의 연결을 의미한다.

  2 - 3) 정점 차수(Degree of Vertex) : 해당 정점(노드)에 연결된 간선의 개수를 나타낸다.

  2 - 4) 희소 그래프(sparse graph) : 정점들 간에 가능한 연결 중 일부만 존재하는 경우 해당 그래프를 희소 그래프라 한다.

  2 - 5) 밀집 그래프(dense graph) : 다양한 정점들 간에 연결이 많은 경우 해당 그래프를 밀집 그래프라고 한다.

  2 - 6) 순환 그래프(cyclical graph) : 어떤 정점에서 출발해 해당 정점으로 다시 돌아오는 경로가 존재하는 지향성 그래프를 말한다.

  2 - 7) 가중치(weight) : 간선에 대한 값으로, 문맥에 따라 다양한 것을 의미한다. 예를 들면 노드 사이의 거리가 될 수 있다.

 

 

 

3. 다양한 그래프

 

  3 - 1) 무지향성 그래프(undirected graph)

  무방향 그래프라고도 하며 한 노드가 다른 노드의 연결인 edge의 방향이 없다.

  즉 노드 간에 edge가 있으면 상호 연결을 의미한다.

 

  3 - 2) 지향성 그래프(directed graph)

 

 

 

  방향 그래프라고도 하며 edge가 방향을 가지는 그래프이다.

 

  3 - 3) 가중치 그래프(weighted graph)

 

 

 

  edge가 특정 값을 가지는 그래프이다. 값의 의미는 문맥에 따라 달라진다.

 

 

 

4. 그래프 구현 방법

 

  그래프를 구현하는 방법에는 인접행렬(Adjacency Materix)와 인접리스트(Adjacency List)방식이 있다.

  두개의 구현 방식은 각각의 장단점을 가지고 있는데 대부분 인접리스트 형식을 많이 사용한다.

 

  4 - 1) 인접 행렬(Adjacency Matrix)

   

  인접행렬은 그래프의 노드를 2차원 배열로 만든 것이다.

  완성된 배열의 모양은 0, 1, 2, 3, 4 의 정점을 연결하는 노드에 다른 노드들이 인접 정점이라면 1, 아니면 0을 넣어준다.

 

  인접 행렬 방식의 장점으로는 2차원 배열 안에 모든 정점들의 간선 정보를 담기 때문에 배열의 위치를 확인하면

  두 점에 대한 연결 정보를 조회할 때 O(1) 의 시간 복잡도면 가능하다.

 

  인접 행렬 방식의 단점으로는 무조건 2차원 배열이 필요하기에 노드(정점)의 개수가 많을때 공간 낭비가 있을 수 있다.

  

  4 - 2) 인접 리스트(Adjacency List)

 

  인접리스트란 그래프의 노드들을 리스트로 표현한 것이다.

  주로 정점의 리스트 배열을 만들어 관계를 설정해줌으로써 구현할 수 있다.

 

  인접리스트의 장점으로는 필요한 만큼의 공간만 사용하기때문에 공간의 낭비가 적다.

  특정 두 점이 연결되었는지 확인하려면 인접행렬에 비해 시간이 오래 걸립니다.

 

  인접 행렬은 O(1) 시간에 탐색이 가능하지만 인접 리스트 방식은 해당 노드에 접근해서 순회해야하기 때문이다.

 

 

 

5. 그래프의 탐색 방법(DFS, BFS)

 

  5 - 1) 깊이 우선 탐색(DFS)

  

    'depth first search' 을 줄인 말이다.

   

Depth First Search

    DFS는 갈 수 있는 깊이만큼 최대한 가고, 더 이상 갈 곳이 없다면 이전 정점으로 돌아가는 방식으로 그래프를 순회하는 방식이다. 

    간단히 재귀호출을 사용하여 구현하거나 스택을 사용하여 구현할 수 있다.

 

  5 - 2) 너비 우선 탐색(BFS) 

 

    'breadth first search'의 줄임말이다.

 

Breadth First Search

  BFS는 시작정점을 기준으로 인접한 모든 정점을 방문한 다음 해당 정점에 인접한 모든 정점들을 우선방문하는 방법이다.

  일반적으로 Queue(선입선출 자료구조)를 사용해서 지금 위치에서 갈 수 있는 것들을 모두 큐에 인큐하고 그 다음 항목을

  인큐하기 전에 기존에 있던 항목을 디큐하는 방법으로 구현할 수 있다.