[자료구조] 그래프 1

그래프

• 노드와 간선을 이용한 비선형 데이터 구조
• 데이터를 노드로, 노드 간의 관계나 흐름을 간선으로 표현하여 데이터 간의 관계를 표현하는 데 사용
• 간선은 방향이 있을 수도, 없을 수도 있음
• 관계나 흐름에서 정도를 표현할 필요가 있다면 가중치라는 개념을 추가하여 표현함.

그래프의 특징과 종류

방향성

• 간선은 방향을 가질 수도 있고 없을 수도 있음
• 방향이 있는 간선을 포함하면 방향 그래프, 방향이 없는 간선을 포함하면 무방향 그래프라고 함
• 방향 그래프는 어느 한 쪽으로만 간선이 있는 것이 아니라, 서로 반대를 가리키는 간선이 있을 수도 있음

가중치

• 흐름의 방향 뿐 아니라 양을 간선에 표현할 때 가중치를 사용
• 가중치가 있는 그래프를 가중치 그래프라고 함

순환

• 특정 노드에서 시작해 간선을 따라 다시 돌아오는 경로가 있는 것
• 순환이 존재하면 순환 그래프, 순환이 존재하지 않으면 비순환 그래프

그래프 구현

인접 행렬 그래프 표현

• 인접 행렬은 2차원 배열을 활용하여 구현하는 경우가 많음
• 이 때 배열의 인덱스는 노드, 배열의 값은 노드의 가중치로 생각하고 인덱스의 세로 방향을 출발 노드, 가로 방향을 도착 노드로 생각함
• 노드의 데이터가 숫자가 아니라 문자열일 경우, 문자열을 숫자로 매핑하여 인접 행렬의 인덱스로 사용
  

인접 리스트 그래프 표현

인접 리스트로 그래프를 표현하려면 값(v), 가중치(w), 다음 노드(next) 를 묶어 관리하여야 함

1. 노드 개수만큼 배열을 준비
2. 배열의 인덱스는 각 시작 노드를 의미하며 배열의 값에는 다음 노드를 연결함
   

인접 행렬의 장단점

메모리 사용 O(N^2), 시간 복잡도 O(1)

단점

• 노드 수에 비해 간선 수가 매우 적은 희소 그래프를 표현하는 경우 (NxN 크기의 인접 행렬 중 대부분의 공간은 실제로 사용하지 않으므로 비효율적)
• 노드들의 값의 차이가 매우 큰 그래프를 표현하는 경우
  노드값이 순차적으로 증가하지 않고 1, 2, 3, 999와 같이 간격이 크면 가장 큰 노드의 값인 999를 기준으로 인접 행렬의 크기를 잡아야 함

장점

• 인덱스 임의 접근으로 노드 간 간선 정보를 바로 확인할 수 있기 때문에, 정보 확인 시 시간 복잡도가 O(1)로 좋음
• 구현 난이도가 낮음

인접 리스트의 장단점

메모리 사용 O(N + M), 시간 복잡도 O(M), M은 간선의 개수

• 실제 연결된 노드에 대해서만 노드의 값을 노드에 담아 연결하기만 하면 되므로 인접 행렬과 정반대의 장단점을 가짐.
• 간선 정보를 확인할 때는 특정 노드에서 시작하여 연결된 노드 개수가 많으면 많을수록 노드를 연결한 리스트의 길이만큼 탐색해야 함 (O(N))

그래프 탐색

• 깊이 우선 탐색: 더 이상 탐색할 노드가 없을 때까지 진행, 더 이상 탐색할 노드가 없으면 최근에 방문했던 노드로 되돌아간 다음 가지 않은 노드를 방문
• 너비 우선 탐색: 현재 위치에서 가장 가까운 노드부터 모두 방문하고 다음 노드로 넘어감. 그 노드에서 또다시 가장 가까운 노드부터 모두 방문

깊이 우선 탐색

탐색을 하려면 우선 시작 노드를 정하고, 스택에 시작 노드를 푸시한다. 스택에 있는 노드는 아직 방문하지 않았지만 방문할 예정인 노드이다. 시작 노드를 푸시했으면 다음 과정을 반복한다.

