[알고리즘(7)] Python으로 알아보는 그래프(Graph)

 

출처: flacticon

 

 

취업해서 9개월만에 돌아옴 깔깔

올해 안엔 이 시리즈 꼭 끝내야지

 

 

[알고리즘 포스팅 순서]

1. 시간복잡도

2. 배열

3. 연결리스트

4. 스택

5. 큐

6. 트리

7. 그래프

8. 해쉬테이블

9. 정렬(선택, 버블, 삽입, 퀵, 힙, 병합)

10. 코테 대비 백준 문제 풀이 꿀팁

 

 

 

[서론]

그래프가 모든 알고리즘의 가장 근간?이라는 생각이 든다.

다른 알고리즘을 설명할 때의 처음과 마지막이 되기 때문이다. 

또한 코테에서 빠지지 않는 필수 문제인 DFS, BFS문제가 나오기 때문에 중요하다.

 

 

 

[그래프란?]

그래프(Graph)란 여러 개의 점과 선으로 이루어진 수학적인 개념이다.

이전 포스팅 내용인 트리(Tree)가 그래프의 한 종류이다.

일상 예시로는  교통 시스템, 컴퓨터 네트워크, 컴퓨터 자원 구조 할당, 신경 학습망 구조 등에 사용된다.

 

 

 

[구조와 기능]

1. 용어 (트리의 용어랑 겹치는 게 꽤 있다)

• 정점(vertex, =노드 node): 데이터(값)과 포인터(다음 노드와의 연결점)를 가지고 있는 트리의 필수 요소
• 간선(edge): 노드와 노드 사이를 잇는 연결선
• 인접 정점(adjacent vertex): 간선에 의해 직접 연결된 정점
• 정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수
  • 무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배
  • 진입 차수(in-degree): 방향 그래프에서 외부에서 오는 간선의 수 (내차수 라고도 부름)
  • 진출 차수(out-degree): 방향 그래픙에서 외부로 향하는 간선의 수 (외차수 라고도 부름)
  • 방향 그래프에 있는 정점의 진입 차수 또는 진출 차수의 합 = 방향 그래프의 간선의 수(내차수 + 외차수)
