그래프(graph)

그래프의 정의

노드와 그 노드를 연결하는 간선을 하나로 모아놓은 자료구조

그래프의 특징

그래프는 네트워크 모델이다.

부모-자식 관계라는 개념이 없다.

→ 루트 노드라는 개념이 없다.

순회는 DFS나 BFS로 이루어진다.

그래프는 순환 혹은 비순환이다.

그래프는 크게 방향 그래프와 무방향 그래프가 있다.

무방향 그래프? 방향 그래프?

무방향: 간선을 통해서 양방향으로 갈 수 있다.

A-B와 B-A가 같다.

방향: 간선에 방향성이 존재하는 그래프

A→B와 B→A가 다르다

가중치 그래프?

간선에 비용이나 가중치가 할당된 그래프

• 네트워크라고도 한다

연결 그래프? 비연결 그래프?

연결 그래프: 무방향 그래프에 있는 모든 정점쌍에 대해서 항상 경로가 존재하는 경우

비연결 그래프: 무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않는 경우

사이클? 비순환 그래프?

사이클: 단순 경로의 시작 정점과 종료 정점이 동일한 경우

• 단순 경로? 경로 중에서 반복되는 정점이 없는 경우

비순환 그래프

• 사이클이 없는 그래프

완전 그래프?

• 그래프에 속해 있는 모든 정점이 서로 연결되어 있는 그래프
• 무방향 완전 그래프

그래프 구현 방법?

1. 인접 행렬
   1. 사용하면 좋을 때 : 그래프에 간선이 많이 존재하는 밀집(Dense) 그래프인 경우
   2. 장점
      1. 2차원 배열에 있는 위치만 확인하면 되기 때문에 조회 시간이 O(1)입니다.
   3. 단점
      1. 모든 정점에 대한 간선정보를 대입해야해서 입력시에는 O(n^2)의 시간복잡도를 가진다.
      2. 무조건 2차원 배열이 필요해서 공간의 낭비가 있다
2. 인접 리스트
   1. 사용하면 좋을 때 : 그래프에 간선이 적은 희소(Sparse) 그래프인 경우
   2. 장점
      1. 인접한 노드를 쉽게 찾을 수 있다.
      2. 그래프에 존재하는 간선의 수를 O(N+E)안에 알 수 있다.
      3. 필요한 만큼의 공간만 사용하여 공간의 낭비가 적다
   3. 단점
      1. 특정 두 점이 연결되었는지 확인하려면 인접행렬에 비해 시간이 오래 걸린다.

그래프의 탐색 방법

1. DFS
   1. 넓게 탐색하기 전에 깊게 탐색하는 것
   2. 모든 노드를 방문하고자 할 때 이 방법 선택하는 게 좋음
2. BFS
   1. 깊게 탐색하기 전에 넓게 탐색하는 것
   2. 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택하는 게 좋음