[Python/코테] 그래프 (Graph) - 개념

그래프

• 정점과 간선으로 이루어진 자료구조

차수

• 각 정점에 대해서 연결된 이웃한 정점의 개수
• 네비게이션에서 최단 경로 찾기, 검색 엔진에서 랭킹 정하기와 같이 원소 사이의 연결 관계를 설정해야 하는 상황에서 유용하게 활용
• 간선에는 방향성이 있을 수 있다. 이 때 나가는 간선 개수를 outdegree, 들어오는 간선 개수를 indegree라고 한다.

사이클

• 임의의 한 점에서 출발해 자기 자신으로 돌아올 수 있는 경로
• 그래프 안에 사이클이 하나라도 있으면 순환 그래프, 없으면 비순환 그래프

왼쪽 그래프에서는 간선의 방향으로 인해 사이클이 없는 그래프가 된다.

• 완전 그래프: 모든 서로 다른 두 정점 쌍이 간선으로 연결된 그래프
• 연결 그래프: 임의의 두 정점 사이에 경로가 항상 존재하는 그래프
• 단순 그래프:두 정점 사이의 간선이 1개 이하이고 루프가 존재하지 않는 그래프

루프

• 한 정점에서 시작해 같은 정점으로 들어오는 간선

표현법

1. 인접행렬

 

• 단순 그래프가 아닐 때는, 1 혹은 0으로만 나타내지 말고 간선이 3개면 3을, 4개면 4를 써서 변형할 수 있다.
• 관례적으로 보통 웬만하면 정점은 1-indexed로 번호를 붙인다.

adj_matrix = [][]
v = int(input())
e = int(input())

# 방향 그래프
for i in range(e):
    u = int(input())
    v = int(input())
    adj_matrix[u][v] = 1
    
# 무방향 그래프
for i in range(e):
    u = int(input())
    v = int(input())
    adj_matrix[u][v] = 1
    adj_matrix[v][u] = 1

 

2. 인접 리스트

• 정점이 많고 상대적으로 작은 상황에서 공간을 절약할 수 있는 방식
• v개의 리스트를 만들어 각 리스트에 자신과 연결된 정점을 저장한다.
• 모든 리스트에서 원소의 개수의 총합은 방향 그래프일 때 E개, 무방향 그래프일 때 2E개이기 때문에 최종적으로 $O(V+E)$

# 방향 그래프
adj = [[] for _ in range(4)]

for i in range(e):
    u = int(input())
    v = int(input())
    adj[u].append(v)

비교

• 일반적인 그래프 문제에서 정점 u, v가 연결되어있는지를 반복적으로 확인해야 하는 경우는 드물다.
• 여러 경로 알고리즘들에서는 전부 특정 정점에 연결된 모든 정점을 확인하는 작업이 반복적으로 등장한다.
• 즉, 인접 행렬 보다는 인접 리스트로 그래프를 나타낼 상황이 훨씬 많다.

---

BFS

그래프에서 너비를 우선으로 방문하는 알고리즘

다차원 배열에서는 큐에서 정점과 연결된 모든 정점을 방문하는 과정에서 상하좌우로 인접한 칸을 확인했던 반면, 그래프에서는 간선으로 연결된 정점을 본다는 차이가 있다.

DFS

DFS를 재귀로 처리할 수 있다. → 가장 늦게 호출된 함수를 가장 먼저 처리하는 LIFO, 스택을 이용할 수 있기 때문이다.

---

연습문제

백준 11724번 연결요소의 개수 https://www.acmicpc.net/problem/11724

✔️ 무방향 그래프로 입력 받는다.

✔️ BFS로 풀 수 있다.

11724번: 연결 요소의 개수

 

---

출처:

https://blog.encrypted.gg/1016

[실전 알고리즘] 0x18강 - 그래프

https://veggie-garden.tistory.com/28

[Python] 그래프 (인접 행렬, 인접 리스트) + DFS/BFS를 배우기 앞서 알아야 할 개념들 (탐색 알고리즘,