I about me

[기말고사] 6-3. BFS vs. DFS 본문

Algorithm/Lecture note

[기말고사] 6-3. BFS vs. DFS

ssungni 2024. 6. 11. 01:21
  BFS DFS
  queue(FIFO)
부모의 관계를 체크		 stack(FILO)
Back edge를 신경(=사이클)
  - 앞 친구 이웃 다 넣음?
- 걔 빼고
- 또 앞 친구 이웃 다 넣음? 		 - 깊숙히
- undirected graph → tree edge & back edge
- directed graph →  tree, forward, back, cross edge
// 코드 이해
  // 코드는 cheating paper에 넣을 것 // 코드는 cheating paper에 넣을 것
  1. Shortest path on unweighted graph, undirected
// 코드

2. Finding Connected components
// 코드

3. Two-coloring graphs (biopartite)
부모랑 반대, 같은 색끼리 연결 x
// 코드		 1. Finding Cycle
2. Articulation Vertices
3. Topological Sorting (Dag)
4. Strongly Connected Components

 

'Algorithm > Lecture note' 카테고리의 다른 글

[기말고사] 6-2. 인접 메트릭스 vs. 인접 리스트  (0) 2024.06.10
[기말고사] 6-(1). 그래프 종류  (0) 2024.06.05
[기말고사] 5. Heap and Greedy Approach  (0) 2024.06.03
[중간고사] 4. Dynamic Programming  (1) 2024.04.28
[중간고사] 3-(2). Sorting - Merge Sort  (1) 2024.04.28
'Algorithm/Lecture note' Related Articles more