• 경로 길이(path length): 경로를 구성하는 데 사용된 간선의 수
• 단순 경로(simple path): 경로 중에서 반복되는 정점이 없는 경우
• 사이클(cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경우
• 가중치(weight): 가중치 그래프에서 간선에 할당된 값 또는 비용을 나타낸다. 딥러닝 신경망 구조에서 많이 사용됨

 

 

2. 특징

• 트리(Tree)와 달리 루트, 리프, 부모, 자식, 형제 개념이 없음
• 순환형/비순환형 둘다 가능함 (트리는 순환형 불가능)
• 무방향(=양방향)/방향 둘다 가능함 (트리는 무방향 불가능)
• 자기 순환(self-loop)이 가능함 (트리는 자기 순환 불가능)
• 간선이 있을수도 없을 수도 있음(트리는 없으면 안됨)

 

3. 종류

• 무방향(Undirected) vs 방향(Directed) 그래프

-무방향 그래프: 간선을 통해서 양방향으로 이동할 수 있는 그래프 → (A,B)와 (B, A)는 동일함

(ex. 양방향 통행 도로)

-방향 그래프: 정해진 방향으로만 이동할 수 있는 그래프 → <A, B>와 <B, A>는 다른 것임

(ex. 일방 통행 도로)

 

• 연결(Connected) vs 비연결(Disconnected) 그래프

 

-연결 그래프: 모든 정점들에 대해 간선이 연결된 그래프

(ex. 트리(Tree))

-비연결 그래프: 다른 정점과 연결되는 간선이 없는 정점이 존재하는 그래프

(ex. 네트워크 연결 비활성화 된 상태의 노트북)

 

• 순환(Cycle) vs 비순환(Ayclic) 그래프

 

-순환 그래프: 단순 경로의 시작 정점과 종료 정점이 동일한 그래프

(ex. 출근하고 퇴근하는 우리들의 일상)

-비순환 그래프: 사이클이 없는 그래프

(ex. 여행가서 핫스팟 부분만 돌아다니는 우리들의 여행 경로)

 

• 희소(sparse) vs 밀집(dense) 그래프

 

-희소 그래프: 간선 수가 노드 수보다 적은 그래프

(ex. 뇌세포의 시냅스 연결?)

-밀집 그래프: 간선 수가 노드 수보다 많은 그래프

(ex. 인물 관계도)

 

• 다중(Multi) 그래프

 

-다중 그래프: 두 정점 사이에 2개 이상의 간선이 존재하는 그래프, 보통 그래프 개념에 포함x

(ex. 각 장소 사이 여러 지름길이 존재하는 경우)

 

• 부분(Sub) 그래프

 

-부분 그래프: 한 그래프 내에서 부분 집합으로 나타낼 수 있는 다른 그래프가 존재하는 그래프

(ex. 부분 집합)

 

• 완전(Completed) 그래프

 

-완전 그래프: 모든 정점 쌍에 대해 모든 간선이 연결된 그래프

(ex. ?ㅁ?)

 

• 가중치(Weighted) 그래프

 

-가중 그래프: 정점을 연결하는 간선에 가중치를 부여한 그래프

(ex. 딥러닝 신경망 구조)

 

 

4. 그래프의 구현

• 인접 리스트: 각 노드마다 인접한 노드들을 연결 리스트로 표현하는 자료구조
  노드의 개수를 N이라고 할 때 N개의 리스트로 구현함

 

-장점: 메모리 효율적, 모든 간선의 수를 O(N+E)속도로 파악, 특정 정점의 인접한 정점을 찾을 때 효율적

-단점: 간선의 존재 여부와 정점의 차수를 탐색 할 땐 속도가 인접 행렬보다 느림

-추천: 간선의 개수가 적은 경우

 

• 인접 행렬: 2차원 배열로 그래프를 나타내는 자료구조
  보통 0과 1로 표현함 간선에 가중치가 있는 경우 가중치로 표현함

 

-장점: 두 정점 사이 간선 존재 여부를 O(1)속도로 파악 가능, 정점의 차수는 O(N)속도로 파악 가능

-단점: N^2의 공간이 필요하여 메모리 비효율적, 모든 간선의 수를 O(N^2)의 속도로 파악, 특정 정점의 인접한 정점을 찾을 때 모든 노드 순회 필요

-추천: 간선의 개수가 많은 경우

 

 

5. 관련 알고리즘 종류

• 깊이 우선 탐색(DFS, Depth-First Search) 

-시작 정점에서 한 방향으로 갈 수 있는 가장 먼 경로까지 깊이 탐색하여, 더 이상 탐색 가능한 노드가 없으면

다시 가장 마지막에 만났던 갈림길 간선으로 돌아가 다른 방향의 간선으로 탐색을 계속하여 모든 정점을 방문하는

순회 방법

-즉, 넓게(wide)보단 깊게(deep) 탐색하는 방식

-모든 노드를 탐색하려고 할 때 추천

-주로 그래프 탐색, 사이클 판별, 연결 요소 확인 등에서 사용

-스택으로 구현 가능, 재귀호출 방식 많이 사용함

 

• 너비 우선 탐색(BFS, Breadth-First Search)

-시작 정점에서 인접한 정점들을 모두 차례로 방문하고, 방문했던 정점에 대해 다시 인접한 정점들을

차례로 방문하는 방식으로, 가까운 정점들을 먼저 방문하고 멀리 있는 정점들은 나중에 방문하는 순회 방법

-즉, 깊게(deep)보단 넓게(wide) 탐색하는 방식

-두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 추천

-주로 최단 경로 탐색, 미로 탐색, 연결된 구성 요소 확인 등에서 사용

-큐로 구현 가능

 

• 다익스트라 알고리즘

가중치 그래프에서 시작 노드로부터 모든 다른 노드까지의 최단 경로를 찾는 알고리즘

 

• 벨만-포드 알고리즘

가중치 그래프에서 시작 노드로부터 모든 다른 노드까지의 최단 경로를 찾는 알고리즘

음수 가중치가 있는 경우에도 가능

 

• 플로이드 워셜 알고리즘

음수 순환 그래프가 아닌 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘

시간 복잡도가 O(n^3)임

 

• 크루스칼 알고리즘

중치 그래프에서 최소 신장 트리를 찾는 알고리즘. 모든 간선을 가중치 순으로 정렬한 뒤, 사이클을 형성하지 않는 간선을 추가하여 트리를 형성

 

• 프림 알고리즘 

가중치 그래프에서 최소 신장 트리를 찾는 알고리즘. 시작 노드에서부터 출발하여, 현재 트리와 연결되지 않은 노드 중 최소 가중치의 간선을 선택하여 트리를 확장

 

• 위상 정렬

방향 그래프에서 노드들을 선형적으로 정렬하는 알고리즘. 선행 관계가 있는 작업의 우선 순위를 결정하는 데 사용

 

• 최소 공통 조상

트리에서 두 노드의 가장 가까운 공통 조상을 찾는 알고리즘. 주로 트리 구조를 활용한 문제에서 사용

 

 

 

 

[코드]

코드는 어... 추후에 추가~

 

 

 

[참고 문헌]

1. 갓 엔지니어님 영상: https://www.youtube.com/watch?v=fVcKN42YXXI&list=PLjSkJdbr_gFY8VgactUs6_Jc9Ke8cPzZP&index=6

2. 블로그: https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html

3. 블로그: https://velog.io/@boyeon_jeong/%EA%B7%B8%EB%9E%98%ED%94%84-%EC%A2%85%EB%A5%98-%EB%B0%8F-%EA%B0%9C%EB%85%90

4. 블로그: https://ongveloper.tistory.com/165

5. 블로그: https://algorfati.tistory.com/138

6. 블로그(알고리즘 종류): https://yozm.wishket.com/magazine/detail/2411/

7. 블로그 (알고리즘 종류) : https://gliver.tistory.com/34