주제
Graph 학습
목표
•
Graph가 무엇인지 안다
키워드
구성요소
◦ 노드(node, N), 간선(edge, E) | 노드와 간선을 모아놓은 자료구조 | 사이클 | 표현방법
- 인접행렬
- 인접리스트 |
깊이 우선 탐색(DFS: Depth-First Search) | 너비 우선 탐색(BFS: Breadth-First Search) | 최단 경로 알고리즘
- 다익스트라
- 벨만 -포드
- 플로이드-워셜 | 백트래킹 |
오일러 경로 | 순환, 비순환 | 무방향, 방향 | 가중 그래프 |
연결, 비연결 그래프 | 완전, 부분 그래프 | 차수
- 진입 차수
- 진출 차수 | 비선형 자료구조 |
정리
정의
그래프(Graph)는 노드(Node)들과 노드들을 연결한 간선(Edge)을 모아놓은 자료구조
조건
정점 하나 이상
탐색 방법
1.
너비 우선 탐색(BFS: Breadth First Search)
2.
깊이 우선 탐색(DFS: Depth First Search)
표현 방법
1.
인접 행렬
2.
인접 리스트
참조
다음 질문
너비 우선 탐색 방법과 구현은 어떻게?