1. 스택이 비었는지 확인함. 스택이 비었다는 건 방문할 수 있는 모든 노드를 방문했음을 의미함. 따라서 스택이 비었으면 탐색을 종료함.
2. 스택에서 노드를 팝함. 팝한 원소는 최근에 스택에 푸시한 노드
3. 팝한 노드의 방문 여부를 확인함. 이미 방문한 노드라면 별도의 처리가 없음. 아직 방문하지 않았다면 노드를 방문 처리함.
4. 방문한 노드와 인접한 모든 노드를 확인함. 그리고 그 중에서 아직 방문하지 않은 노드를 스택에 푸시함.

스택을 활용한 깊이 우선 탐색

1. 스택에는 방문 예정인 노드를 푸시함. 시작 노드에는 1을 푸시함.
   

2. 스택에서 1을 팝한 후에 1이 방문한 상태인지 확인함. 1은 아직 방문하지 않은 노드이므로 방문 처리를 함. 그 후 1과 인접하면서 방문하지 않은 노드 4, 5를 5 -> 4 순서로 푸시하여 이후 4 -> 5 순서로 방문 처리할 수 있게 함.
   

3. 같은 방식으로 팝, 푸시를 진행함. 스택에서 4를 팝한 다음, 4가 방문한 상태인지 확인함. 4는 아직 방문하지 않았으므로 방문 처리함. 그런 다음 4와 인접한 2, 3을 3 -> 2 순서로 푸시함.
   

4. 반복하여 스택이 비었으면 작업 종료

재귀 함수를 이용한 깊이 우선 탐색

• dfs(N): N번 노드를 방문 처리하고 N번 노드와 인접한 노드 중 아직 방문하지 않은 노드를 탐색

1. 시작 노드는 1번 노드이므로 dfs(1) 을 호출함. dfs(1) 이 실행되면 1을 방문 처리하고 내부적으로 dfs(4)를 재귀 호출함. 아직 dfs(1) 은 dfs(4) 를 호출한 상태이므로 종료되지 않고 스택에 dfs(1)이 쌓임.
   

2. dfs(4) 가 실행되므로 4는 방문 처리하며, 내부적으로 dfs(4)는 dfs(2)를 호출함. 같은 이유로 dfs(4) 는 스택에 쌓임. 그 후 dfs(2) 를 실행하고 dfs(2)는 dfs(3) 을 재귀 호출함.
   

3. dfs(3) 을 실행함. 3은 인접 노드가 없으므로 추가로 재귀 호출을 하지 않고 함수를 종료함. 여기서 처음으로 스택에서 빠져나오는 함수가 생김.
   

4. 스택 특성에 의해 dfs(2) 로 돌아가 다음 실행 스텝을 진행함. 그러나 2는 방문하지 않았으면서 인접한 노드가 없으므로 종료됨
   

5. 반복하여 작업 종료

너비 우선 탐색

우선 시작 노드를 정하고, 스택에 시작 노드를 푸시함. 시작 노드를 큐에 푸시하면서 방문 처리를 함

1. 큐가 비었는지 확인함. 큐가 비었다면 방문할 수 있는 모든 노드를 방문했다는 의미 (탐색 종료)
2. 큐에서 노드를 팝함
3. 팝한 노드와 인접한 모든 노드를 확인하고 그 중 아직 방문하지 않은 노드를 큐에 푸시하며 방문 처리함.

큐를 활용한 너비 우선 탐색

1. 시작 노드 1을 큐에 푸시하고 방문 처리
   

2. 1을 팝한 후 인접한 4와 5를 확인함. 아직 방문하지 않았으므로 방문 처리하고 4, 5 순서로 큐에 푸시함
   

3. 4를 팝한 후 인접한 2와 3을 확인함. 아직 방문하지 않았으므로 방문 처리하고 2, 3 순서로 큐에 푸시함
   

4. 5를 팝한 후 인접한 1과 4를 확인함. 이미 방문했으므로 아무것도 하지 않음. 큐의 나머지 노드들도 자신과 인접한 노드들을 모두 방문했으므로 아무것도 하지 않고 팝함. 큐가 비면 탐색을 마무리한 것.
   

깊이 우선 탐색과 너비 우선 탐색 비교

깊이 우선 탐색

• 모든 가능한 해를 찾는 백트래킹 알고리즘을 구현할 때 혹은 그래프의 사이클을 감지해야 하는 경우 활용
• 다음에 방문할 인접한 노드를 푸시

너비 우선 탐색

• 찾은 노드가 시작 노드로부터 최단 경로임을 보장함, 미로 찾기 문제에서 최단 경로를 찾거나 네트워크 분석 문제를 풀 때 활용할 수 있음
• 지금 방문할 노드를 푸시