- 그래프
그래프는 정점(Vertex)과 간선(Edge)의 집합으로 하나의 간선은 2개의 정점을 연결
그래프는 G=(V,E)로 표현. V=정점의 집합 / E=간선의 집합
무방향 그래프(Undirected Graph) : 간선에 방향이 없는 그래프
방향 그래프(Directed Graph) : 간선에 방향이 있는 그래프
정점 a와 b를 연결하는 간선 : (a,b)
정점 a에서 b로 간선의 방향이 있는 경우 : <a,b>
경로(path) : 시작점 u부터 도착점 v까지의 정점을 나열하여 표현
사이클(cycle) : 시작점과 도착점이 같은 단순 경로
가중치(Weighted) 그래프 : 간선에 가중치가 부여된 그래프
부분 그래프(Subgraph) : 주어진 그래프의 정점과 간선의 일부분으로 이루어진 그래프
트리(Tree) : 사이클이 없는 그래프
신장 트리(Spanning Tree) : 주어진 그래프가 하나의 연결 성분으로 구성되어 있을 때, 그래프의 모든 정점을 사이클 없이 연결하는 부분 그래프
- 그래프 탐색
깊이 우선 탐색(DFS, Depth First Search)
너비 우선 탐색(BFS, Breadth First Search)
깊이 우선 탐색(DFS)이란?
DFS는 임의의 정점에서 시작하여 이웃하는 하나의 정점을 방문하고, 방금 방문한 정점의 이웃 정점을 방문하며, 이웃하는 정점들을 모두 방문하였을 때 이전 정점으로 되돌아가서 탐색을 수행
# DFS 함수 정의
def dfs(graph, start, visited):
# 현재 노드를 방문 처리
visited[start] = True
print(start, end=' ')
# 현재 노드와 연결된 다른 노드들을 재귀적으로 방문
for neighbor in graph[start]:
if not visited[neighbor]:
dfs(graph, neighbor, visited)
# 그래프를 인접 리스트로 표현
graph = {
1: [2, 3, 4],
2: [5, 6],
3: [],
4: [7],
5: [],
6: [],
7: []
}
# 방문 여부를 저장할 리스트 초기화
visited = {node: False for node in graph}
# DFS 실행
dfs(graph, 1, visited)DFS의 예시 코드
1 2 5 6 3 4 7 => 실행결과
- 탐색이 각 정점을 한 번씩 방문하며, 각 간선을 한 번씩만 사용하여 탐색하기 때문에 수행시간은 O(m+n)
n = 그래프의 정점의 수, m = 간선의 수
너비 우선 탐색(BFS)란?
BFS는 임의의 정점 s에서 시작하여 s의 모든 이웃하는 정점들을 방문하고, 방문한 정점들의 이웃 정점들을 모두 방문하는 방식으로 그래프의 모든 정점을 방문
BFS는 이진 트리에서의 레벨 순회와 유사
from collections import deque
# BFS 함수 정의
def bfs(graph, start):
# 방문 여부를 기록할 딕셔너리
visited = {node: False for node in graph}
queue = deque([start]) # 큐 초기화
visited[start] = True # 시작 노드를 방문 처리
while queue:
# 큐에서 노드를 하나 꺼내 출력
current = queue.popleft()
print(current, end=' ')
# 현재 노드의 인접 노드 중 방문하지 않은 노드를 큐에 추가
for neighbor in graph[current]:
if not visited[neighbor]:
queue.append(neighbor)
visited[neighbor] = True
# 그래프를 인접 리스트로 표현
graph = {
1: [2, 3, 4],
2: [5, 6],
3: [],
4: [7],
5: [],
6: [],
7: []
}
# BFS 실행
bfs(graph, 1)BFS의 예시 코드
1 2 3 4 5 6 7 => 실행 결과
- 각 정점을 한 번씩 방문하며, 각 간선을 한 번씩만 사용하여 탐색하기 때문에 O(m+n)의 수행시간이 소요