'그래프'란?

실제 세계의 많은 문제들은 객체들과 그들의 관계로 표현된다.
그래서 실제로는 많은 문제들이 그래프 문제로 변형되어서 풀어진다고 한다.
ex) 하이데라바드에서 뉴욕까지 가는 가장 빠른 노선은? 가장 저렴한 노선은?

그래프는 '정점vertex' (노드)들과 그들을 연결하는 '간선edge'들의 집합.

• 엣지에는 방향이 있을 수 있고 없을 수도 있다.
• 엣지가 두 노드를 연결하고 있으면 두 노드가 인접adjacent하다고 한다.
• 사이클이 없는 그래프는 트리라고 한다. (이전 수업에서 힙은 트리의 일종이라고 했는데, 트리는 그래프의 일종인건가?)
• 경로 path : 인접한 정점들의 sequence이다.
  • simple path : 반복되는 정점이 없는 경로.
• 사이클 cycle : 첫 번째 점과 마지막 점이 같은 경로. (A,B,C,A)

그래프 적용 사례

전자 회로에서 각 구성 요소들의 관계를 표현할 때
수송 네트워크 : 고속도로 네트워크, 항공 네트워크
컴퓨터 네트워크
데이터 베이스 : 데이터베이스의 테이블 간의 의존 관계를 표현하는 ERD

구현

그래프 또한 다른 ADT와 마찬가지로 컴퓨터로 다루기 유용한 형태로 표현해야 할 필요가 있다.

인접 행렬

대표적인 방법으로 인접 행렬Adjacency Matrix이 있다.
말 그대로 matrix, 배열들의 배열이다.
V 개의 배열이 있고 각 배열은 V 개의 칸이 있어서, 두 노드 사이에 연결이 있으면 1, 없으면 0.
방향 그래프인 경우 각 노드에서 출발하는 엣지가 있으면 1, 없으면 0.

인접 리스트

그래프가 조밀dense하지 않다면, 즉 엣지 수가 적다면 인접 리스트가 더 효율적인 방법이다.
각 노드별로 자신과 연결된(방향 그래프의 경우 자신에서 출발한 엣지만) 노드들을 리스트에 담는다.
당연히 인접행렬처럼 많은 공간을 차지하지 않는 장점이 있다.

단점

이렇게 보면 인접 리스트가 인접 행렬보다 더 좋은 방식의 구현인것 같은데, 인접 리스트의 단점이 무엇이길래 인접 행렬도 사용되는것일까?
인접 리스트에서 두 노드 a,b가 서로 연결되어있는지 확인(엣지확인) 하려면? 방향 그래프의 경우 a->b 엣지가 있는지 확인하려면?
인접 리스트는 '리스트'들의 '배열' 이니까, 배열에서 a 노드를 찾는데는 O(1)이고 리스트에서는 a가 가진 엣지의 수 만큼 조회해야하니 O(n) 복잡도를 가진다. (행렬의 경우 모두 배열로 이루어졌으니 O(1)복잡도.)

어떤 노드를 삭제하는 경우에는? 모든 노드들을 순회하면서 거기에 해당 노드와의 엣지가 있는지 확인해야하니 O(n^2) 씩이나 소요된다.

(여기서 시간 복잡도에 있는 n은 정확히는 차수를 의미한다.)

간선 리스트

인접 행렬과 인접 리스트 외에도 간선 리스트, 인접 집합 이라는 표현도 있긴 한데 거의 사용되지 않는다고.
간선들의 리스트로. 노드를 저장하지 않기 때문에 메모리 공간은 훨씬 적게 차지하겠지만, 모든 연산에서 시간이 많이 소요될 수 밖에 없다.

그래프 탐색

혹은 그래프 검색 알고리즘이라고도 불린다.
트리의 탐색 알고리즘(DLR, LDR, LRD)처럼 그래프의 특정 노드에서 시작해 엣지들을 따라 검사하며 탐색한다.
그래프를 탐색하는데 두 가지 방법이 있다.

DFS

Depth First Search : 깊이 우선 탐색.
DFS는 트리의 전위 탐색 (DLR) 과 유사하게 동작한다.

대부분의 DFS 알고리즘에서는 방문/비방문 여부를 boolean으로 표시한다.(간혹 세 가지 경우가 필요할 수 있다.)

BFS

Breadth First Search : 너비 우선 탐색.