[자료구조] 그래프

석사 시절, airline operation system에 대해 잠깐 공부했었는데 그때 항공기 스케줄을 그래프로 표현하고 모든 스케줄을 소화할 최소 항공기 댓수는 몇개일지 구하는 것 등을 배웠다. 이때도 그래프로 표현하고 문제를 푸는게 정말 재밌었는데, 자료구조로 또 만나니 반가웠다. 오늘은 이 그래프를 코드로 구현하는 법에 대해 배워보자

 

 

1. 그래프

• 정점과 간선으로 이루어진 자료구조로
  • 객체 간의 네트워크를 모형화하는데 사용되며 이는 수학적인 관계를 표현하는데 유용하다
  • 차수(degree) : 각 정점에 간선으로 연결된 이웃한 정점의 개수
• 그래프의 종류
  • 무방향 그래프(Undirected Graph) : 방향성이 없는 그래프
  • 방향 그래프(Directed Graph) : 방향성이 있는 그래프
  • 순환 그래프(Cyclic Graph) : (자기 자신으로 돌아올 수 있는) 사이클이 있는 그래프
  • 비순환 그래프(Acyclic Graph) : 사이클이 없는 그래프
  • 완전 그래프(Complete Graph) : 모든 서로 다른 두 정점 쌍이 간선으로 연결된 그래프
  • 연결 그래프(Connected Graph) : 임의의 두 정점 사이에 경로가 항상 존재하는 그래프 = 간선이 없는 정점이 존재하지 않음

 

 

2. 그래프를 어떻게 코드로 표현할 수 있을까?

• 표현법 1 - 인접 행렬
  • 연결된 두 정점 사이의 간선 개수를 사용해 인접 행렬로 표현할 수 있다

# 인접 행렬로 표현 # 무방향 그래프 # V: 정점 개수, E: 간선 개수
adj_matrix = [[0]*(V+1) for _ in range(V+1)]

for _ in range(E):
    x,y = map(int,input().split())
    adj_matrix[x][y] = 1
    adj_matrix[y][x] = 1

• 표현법 2 - 인접 리스트
  • 인접 행렬과 비교했을 때 정점이 많고 간선은 상대적으로 작은 상황에서 공간을 절약할 수 있는 방식으로, V개의 리스트를 만들어 각 리스트에 자신과 연결된 정점을 넣어 인접 리스트로 표현할 수 있다

# 인접 리스트로 표현 # 무방향 그래프 # V: 정점 개수, E: 간선 개수
adj_list = [[] for _ in range(V+1)]

for _ in range(E):
    x,y = map(int,input().split())
    adj_list[x].append(y)
    adj_list[y].append(x)

 

• 어떤게 더 효율적일까요?
  • (예시 1) V = 100,000 E  =200,000라면 간선의 개수 E가 V의 제곱보다 훨씬 작기 때문에 인접 리스트를 사용하는게 효율적이다. 사실 애초에 256MB나 512MB 같은 일반적인 메모리 제한에는 V = 100,000이면 표현이 불가하다
  • (예시 2) V = 100 E = 7,000라면 인접 행렬을 사용하는 것이 효율적이다
  • 여러 경로 알고리즘(BFS, DFS emd)에서는 특정 정점에 연결된 모든 정점을 확인하는 경우가 훨씬 많아 인접 리스트가 더 많이 쓰인다. 다만 입력 자체가 인접 행렬로 주어지거나 V가 많이 작아 편의를 챙기거나, 플로이드 알고리즘을 쓸때는 인접 행렬을 사용할 수도 있다

 

 

 

3. 문제 예시

• boj 11724. 연결 요소의 개수 (https://www.acmicpc.net/problem/11724)
  • (문제) 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오
  • (입력) 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다
  • (출력) 첫째 줄에 연결 요소의 개수를 출력한다

# dfs # 재귀로 구현
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)
    
def dfs(v):
    vis[v] = True
    for i in adj[v]:
        if not vis[i]:
            DFS(i)

V,E = map(int,input().split())
adj = [[] for _ in range(V+1)]
vis = [False]*(V+1)

for _ in range(E):
    x,y = map(int,input().split())
    adj[x].append(y)
    adj[y].append(x)

cnt = 0
for i in range(1,V+1):
    if not vis[i]:
        cnt += 1
        dfs(i)

print(cnt)

# bfs
from collections import deque
import sys
input = sys.stdin.readline

def bfs(adj, start, visited):
    queue = deque([start])
    vis[start] = True
    
    while queue:
        now = queue.popleft()
        for i in adj[now]:
            if not vis[i]:
                queue.append(i)
                vis[i] = True  

V,E = map(int,input().split())
adj = [[] for _ in range(V+1)]
vis = [False]*(V+1)

for _ in range(E):
    x,y = map(int,input().split())
    adj[x].append(y)
    adj[y].append(x)
    
cnt = 0
for i in range(1, V+1):
    if not vis[i]:
        bfs(adj, i, vis)
        cnt += 1

print(cnt)

 

 

 

 

 

[출처] 바킹독