그래프(Graph)란?
실제 세계 현상이나 사물을 정점(Vertex) 또는 노드(Node)와 간선(Edge)으로 표현하기 위해 사용
그래프(Graph) 관련 용어
참고용어
그래프 종류
1) 무방향 그래프 (Undirected Graph)
2) 방향 그래프 (Directed Graph)
3) 가중치 그래프 (Weighted Graph) 또는 네트워크 (Network)
4) 연결 그래프 (Connected Graph)와 비연결 그래프 (Disconnected Graph)
5) 사이틀 (Cycle)과 비순환 그래프 (Acyclic Graph)
사이틀 : 단순 경로의 시작 노드와 종료 노드가 동일한 경우
비순환 : 사이클이 없는 그래프
6) 완전 그래프 (Complete Graph)
그래프의 모든 노드가 서로 연결되어있는 그래프
그래프와 트리의 차이
트리는 그래프에 속한 특별한 종류
ㅤ
ㅤ
ㅤ
ㅤ
ㅤ
대표적인 그래프 탐색 알고리즘
파이썬으로 그래프 표현
1) 너비 우선 탐색 (Breadth First Search)
BFS 알고리즘 구현
code
def bfs(graph, start_node): visited = list() need_visit = list() ㅤ need_visit.append(start_node) ㅤ while need_visit: node = need_visit.pop(0) if node not in visited: visited.append(node) need_visit.extend(graph[node]) // 데이터를 붙일 수 있음 ㅤ return visited ------------------------------------------------ bfs(graph, 'A')
시간 복잡도
일반적인 BFS 시간 복잡도
노드 수 : V
간선 수 : E
위 코드에서 while need_visit은 V+E번만큼 수행
시간 복잡도 : O (V+E)
2) 깊이 우선 탐색 (Depth First Search)
DFS 알고리즘 구현
code
def dfs(graph, start_node): visited = list() need_visit = list() ㅤ need_visit.append(start_node) ㅤ while need_visit: node = need_visit.pop() if node not in visited: visited.append(node) need_visit.extend(graph[node]) // 데이터를 붙일 수 있음 ㅤ return visited ------------------------------------------------ dfs(graph, 'A')
시간 복잡도
일반적인 DFS 시간 복잡도
노드 수 : V
간선 수 : E
위 코드에서 while need_visit은 V+E번만큼 수행
시간 복잡도 : O (V+E)
pop(0) = 큐처럼
pop() = 스택처럼
본 게시글은 fastcampus 이준희강사 수업을 듣고 개인적으로 정리한 내용임을 밝힘.