자료구조, 알고리즘) Graph - About Graph, DFS, BFS

 

Graph

• G = (V, E) 
• V = Vertex ( Node라고 하기도 함, 정점들의 집합)    /   E = Edge (간선들의 집합, 정점들을 잇는 선들의 집합)
• 정점: 대상      /    간선: 정점(대상)들의 관계
  • '인접하다'의 의미

출처: 학교 강의 자료

Graph의 종류

• 기본적인 그래프: 방향, 가중치 X
• 가중 그래프: 방향 X, 가중치 O
• 방향 그래프: 방향 O, 가중치 X
• 가중성 방향 그래프 : 방향 O, 가중치 X

(쉬우니까 그림 생략)

 

 

---

 

 

Adjacency Matrix, Adjacency List (인접 행렬, 인접 리스트)

• n * n 행렬로 표시됨 (n: number of vertex)

Adjacency Matrix

 

 

 

 

 

 

 

 

 

 

 

 출처: 학교 강의 자료

 

 

 

 

Adjacency Array

 

 

 

 

 

 

 

출처: 학교 강의 자료

 

 

 

---

 

 

Graph Traversal

• 임의의 한 정점에서 시작하여 그래프 내의 모든 정점을 방문하는 것
• 대표적인 알고리즘들 - DFS (Depth-First Search), BFS(Breadth-First Search) 

 

 

출처: https://www.freelancinggig.com/blog/2019/02/06/what-is-the-difference-between-bfs-and-dfs-algorithms/

 

 

 

 

BFS 

• 너비 우선 탐색
• Queue를 이용 

BFS Algorithm

출처: 쉽게 배우는 자료구조 with 파이썬 책의 강의록

 

 

 

DFS

• 깊이 우선 탐색
• Recursion, Stack을 이용
• Backtracking을 이용한 Algorithm이다.

DFS Algorithm

출처눈 사진에 명시

 

 

 

출처는 사진에 명시

 

 

 

Difference between DFS and BFS

• DFS는 최단 경로를 보장하지 않으므로, 최단 경로를 찾는 것에 적합하지 않다. -> 즉, Optimal Solution이 아니다.
• BFS는 최단 경로를 보장한다. -> 즉, Optimal Solution이다. (해를 찾으면 그 해가 최적의 해가 된다) 

 

 

 

---